目录
-
- 题目：
-
-
- [剑指 Offer 62. 圆圈中最后剩下的数字](https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)
- 题目分析
-
- 初始解答：
- 学习他人：
-
- 方法一:
- 方法二：
- 方法三：
- 方法四：
- 总结
刷题日期：下午8:42 2021年5月26日星期三
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 62. 圆圈中最后剩下的数字
难度简单369
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
题目分析
如果能用循环链表一类的存放肯定就简单多了，直接遍历到剩唯一一个即可。
肯定不能直接用数组来弄，因为数组的特点就是查找简单但是插入删除麻烦，而且数组长度在100000，稍微长一点就会超时。
单纯的存在链表也不好用，同样因为长度太长，占用空间会很大。
最好就是找到某个数学公式，直接计算出来何时能把n轮完，计算得到下标直接返回即可。
初始解答：
举例子尝试了下，规律还是不太好找，而且感觉可能还是一道动态规划的题。
看了K神的分析，果然逃不过动态规划，但是分析完也太简单了吧，果然还是自己太菜。
class Solution {
public int lastRemaining(int n, int m) {
int x = 0;
// 不论如何最后一轮剩下2个，所以从2开始
for(int i = 2; i <= n; i++) {
x = (x + m) % i;
}
return x;
}
}
执行结果：通过
显示详情 添加备注
执行用时：7 ms, 在所有 Java 提交中击败了99.88%的用户
内存消耗：34.9 MB, 在所有 Java 提交中击败了98.53%的用户
给跪了orz
学习他人：
方法一:
Sweetiee🍬的小号L5 （编辑过）2020-03-30
关于为什么有的模拟会超时，可以移步👉我的题解👈，里面有更详细的说明~
这个问题是以弗拉维奥·约瑟夫命名的，他是1世纪的一名犹太历史学家。他在自己的日记中写道，他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘，最终决定自杀，并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人，他们将向罗马军队投降，不再自杀。约瑟夫斯把他的存活归因于运气或天意，他不知道是哪一个。 —— 【约瑟夫问题】维基百科
- 模拟做法：
class Solution {
public int lastRemaining(int n, int m) {
ArrayList<Integer> list = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
list.add(i);
}
int idx = 0;
while (n > 1) {
idx = (idx + m - 1) % n;
list.remove(idx);
n--;
}
return list.get(0);
}
}
- 数学方法：
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
方法二：
eeloo 2021-04-01 555，完全靠自己一遍过的。。在草稿纸里写着写着慢慢推出了公式，雨点小激动。
class Solution {
public int lastRemaining(int n, int m) {
int pos=0; //初始化位置，后面要用做记录每一轮开始的位置。
List<Integer> list= new ArrayList<>();
for(int i=0;i<n;i++)
list.add(i); //先把所有数加到动态数组里。
while(list.size()>1){ //循环条件要求list大小大于1，当只剩下最后一个数了就跳出
int temp=(pos+m-1)%list.size();
list.remove(temp);
pos=temp;
}
return list.get(0);
}
}
方法三：
user1544tL1 2021-03-26 终于说服了自己
class Solution {
public int lastRemaining(int n, int m) {
return f(n, m);
}
private int f(int n, int m) {
if (n == 1) return 0;
// 获得相对于长度(n-1)序列最终剩下的下标
int x = f(n - 1, m);
// 拿到的x不能直接用 因为这是从0开始算的
// 那么加上偏移量m 就翻译成了长度n序列的下标
return (m % n + x) % n;
}
}
方法四：
K神 模拟整个删除过程最直观，即构建一个长度为 n 的链表，各节点值为对应的顺序索引；每轮删除第 m 个节点，直至链表长度为 1 时结束，返回最后剩余节点的值即可。
作者：jyd
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
来源：力扣（LeetCode）
如下图所示，为 n = 5n=5 , m = 3m=3 时的状态转移和对应的模拟删除过程。
class Solution {
public int lastRemaining(int n, int m) {
int x = 0;
for (int i = 2; i <= n; i++) {
x = (x + m) % i;
}
return x;
}
}
总结
关于以后：
Peter-12138L1 2021-02-24
k神太强了！顺便请教一下，我打算今年7.8月找工作，现在已经把剑指offer刷了两遍，接下来应该刷“热题hot 100”还是“LeetCode精选面试题”呢？
KrahetsL6 2021-02-25
@Peter-12138 哈喽，这两个 tab 都挺好的，可以先刷两个 tab 里的重合题目（应该也会有部分和剑指offer题目重合，可以当作测试是否已经掌握）~ 如果时间充裕的话可以都刷，或者着重刷一些 动态规划、DFS 的题目，个人感觉笔试比较喜欢出~ 也可以去力扣讨论区看看大佬们的刷题经验哈~
以上就是本题的内容和学习过程了，模拟或者找规律，模拟需要链表操作，找规律需要大佬思维，就这样。
欢迎讨论，共同进步。