孩子们的游戏(看了一圈 都没有这个思路 补上)

孩子们的游戏(圆圈中最后剩下的数)

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;
    }
};
全部评论

相关推荐

雪飒:我也遇见过,我反问他有考虑来华为od吗?
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务