题目描述
如果采用模拟的方法，比如新建链表之类的会超时。
此问题是一个约瑟夫环问题，利用数学手段得到公式为：f(n,m)=[f(n−1,m)+m]%n。
约瑟夫环
每次杀掉一个人，从后面的人开始重新编号，会发现最后的一个人为0。如果从 n = 1 递推，就会发现上面的公式：
公式
class Solution {
public int lastRemaining(int n, int m) {
int pos = 0;
for(int i = 2; i <= n; i++){
pos = (pos + m) % i;
}
return pos;
}
}
剑指 Offer 62. 圆圈中最后剩下的数字[https://leetcode.cn/problems/yuan...
LeetCode 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Easy】【Python】【数学】 问题 ...
1、前言 2、思路 如果采用模拟的方法，比如新建链表之类的会超时。 此问题是一个约瑟夫环问题，利用数学手段得到公式...
本系列导航：剑指offer（第二版）java实现导航帖 面试题62：圆圈中最后剩下的数字 题目要求：0，1，2.....
题意：0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数...
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个...
有公式= =。。但是n == 1的时候返回0？ 三目运算符的 非递归 自上而下的内存消耗比较低。。
题目链接： 剑指offer 60-68 目录： 60. n 个骰子的点数61. 扑克牌顺子62. 圆圈中最后剩下的...
题目 题目:有n个人,围成一个环，编号为 0、1、2、3、、、n-1，从第一个人开始循环报数(从1开始)，假设数到...
这是一道约瑟夫环的问题，想不出来。 图解原文链接
本文标题：剑指 Offer 第62题：圆圈中最后剩下的数字
本文链接：https://www.haomeiwen.com/subject/uxobbrtx.html
网友评论