题解 | #孩子们的游戏# 逻辑扩展+注释

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

https://www.nowcoder.com/practice/f78a359491e64a50bce2d89cff857eb6

本题是考 “约瑟夫环” 的题型(吐槽:这种类型的题我总是感觉数学性太强了)。

通过“约瑟夫环”得到的结论就是:在约瑟夫环的逻辑下,可以通过某一位置中新环的坐标按照一个数学公式反推到这个位置对应的最开始的坐标。

按照这种逻辑,本题知识求解最后一个人的坐标,因此可以简单地扩展多倒数第x个人的坐标。即如果只求最后一个人,那他在新环中的坐标总是0,否则需要先确定其在新环中的坐标,再由此坐标反推原始坐标。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int recursion(int n, int m, int sum){
        if(n == sum){
            // 在此处的逻辑是求出在约瑟夫环的逻辑下出局的新的编号,不过本题确定求最后一个人,才有了return 0 的特殊形式。
            return 0 + (m-1)%sum;
        } 
        // 此代码表示约瑟夫环的执行逻辑
        int x = recursion(n-1, m, sum);
        // 此行代码表示约瑟夫环的坐标反推逻辑
        return (x + m ) % n;

    }
    
    int LastRemaining_Solution(int n, int m) {
        // write code here
        if(n == 0 || m == 0){
            return -1;
        }
        return recursion(n, m, 1);
    }
};

全部评论

相关推荐

06-12 16:00
天津大学 Java
牛客30236098...:腾讯坏事做尽,终面挂是最破防的 上次被挂了后我连简历都不刷了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务