Leecode 面试题62. 圆圈中最后剩下的数字

简介: Leecode 面试题62. 圆圈中最后剩下的数字

题目描述:

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

限制:

1 <= n <= 10^5

1 <= m <= 10^6

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思想:这个题的解题思维可以参考解决约瑟夫环问题的想法,从2每次循环,然后

第一轮是 [0, 1, 2, 3, 4] ,所以是 [0, 1, 2, 3, 4] 这个数组的多个复制。这一轮 2 删除了。

第二轮开始时,从 3 开始,所以是 [3, 4, 0, 1] 这个数组的多个复制。这一轮 0 删除了。

第三轮开始时,从 1 开始,所以是 [1, 3, 4] 这个数组的多个复制。这一轮 4 删除了。

第四轮开始时,还是从 1 开始,所以是 [1, 3] 这个数组的多个复制。这一轮 1 删除了。

最后剩下的数字是 3。

图中的绿色的线指的是新的一轮的开头是怎么指定的,每次都是固定地向前移位 mm 个位置。

然后我们从最后剩下的 3 倒着看,我们可以反向推出这个数字在之前每个轮次的位置。

最后剩下的 3 的下标是 0。

第四轮反推,补上 mm 个位置,然后模上当时的数组大小 22,位置是(0 + 3) % 2 = 1。

第三轮反推,补上 mm 个位置,然后模上当时的数组大小 33,位置是(1 + 3) % 3 = 1。

第二轮反推,补上 mm 个位置,然后模上当时的数组大小 44,位置是(1 + 3) % 4 = 0。

第一轮反推,补上 mm 个位置,然后模上当时的数组大小 55,位置是(0 + 3) % 5 = 3。

所以最终剩下的数字的下标就是3。因为数组是从0开始的,所以最终的答案就是3。

总结一下反推的过程,就是 (当前index + m) % 上一轮剩余数字的个数。

class Solution {
    public int lastRemaining(int n, int m) {
        int ans = 0;
        for(int i = 2;i <= n;i++ ){
            ans = (ans + m) % i;
        }
        return ans;
    }
}


相关文章
|
6月前
Leecode之面试题消失的数字
Leecode之面试题消失的数字
|
存储
Leecode 面试题 17.16. 按摩师
Leecode 面试题 17.16. 按摩师
64 0
Leecode面试题40. 最小的k个数
Leecode面试题40. 最小的k个数
64 0
Leecode 面试题 01.06. 字符串压缩
Leecode 面试题 01.06. 字符串压缩
43 0
|
存储
Leecode面试题43. 1~n整数中1出现的次数
Leecode面试题43. 1~n整数中1出现的次数
69 0
Leecode 面试题57 - II. 和为s的连续正数序列
Leecode 面试题57 - II. 和为s的连续正数序列
48 0
|
机器学习/深度学习
Leecode面试题64
Leecode面试题64
63 0
|
Java
Leecode 面试题09用两个栈实现队列
Leecode 面试题09用两个栈实现队列
64 0
|
3月前
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
8天前
|
存储 算法 Java
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?