欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)

程序员文章站 2024-03-07 21:03:03
...

题目:

剑指 Offer 62. 圆圈中最后剩下的数字
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)

题解:约瑟夫环问题

剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)

1. 题解一:模拟链表,O(n²)

剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)

2. 题解二:数学解法,O(n)

剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)
剑指 Offer 62. 圆圈中最后剩下的数字(约瑟夫环问题)

代码:

1. 代码一:模拟链表,O(n²)

import java.util.*;

public class 面试题62 {

    // 方法1:模拟链表
    public static int lastRemaining(int n, int m) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++)
        {
            list.add(i);
        }
        int index = 0;
        while(n > 1)
        {
            index = (index + m - 1) % n;
            list.remove(index);
            n--;
        }
        return list.get(0);
    }

    public static void main(String[] args) {
        int n1 = 5, m1 = 3;
        int res1 = lastRemaining(n1, m1);
        System.out.println(res1); // 3

        int n2 = 10, m2 = 17;
        int res2 = lastRemaining(n2, m2);
        System.out.println(res2); // 2
    }
}

2. 代码二:数学解法,O(n)

import java.util.*;

public class 面试题62 {

    // 方法2:数学解法
    public static int lastRemaining(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人,所以从2开始反推
        for(int i = 2; i <= n; i++)
        {
            ans = (ans + m) % i;
        }
        return ans;
    }

    public static void main(String[] args) {
        int n1 = 5, m1 = 3;
        int res1 = lastRemaining(n1, m1);
        System.out.println(res1); // 3

        int n2 = 10, m2 = 17;
        int res2 = lastRemaining(n2, m2);
        System.out.println(res2); // 2
    }
}

参考:

  1. Java解决约瑟夫环问题,告诉你为什么模拟会超时!
  2. 圆圈中最后剩下的数字
  3. 换个角度举例解决约瑟夫环
  4. 图解约瑟夫环,还送《具体数学》PDF ????吃鲸 Σ(っ °Д °;)っ
  5. c++ 倒推法 【面试题62. 圆圈中最后剩下的数字】
  6. 四种方法,详细解答
  7. python,全真模拟,真·暴力解
  8. 解释递推公式,递归迭代随便写
  9. 理解规律,很简单!JavaScript解法
  10. 约瑟夫环问题图解,多种写法详细思路分析
  11. 这或许是你能找到的最详细约瑟夫环数学推导!
  12. 约瑟夫环——公式法(递推公式)