n个人, 每m个数就杀掉一个人
其实这是一个数学问题.
我们只关注活着的那个人(我们称之为幸运儿)的序号变化:
image.png
正这不好看我们从下往上看. 如下图, 从N = 7 反推N = 8
image.png
我们可以得到, 索引(也称为活着的人数)为N时, 幸运儿的位置, 是索引N-1时的位置 + m, (此时数组长度溢出, 因此要余索引N),得到N时幸运儿的位置.
最后一次我们知道幸运儿位置一定是0, 且这次的索引是1, 因此我们从索引2开始一直推到索引N, 也就是所有人的总数n, 取此时的位置变量, 就是最终结果.
代码很简单
int lastRemaining(int n, int m){
int pos = 0;
for(int i = 2; i<=n; i++)
{
pos = (pos + m) % i;
}
return pos;
}
n个人, 每m个数就杀掉一个人 其实这是一个数学问题. 我们只关注活着的那个人(我们称之为幸运儿)的序号变化: 正...
⭐TODO: 能推出约瑟夫环问题的状态转移方程2.重做机器人的运动范围 一、剑指 Offer 62. 圆圈中最后剩...
1. 列表的定义 先进先出（FIFO） 2. 用法 类代码如下： 3. 算法运用 ① 约瑟夫环剑指offer62 ...
约瑟夫环问题 0，1，2，...，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字，求最后...
LeetCode 面试题62. 圆圈中最后剩下的数字【剑指Offer】【Easy】【Python】【数学】 问题 ...
剑指 Offer 62. 圆圈中最后剩下的数字[https://leetcode.cn/problems/yuan...
【剑指offer】Java版代码（完整版） 【剑指offer】1-10题 【剑指offer】11-20题 【剑指o...
1、题目描述 0, 1, …, n-1这n个数字(n>0)排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字...
剑指offer leetcode
优先队列PriorityQueue说白了就是一个最小堆，其中存储元素并不是按照顺序存储，但是检索是按照顺序的，re...
本文标题：剑指offer 62 约瑟夫问题
本文链接：https://www.haomeiwen.com/subject/evxaghtx.html
网友评论