leetcode 圆圈中最后剩下的数字（思路）
leetcode 面试题62. 圆圈中最后剩下的数字 2020/3/30 感觉这个题的思路很重要，保存以备今后参考！
题目：0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如：0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例：
输入: n = 5, m = 3
输出: 3
输入: n = 10, m = 17
输出: 2
【leetcode 圆圈中最后剩下的数字（思路）】解题思路：
阅前提示（全文最重要的点）：
只关心最终活着那个人的序号变化
1 约瑟夫问题
这个问题实际上是约瑟夫问题，这个问题描述是:
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
2 问题转换
既然约塞夫问题就是用人来举例的，那我们也给每个人一个编号（索引值），每个人用字母代替
下面这个例子是N=8 m=3的例子:
我们定义F(n,m)表示最后剩下那个人的索引号，因此我们只关心最后剩下来这个人的索引号的变化情况即可
文章图片
从8个人开始，每次杀掉一个人，去掉被杀的人，然后把杀掉那个人之后的第一个人作为开头重新编号
3 最终活着的人编号的反推
如何才能将N = 7 的排列变回到N = 8 呢？
我们先把被杀掉的C补充回来，然后右移m个人，发现溢出了，再把溢出的补充在最前面
文章图片
推出递推公式： f(8,3)=[f(7,3)+3]%8
进行推广泛化 f(n,m)=[f(n?1,m)+m]%n
python程序：
def f(n, m):
if n == 0:
return 0
return (f(n-1,m) + m) % n
class Solution(object):
def lastRemaining(self, n, m):
return f(n,m)
推荐阅读
- 热闹中的孤独
- Shell-Bash变量与运算符
- JS中的各种宽高度定义及其应用
- 2021-02-17|2021-02-17 小儿按摩膻中穴-舒缓咳嗽
- 深入理解Go之generate
- 异地恋中，逐渐适应一个人到底意味着什么（）
- 我眼中的佛系经纪人
- 《魔法科高中的劣等生》第26卷（Invasion篇）发售
- “成长”读书社群招募
- 2020-04-07vue中Axios的封装和API接口的管理