[剑指 Offer 第 2 版第 62 题] “孩子们的游戏(圆圈中最后剩下的数)”做题记录

第 62 题：孩子们的游戏（圆圈中最后剩下的数）

传送门：圆圈中最后剩下的数字，牛客网 online judge 地址。

0, 1, …, n-1 这 n 个数字 (n>0) 排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。

求出这个圆圈里剩下的最后一个数字。

样例：

输入：n=5 , m=3

输出：3

思路1：使用环形链表模拟约瑟夫环。注意特例，即 n==0 成立，没有数字的时候，返回 -1 即可。

Python 写法：记住这种写法，两个要点。

  class Solution:
        def lastRemaining(self, n, m):
            # 特判
            if n == 0 and m == 0:
                return -1

            l = [i for i in range(n)]
            bt = 0
            while len(l) > 1:

                # 在这一行模拟约瑟夫环操作
                # 1、m - 1 ：因为当前数字算 1 个，走 m - 1 步
                # 2、len(l)：每次删去一个数，所以得动态取
                bt = (bt + m - 1) % len(l)

                l.pop(bt)
            return l[0]

Java 代码：

  import java.util.LinkedList;

    public class Solution {
        // 约瑟夫环问题
        // 其实并不一定要构造出一个真的循环链表
        public int LastRemaining_Solution(int n, int m) {
            // 这里用链表是为了提升性能，如果用 ArrayList 在删除操作中，就会有大量的性能消耗
            LinkedList<Integer> list = new LinkedList<>();
            int bt = 0;
            for (int i = 0; i < n; i++) {
                list.addLast(i);
            }
            while (list.size() > 1) {
                bt = (bt + m - 1) % list.size();
                list.remove(bt);
            }
            // 思考为什么会有最后这个判断
            return list.size() == 1 ? list.get(0) : -1;
        }
    }

Java 代码：

  import java.util.LinkedList;

    public class Solution {
        // 约瑟夫环问题
        // 其实并不一定要构造出一个真的循环链表
        public int LastRemaining_Solution(int n, int m) {
            // 先处理极端输入
            if (n <= 1) {
                return -1;
            }
            // 这里用链表是为了提升性能，如果用 ArrayList 在删除操作中，就会有大量的性能消耗
            LinkedList<Integer> list = new LinkedList<>();
            int bt = 0;
            for (int i = 0; i < n; i++) {
                list.addLast(i);
            }
            while (list.size() > 1) {
                // 表示的是索引的值
                bt = (bt + m - 1) % list.size();
                // 下面这一行代码可以帮助调试
                // System.out.println(bt + " " + list);
                // bt 是链表的索引
                list.remove(bt);
            }
            // 思考为什么会有最后这个判断
            return list.get(0);
        }

        // 测试用例： n = 6，[0,1,2,3,4,5]，m=3
        public static void main(String[] args) {
            Solution solution = new Solution();
            int n = 6;
            int m = 3;
            int lastRemainingSolution = solution.LastRemaining_Solution(n, m);
            System.out.println(lastRemainingSolution);
        }
    }

思路2：书上说的，使用数学方法。

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/