孩子们的游戏(看了一圈 都没有这个思路 补上)
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6
思路
设置一个状态数组,是否被选中过,一开始将所有数组元素置为1,然后只要被选中就置为0,分别设置一个num和count(初始值为0)计数,如果num的值等于m选中此位置,然后选中一个count加1,当count 等于 n-1 时跳出循环,最后为1的数就是最后留下来的
class Solution { public: int LastRemaining_Solution(int n, int m) { int status[1000]; int count=0,num = 0; memset(status, 0, sizeof(status)); for(int i=1;i<=n;i++){ status[i] = 1; } if(n==0||m==0){ return -1; } // 用状态数组 while(count<n-1){ for(int i=1;i<=n;i++){ if(status[i]==1) num++; if(num == m){ status[i] =0; count++; num = 0; } if(count == n-1) break; } } int res=0; for(int i=0;i<=n;i++){ if(status[i] == 1 ) res =i-1; } return res; } };