1 题目描述
每年六一儿童节，牛客都会准备一些小礼物去看望孤儿院的小朋友，今年亦是如此。HF作为牛客的资深元老，自然也准备了一些小游戏。其中,有个游戏是这样的：首先，让小朋友们围成一个大圈。然后，他随机指定一个数m，让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续0...m-1报数....这样下去....直到剩下最后一个小朋友，可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1) 如果没有小朋友，请返回-1。
2 思路和方法
思路一：
考虑用环形链表解决；用stl中的list来模拟环形链表。list本身不是环形结构，所以每当迭代器扫描到链表末尾时，需要把迭代器移到链表的头部，list的erase方法删除节点后，原来的迭代器会失效，所以需要保存下一个节点。或者使用vector模拟环形链表。
思路二：
https://blog.****.net/SCS199411/article/details/92988332
分析每次被删除数字的规律直接计算出圆圈中最后剩下的数字。隐函数f(n,m)为在n个数字中每次删除第m个数字最后剩下的数字。
相关知识点：
取余运算的一些性质需要熟悉：一、某数取余多次与取一次相等，例如5%2=1，而5%2%2%2=1；二、取余运算满足结合律，例如a%n - 1=(a-1)%n (n > 1)；三、如果对于一个明显不在[0, n-1]区间的数x，在该区间的同余数有且只有1个。例如x = -2，-2%n=n-2。
3 C++核心代码
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
// 环形链表
// STL中的list只有没有循坏，每次访问到链表末尾时要重新指向链表头
int LastRemaining_Solution(int n, int m){
if (n< || m<)
return ;
list<int> nums;
for (int i = ; i < n; ++i) {
nums.push_back(i);
}
list<int>::iterator cur = nums.begin();
while (nums.size()>){
for (int i = ; i < m; ++i) {
cur++;
if(cur == nums.end())
cur = nums.begin();
}
list<int>::iterator next = ++cur; // 保存下一个节点
if (next == nums.end())
next = nums.begin();
cur--;
nums.erase(cur); // 删除该节点
cur = next; // 指向下一个节点
}
return *(cur);
}
};
class Solution {
public:
int LastRemaining_Solution(int n, int m)
{
if(n < || m < ) //守卫代码
return -;
//int last = 0;
//for (int i = 2; i<=n; ++i){
// last = (last+ m) % i;
//}
//return last;
if(n == )
return ;
return (LastRemaining_Solution(n-, m) + m) % n;
}
};
4 C++完整代码
#include <iostream>
#include <vector>
#include <list> using namespace std; int LastRemaining_Solution(int n, int m); int main() {
cout << LastRemaining_Solution(, ) << endl; system("pause");
return ;
} int LastRemaining_Solution(int n, int m) {
if (n < || m < )return -; //使用vector来模拟一个环形链表
vector<int> num;
for (int i = ; i != n; i++) {
num.push_back(i);
} int start = ;
while (num.size() > ) {
int cntDown = m;
int mv = start;
while (--cntDown) {
//如果遍历到了最后一个数字，下一个遍历数组首个数字
if (mv == (num.size() - )) {
mv = ;
}
else {
mv++;
}
} if (mv == (num.size() - )) {
start = ;
}
else {
start = mv;
}
num.erase(num.begin()+mv);
} return num[];
}
参考资料
https://blog.****.net/zjwreal/article/details/88917056
https://blog.****.net/m0_37950361/article/details/82154753
https://blog.****.net/SCS199411/article/details/92988332