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

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

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);
    }
};

全部评论

相关推荐

叶扰云倾:进度更新,现在阿里云面完3面了,感觉3面答得还行,基本都答上了,自己熟悉的地方也说的比较细致,但感觉面试官有点心不在焉不知道是不是不想要我了,求阿里收留,我直接秒到岗当阿里孝子,学校那边的房子都退租了,下学期都不回学校,全职猛猛实习半年。这种条件还不诱人吗难道 然后现在约到了字节的一面和淘天的复活赛,外加猿辅导。华为笔试完没动静。 美团那边之前投了个base广州的,把我流程卡麻了,应该是不怎么招人,我直接简历挂了,现在进了一个正常的后端流程,还在筛选,不知道还有没有hc。
点赞 评论 收藏
分享
06-25 16:25
梧州学院 Java
愿汐_:项目介绍那么长,然而你做了啥就一句话?
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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