列表

详情


NC132. 环形链表的约瑟夫问题

描述

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?

数据范围: 
进阶:空间复杂度 ,时间复杂度

示例1

输入:

5,2     

输出:

3    

说明:

开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开 1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开 1,3,5,从5开始报数,5->1,1->2编号为1的人离开 3,5,从3开始报数,3->1,5->2编号为5的人离开 最后留下人的编号是3

示例2

输入:

1,1

输出:

1

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++ 解法, 执行用时: 2ms, 内存消耗: 356KB, 提交时间: 2021-06-08

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int res = 0;
        for(int i=2; i <= n; ++i)
        {
            res = (res + m) % i;
        }
        return res + 1;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 360KB, 提交时间: 2021-05-28

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        if(n == 1){
            return 0;
        }
        int res = 0;
        int count = n-1;
        while(count--){
            res = (res+m)%(n-count);
        }
        return res+1;

    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 392KB, 提交时间: 2021-07-20

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int p = 0;
        for(int i=2;i<=n;i++){
            p = (p+m)%i;
        }
        return p + 1;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 404KB, 提交时间: 2021-09-08

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
//         if(n==1)
//             return 0;
        int x=0; //编号从0开始
        for(int i=2;i<=n;++i)
            x=(x+m)%i;
        return x+1;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 404KB, 提交时间: 2021-09-07

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
        // write code here
        int res=0;
        int j=2;
        while(j<=n){
            res=(m%j+res)%j;
            j++;
        }
        return res+1;
    }
};

上一题