约瑟夫环(超好的代码存档)--19--约瑟夫环--LeetCode面试题62(圆圈最后剩下的数字)
2024-08-25 03:24:11
圆圈中最后剩下的数字
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
class Solution {
public int lastRemaining(int n, int m) {
if (n == 1)
return 0;
int now = lastRemaining(n - 1, m);
return (m % n + now) % n;
}
/* 淘汰顺序
n = 1:一个元素:0 0 最后一次淘汰的下标是0
n = 2:两个元素:0 1 3 % 2 + 0 == 1 1 % 2 == 1 0 1 最后一次淘汰的下标是1
n = 3:三个元素:0 1 2 3 % 3 + 1 == 1 1 % 3 == 1 2 0 1 最后一次淘汰的下标是1
n = 4:四个元素:0 1 2 3 3 % 4 + 1 == 4 4 % 4 == 0 2 1 3 0 最后一次淘汰的下标是0
n = 5:五个元素:0 1 2 3 4 3 % 5 + 0 == 3 3 % 5 == 3 2 0 4 1 3 最后一次淘汰的下标是3
*/
}
最新文章
- 【原】作为前端需要了解的B/S架构
- Python小游戏之猜数字
- Samba配置文件常用参数详解-OK
- cocos2d-x实战 C++卷 学习笔记--第5章 精灵
- python学习第十天 -- 函数
- python中的model模板中的数据类型
- 面向对象程序设计-C++_课时24多态的实现
- 怎么破解Wifi密码
- 添加组groupadd,修改组groupmod,删除组groupdel,将用户加入删除组gpasswd
- 书写Css文件要点
- 15-TypeScript策略模式
- IOC的理解,整合AOP,解耦对Service层和Dal层的依赖
- openpyxl工具总结
- what is MAC address
- python_代码中调用java类
- Percona Server 5.6 安装TokuDB
- clojure中符号symbols 和变量vars的正确理解
- Istio 1.1尝鲜记
- wifi测距
- 8.8.8.8和8.8.4.4 DNS域名解析服务器