移动互联网发展史_宁波网站建设信任荣盛网络_百度快速收录技术_百度搜索排名服务

题干

1823. 找出游戏的获胜者 - 力扣（LeetCode）

这个就是约瑟夫环的问题。太难了，根本抽象不出来，抽象出来了也不会改递归，盯着公式看了半小时人都懵懵的。b站上的视频讲解也感觉讲的人是蒙的。

个人觉得，先看解法1，再在基础上背诵下来解法2 争取解法1可以面试时候考理解写下来。
但是这玩意，就像是跳台阶一样，当前看很难，现在看很简单。再回首时可以轻松秒杀。

解法1

    public int findTheWinnerA(int n, int m) {if (m == 1)return n - 1 + 1;  // 本题，下标从0开始算，答案从1开始算，因为加1List<Integer> list = new ArrayList<>();// 先把下标都给进来for (int i = 0; i < n; i++) {list.add(i);}int index = 0;while (list.size() > 1) {// 这里减去1是因为计数的关系index = (index + m - 1) % (list.size());  // 从左到右数m个 然后将index踢掉list.remove(index);}return list.get(0) + 1;}

解法2

这里需要进行递归的抽象 index = (index + m - 1) % (list.size());
这里的f(n) = f(n-1)+m-1 % n
很多题解的写法，变量多的看的我眼花。这里就是n状态的答案，是如何依赖n-1的答案的规律，然后，n为0的时候，下标也是0

    public static int findTheWinner(int n, int m) {return f(n, m);}public static int f(int n, int m) {if (n == 1) {return 1;}// 依赖于上面一个return (f(n - 1, m) + m - 1) % n + 1;}