当前位置:网站首页>leecode学习笔记-约瑟夫问题
leecode学习笔记-约瑟夫问题
2022-07-04 13:23:00 【喜欢历史的工科生】
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;
}
}
- 解释
帮助理解
问题1: 假设我们已经知道11个人时,胜利者的下标位置为6。那下一轮10个人时,胜利者的下标位置为多少?
答: 其实吧,第一轮删掉编号为3的人后,之后的人都往前面移动了3位,胜利这也往前移动了3位,所以他的下标位置由6变成3。问题2: 假设我们已经知道10个人时,胜利者的下标位置为3。那下一轮11个人时,胜利者的下标位置为多少? 答:
这可以看错是上一个问题的逆过程,大家都往后移动3位,所以f ( 11 , 3 ) = f ( 10 , 3 ) + 3
f(11,3)=f(10,3)+3f(11,3)=f(10,3)+3。不过有可能数组会越界,所以最后模上当前人数的个数,f ( 11 , 3
) = ( f ( 10 , 3 ) + 3 ) % 11
f(11,3)=(f(10,3)+3)%11f(11,3)=(f(10,3)+3)%11
最后只剩下一个元素,假设这个最后存活的元素为 num, 这个元素最终的的下标一定是0 (因为最后只剩这一个元素),
所以如果我们可以推出上一轮次中这个num的下标,然后根据上一轮num的下标推断出上上一轮num的下标,
直到推断出元素个数为n的那一轮num的下标,那我们就可以根据这个下标获取到最终的元素了。推断过程如下:
首先最后一轮中num的下标一定是0, 这个是已知的。
那上一轮应该是有两个元素,此轮次中 num 的下标为 (0 + m)%n = (0+3)%2 = 1; 说明这一轮删除之前num的下标为1;
再上一轮应该有3个元素,此轮次中 num 的下标为 (1+3)%3 = 1;说明这一轮某元素被删除之前num的下标为1;
再上一轮应该有4个元素,此轮次中 num 的下标为 (1+3)%4 = 0;说明这一轮某元素被删除之前num的下标为0;
再上一轮应该有5个元素,此轮次中 num 的下标为 (0+3)%5 = 3;说明这一轮某元素被删除之前num的下标为3;
…因为我们要删除的序列为0-n-1, 所以求得下标其实就是求得了最终的结果。比如当n 为5的时候,num的初始下标为3,
所以num就是3,也就是说从0-n-1的序列中, 经过n-1轮的淘汰,3这个元素最终存活下来了,也是最终的结果。总结一下推导公式:(此轮过后的num下标 + m) % 上轮元素个数 = 上轮num的下标
边栏推荐
- Count the running time of PHP program and set the maximum running time of PHP
- Query optimizer for SQL optimization
- Chapter 17 process memory
- Alcohol driving monitoring system based on stm32+ Huawei cloud IOT design
- Xcode abnormal pictures cause IPA packet size problems
- 5G电视难成竞争优势,视频资源成中国广电最后武器
- Data Lake (13): spark and iceberg integrate DDL operations
- 现代控制理论入门+理解
- LVGL 8.2 text shadow
- Node mongodb installation
猜你喜欢
Intelligence d'affaires bi analyse financière, analyse financière au sens étroit et analyse financière au sens large sont - ils différents?
LVGL 8.2 LED
LVGL 8.2 Draw label with gradient color
Explain of SQL optimization
Compile oglpg-9th-edition source code with clion
92. (cesium chapter) cesium building layering
Chapter 17 process memory
Xcode abnormal pictures cause IPA packet size problems
LVGL 8.2 text shadow
Programmers exposed that they took private jobs: they took more than 30 orders in 10 months, with a net income of 400000
随机推荐
MySQL的存储过程练习题
LVLG 8.2 circular scrolling animation of a label
第十六章 字符串本地化和消息字典(二)
leetcode:6110. 网格图中递增路径的数目【dfs + cache】
LVGL 8.2 Sorting a List using up and down buttons
leetcode:6109. Number of people who know the secret [definition of DP]
产业互联网则具备更大的发展潜能,具备更多的行业场景
LVGL 8.2 Menu
An overview of 2D human posture estimation
LVGL 8.2 Sorting a List using up and down buttons
LVGL 8.2 LED
Nowcoder reverse linked list
Test evaluation of software testing
商业智能BI财务分析,狭义的财务分析和广义的财务分析有何不同?
[algorithm leetcode] interview question 04.03 Specific depth node linked list (Multilingual Implementation)
es6模块化
SqlServer函数,存储过程的创建和使用
Red envelope activity design in e-commerce system
Solutions aux problèmes d'utilisation de l'au ou du povo 2 dans le riz rouge k20pro MIUI 12.5
A keepalived high availability accident made me learn it again