有个游戏是这样的：首先，让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m - 1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0 ... m - 1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演,并且拿到一份珍贵的礼品。请你试想下，哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从 0 到 n - 1)
解题思路
其实这是一个约瑟夫环问题：如果不想死记公式，可以直接模拟游戏过程
import java.util.LinkedList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0) {
return -1;
}
int bt = 0;
LinkedList<Integer> list = new LinkedList<>();
for(int i = 0; i < n; i++) {
list.add(i);
}
while(list.size() != 1) {
bt = (m - 1 + bt) % list.size();
list.remove(bt);
}
return list.getFirst();
}
}
或者使用数组来模拟
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n <= 0) {
return -1;
}
int[] array = new int[n];
int i = -1;
int count = n;
int step = 0;
while(count > 0) {
// 指向上一个被删除对象的下一个元素
i++;
// 模拟环
if(i == n) {
i = 0;
}
// 跳过被删除的对象
if(array[i] == -1) {
continue;
}
// 记录已走过的
step++;
// 找到待删除的对象
if(step == m) {
array[i] = -1;
step = 0;
count--;
}
}
// 返回跳出循环时的i,即最后一个被设置为 -1 的元素
return i;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
