有個游戲是這樣的：首先，讓小朋友們圍成一個大圈，然后，隨機指定一個數 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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/188905.html
標籤：其他
上一篇：有趣的神級注釋