1. 首页
  2. 剑指offer经典面试题

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

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

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

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

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

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

样例:

输入:n=5 , m=3

输出:3

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

liwei2019101118_1.png

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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3302.html

« [剑指 Offer 第 2 版第 61 题] “n 个骰子的点数”做题记录
[剑指 Offer 第 2 版第 63 题] “股票的最大利润”做题记录»

相关推荐

QR code