关于学校网站建设,苏州知名网站建设公司,广州百度seo排名优化,网站名称注意事项题目
0,1,2…,n-1这n个数字排成一个圆圈#xff0c;从数字0开始#xff0c;每次从这圆圈你删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如#xff0c;0、1、2、3、4这5个数字组成一个圆圈#xff0c;从数字0开始每次删除第3个数字#xff0c;则删除的前4个数字…题目
0,1,2…,n-1这n个数字排成一个圆圈从数字0开始每次从这圆圈你删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如0、1、2、3、4这5个数字组成一个圆圈从数字0开始每次删除第3个数字则删除的前4个数字依次2、0、4、1因此最后剩下的数字是3。 本题就是有名的约瑟夫Josephuse环问题。
分析
两种解题方法
用环形链表模拟圆圈的经典解法分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字
放码
一
用环形链表模拟圆圈的经典解法
public int lastRemaining(int n, int m) {if(n 1 || m 1) {throw new IllegalArgumentException();}LinkedListInteger list new LinkedList();for(int i 0; i n; i) {list.add(i);}int count 0, index 0;while(list.size() 1) {count;if(count m) {list.remove(index);count 0;}else {index;}if(index list.size()) {index 0;}}return list.get(0);
}二
分析每次被删除的数字的规律并直接计算出圆圈中最后剩下的数字
首先我们定义一个关于 n 和 m 的方程f(n,m)表示每次在 n 个数字 01 … n-1中每次删除第 m 个数字最后剩下的数字。
在这 n个数字中第一个被删除的数字是(m-1)%n。为了简单起见我们把(m- 1)%n 记为 k那么删除k之后剩下的 n-1 个数字为 01… k-1k1… n-1并且下一次删除从数字 k1 开始计数。相当于在剩下的序列中 k1 排在最前面从而形成 k1… n- 101… k-1 。
该序列最后剩下的数字也应该是关于 n 和 m 的函数。由于这个序列的规律和前面最初的序列不一样最初的序列是从 0 开始的连续序列因此该函数不同于前面的函数记为 f’(n-1,m)。
最初序列最后剩下的数字 f(n, m一定是删除一个数字之后的序列最后剩下的数字即 f(n, m)f(n-1, m。
接下来我们把剩下的这 n-1 个数字的序列 k-1 …n-101… k-1 做一个映射映射的结果是形成一个从 0 到 n-2 的序列
last index-indexk10k21……n-1n-k-20n-k-11n-k……k-1n-2
我们把映射定义为p则p(x)(x-k-1)%n if p(x)0, then p(x)n。
它表示如果映射前的数字是x那么映射后的数字是(x-k-1)%n。该映射的逆映射是p⁻¹(x)(xk1)%n。
由于映射之后的序列和最初的序列具有同样的形式即都是从0开始的连续序列因此仍然可以用函数f来表示记为f(n-1, m)。根据我们的映射规则映射之前的序列中最后剩下的数字f(n-1, m)p⁻¹[f(n-1, m)][f(n - 1, m) k 1] % n,把k (m - 1) % n代入得到f(n, m)f(n-1, m)[f(n-1, m) m] % n。
经过上面复杂的分析我们终于找到了一个递归公式。要得到n个数字的序列中最后剩下的数字只需要得到n-1个数字的序列中最后剩下的数字并以此类推。当n1时也就是序列中开始只有一个数字0那么很显然最后剩下的数字就是0。我们把这种关系表示为: public int lastRemaining2(int n, int m) {if(n 1 || m 1) {throw new IllegalArgumentException();}return n 1 ? 0 : (lastRemaining2(n - 1, m) m) % n;
}三
针对这个题目先说说难点
数字组成是环形的结构当数到最后个数字时还不是需要删除的第 m 个数需要回至数组的首位继续 每次重新数的位置都是上次删除数字的下一位。 针对第一个难点可以考虑取模
针对第二个难点可以考虑将删除数字下一位作为下次重新数的起点剩余数字依次排列。注意数字组成是环状的
考虑先模拟然后再进行逆推
为体现闭环这里将数组进行复制。注意 未得到最后 1 位数时除第 1 轮开始 每一轮都是以上一轮删除数字下一位作为起点重新数需要删除的第 m 个数
这就是模拟之后得到的结果。
现在我们来进行逆推 最终确定的 1 个数字这个数字对应的索引一定是 0逆推这个最终数字在每一轮中所处的索引位置那么假设n 表示数组元素个数m 表示要删除的第 m 个数取示例 1n 5 m 3
n 1 时索引0n 2 时索引(0 m) % 2 3 % 2 1n 3 时索引((0 m) % 2 3) % 3 (1 3) % 3 1n 4 时索引(((0 m) % 2 3) % 3 m) % 4 (1 3) % 4 0n 5 时索引((((0 m) % 2 3) % 3 m) % 4 m) % 5 (0 3) % 5 3 。
大致讲下前面的逆推过程找出剩余元素在前面每一轮所处的位置
当剩下 1 个数字的时候这个数字3的索引为 0往前逆推当剩下 2 个数字的时候在上一轮元素索引的基础上要补上 m 个位置然后对数组元素个数取模得到这一轮该元素所在的位置代入 nm可得数字3索引为 1当剩下 3 个数字时同样补上 m 个位置然后对数组元素个数取模这个时候数组元素个数为 3代入 mn得数字3索引为 1…
对上面的逆推过程进行总结从最后 1 轮往前逆推时前面一轮的元素所处的位置为当前索引 m % 前面一轮元素个数。
那么根据这个公式用代码进行实现。
class Solution:def lastRemaining(self, n: int, m: int) - int:ans 0# 最后 1 位为最终保留数字# 往前逆推从元素个数为 2 开始for i in range(2, n 1):# 逆推公式ans (ans m) % ireturn ans测试
import org.junit.Assert;
import org.junit.Test;public class LastRemainingTest {Testpublic void test() {LastRemaining lr new LastRemaining();Assert.assertEquals(3, lr.lastRemaining(5, 3));Assert.assertEquals(2, lr.lastRemaining(10, 17));Assert.assertEquals(3, lr.lastRemaining2(5, 3));Assert.assertEquals(2, lr.lastRemaining2(10, 17));}}参考 LeetCode 面试题62. 圆圈中最后剩下的数字 LaTex数学公式生成
