题目描述：
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
思路：
- 方法一
看到题目的第一个想法就是用vector来模拟报数过程，把每轮中奖的小朋友标记一下，表示已经离开，所以每轮数m个人，遇到有标记的小朋友要跳过。最后剩下的那个小朋友就是获得大奖的小朋友了~
这种方法逻辑上没得说，形象易懂。
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
vector<bool> flags(n, false);
int count = 1;
int kid = 0;
while (count < n) {
for (int i = 0; i < m; i++) {
if (flags[kid])
i--;
kid = (kid + 1) % n;
}
kid--;
if (kid < 0)
kid = n - 1;
flags[kid] = true;
count++;
}
for (int i = 0; i < n; i++) {
if (flags[i] == false)
return i;
}
return -1;
}
};
- 方法二
对于这种有规则的过程，肯定是有数学公式可以简便计算的~当然我并没有想出来，看了解析后才知道的。
对每轮的小朋友都重新编号，如果第i轮某个小朋友所在位置为f(i)，那么该小朋友在前一轮所在位置f(i-1)与f(i)是存在关联的，因此，从最后一轮获得大奖的小朋友所在位置就可以向前反推这个小朋友在各轮中所在的位置。
举个例子现在有n = 4个小朋友：0 1 2 3，令m = 2。总共需要4轮就可以找到最后一个小朋友。
| 轮数 | 序列(每轮重新编号) | 获得大奖的小朋友在本轮中所在的位置 | 说明 |
|---|---|---|---|
| 第4轮 | v = [0] | f(4) = m % 1 = 0 | 只剩一个小朋友时一定是他获奖，令B表示这个小朋友 |
| 第3轮 | v = [0 1] | f(3) = (m + f(4)) % 2 | 本轮中奖小朋友在(m-1)%2，下轮中奖小朋友即B在此轮中的位置为(m-1+1+f(4)) % 2 = (m+f(4)) % 2。即f(3)表示小朋友B在本轮中的位置。 |
| 第2轮 | v = [0 1 2] | f(2) = (m + f(3)) % 3 | f(3)表示下一轮中B所在位置，那么B在此轮中所在位置为(m+f(3)) % 3 |
| 第1轮 | v = [0 1 2 3] | f(1) = (m + f(2)) % 4 | 同上，由下一轮中B所在位置来反推B在此轮中的位置 |
因此，从最后一轮中奖小朋友的位置向前反推大奖小朋友B在各轮中的位置，整个过程就是一个递归的过程。
目标在第i轮中的位置： f(i) = ( m + f(i + 1) ) % (n - i + 1) 且f(n) = 0
代码如下：
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if (n < 1)
return -1;
else if (n == 1)
return 0;
else
return (m + LastRemaining_Solution(n - 1, m)) % n;
}
};
- 方法三
将方法二中的递归过程反过来写成循环的过程，效率更高。前提是理解递归表达式
目标在第i轮中的位置： f(i) = ( m + f(i + 1) ) % (n - i + 1) 且f(n) = 0
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if (n < 1)
return -1;
else {
int res = 0;
for (int i = 1; i < n; i++)
res = (m + res) % (i + 1);
return res;
}
}
};
网友评论