经典面试题 （一） 猫午睡问题 Kaki的博客

经典面试题 （一） 猫午睡问题 Kaki的博客

经典面试题 （一） 猫午睡问题    Kaki的博客

问题描述：

       假设两只猫住在一起，都喜欢睡觉，它们每小时都会循环地更换午睡的地方。

现在给定 n 个可以睡觉的位置：

➢ 猫 A 按顺序更换它的午睡地： , 1, 2, ,3,2,1, , 1, n n n n n − − − ，换句话 说，在第 1 个小时里，它在 n 的位置上，然后按顺序循环递减。

➢ 猫 B 按顺序改变它的午睡地点: 1,2,3, , 1, ,1,2, n n − ，换句话说，在

       第 1 个小时里，它在 1 的位置上，然后以循环的方式递增。 猫 B 比猫 A 要年轻得多，所以它们有严格的等级制度。A 和 B 不能同时在一 个位置上睡觉。换句话说，当某个小时的开始时刻，如果两只猫将要去睡觉的位 置相同（例如 x 号位置），那么 A 将会占用这个位置睡觉，而 B 必须按它的顺序 挪到下一个位置去睡觉（如果 x>n，就到 x+1，但如果 x=n，就到 1）。

       试计算一下，猫 B 在第 k 小时的开始时刻将占用哪个位置睡觉？

⚫要求：

完成题目对应的程序模板（CatSleeping）中的方法：
       int findPosition(int n, int k);
       该方法的入口参数 n 为两个猫睡觉的位置总数，参数 k 为第 k 小时的开始 时刻； 最后输出结果为猫 B 在第 k 小时的开始时刻所能占用的位置 提示         • 2 <= n <= 10(9次幂)
        • 1 <= k <= 10(9次幂)

⚫ 样例：

     ◼ 样例 1      输入：n = 4, k = 2      输出：2

     解释：第 1 个小时的开始时刻，猫 B 移到位置 1 睡觉，第 2 个小时的开
始时刻，按照顺序，猫 B 将移到位置 2 睡觉，所以输出结果为 2

     ◼ 样例 2
     输入：n = 3, k = 2
     输出：3
     解释：第 2 个小时的开始时刻，猫 A 和猫 B 都来到了位置 2，按照等级，猫 B 必须让出位置 2，前往位置 3 睡觉，所以输出结果为 3

解答：

package st;/*** @author Kaki Nakajima* @date   2020-05-15* @desc   猫午睡问题*/
public class CatSleeping {/*** 猫午睡问题* @param n 可移动的睡觉位置* @param k 几个小时时间内* @return 最后输出结果为猫 B 在第 k 小时的开始时刻所能占用的位置*/public static int findPosition(int n, int k){//分析1: 猫A 递减，猫B 递增//分析2： 当睡觉位置有交集时，猫A 跳到下一个位置//猫B 移动统计int maoBCount = 0;int maoAPosition = n; //猫A 位置int maoBPosition = 1; //猫B 位置//循环(时间)for (int i=k; k >0 ; k--) {maoBCount ++;maoAPosition --;//猫A 递减maoBPosition ++;//猫B 递增//循环位置if(maoAPosition == 1){maoAPosition = n;}if(maoBPosition >=n){maoBPosition = 1;}//交集的情况 (当睡觉位置有交集时，猫A 跳到下一个位置)if(maoAPosition == maoBPosition){maoBCount++;maoAPosition --;}}return maoBCount;}public static void main(String[] args) {//n = 4, k = 2...  n = 3, k = 2System.out.println(findPosition(3,8));}
}

此处方法只是实现之一，如有更高效的方法可以在评论区留言哈~

码云地址直通车

欢迎码云，B站，ins 关注Kaki Nakajima