剑指 Offer 62. 圆圈中最后剩下的数字


剑指 Offer 62. 圆圈中最后剩下的数字

难度简单 300
0,1,···,n-1 这 n 个数字排成一个圆圈,从数字 0 开始,每次从这个圆圈里删除第 m 个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4 这 5 个数字组成一个圆圈,从数字 0 开始每次删除第 3 个数字,则删除的前 4 个数字依次是 2、0、4、1,因此最后剩下的数字是 3。

示例 1:
输入: n = 5, m = 3
**输出: **3

示例 2:
输入: n = 10, m = 17
**输出: **2

     public int lastRemaining1(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) &#123;
            list.add(i);
        &#125;
        int idx = 0;
        while (n > 1) &#123;
            idx = (idx + m - 1) % n;
            list.remove(idx);
            n--;
        &#125;
        return list.get(0);

// 作者:sweetieeyi
// 链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
    &#125;

假设当前删除的位置是 idx,下一个删除的数字的位置是 idx+m 。但是,由于把当前位置的数字删除了,后面的数字会前移一位,所以实际的下一个位置是 idx+m−1。由于数到末尾会从头继续数,所以最后取模一下,就是
(idx+m−1)(mod n)。

作者:sweetieeyi
链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/


动态规划

    public int lastRemaining1(int n, int m) &#123;
        int[] ans = new int[n+1];
        ans[0] = 0;
        // 最后一轮剩下2个人,所以从2开始反推
        for (int i = 1; i <= n; i++) &#123;
            ans[i] = (ans[i-1] + m) % i;
        &#125;
        return ans[n];
    &#125;

    public int lastRemaining(int n, int m) &#123;
        int[] ans = new int[n+1];
        ans[1] = 0;
        // 最后一轮剩下2个人,所以从2开始反推
        for (int i = 2; i <= n; i++) &#123;
            ans[i] = (ans[i-1] + m) % i;
        &#125;
        return ans[n];
    &#125;

动态规划解析:

状态定义: 设「i,m 问题」的解为 dp[i] ;
状态转移方程: 通过以下公式可从 dp[i−1] 递推得到 dp[i] ;dp[i]=(dp[i−1]+m)%i;

初始状态:「1,m 问题」的解恒为 0 ,即 dp[1]=0 ;
返回值: 返回「n,m 问题」的解 dp[n] ;

作者:jyd
链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


动态规划优化版

    public int lastRemaining(int n, int m) &#123;
        int ans = 0;
        // 最后一轮剩下2个人,所以从2开始反推
        for (int i = 2; i <= n; i++) &#123;
            ans = (ans + m) % i;
        &#125;
        return ans;
    &#125;

// 作者:sweetieeyi
// 链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/

文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
202. 快乐数 202. 快乐数
202. 快乐数难度简单 541编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为: 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。 如
下一篇 
405. 数字转换为十六进制数 405. 数字转换为十六进制数
405. 数字转换为十六进制数给定一个整数,编写一个算法将这个数转换为十六进制数。对于负整数,我们通常使用 补码运算 方法。注意: 十六进制中所有字母(a-f)都必须是小写。 十六进制字符串中不能包含多余的前导零。如果要转化的数为 0,那
  目录