怎么自己创建网站,个人网站的建立怎么做,wordpress小程序音频插件,安徽外经建设集团有限公司网站目录 题目思路及实现方式一#xff1a;迭代模拟#xff08;用链表模拟这个游戏#xff09;思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二#xff1a;数学迭代思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式三#xff1a;递归思路代码实现Java版… 目录 题目思路及实现方式一迭代模拟用链表模拟这个游戏思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式二数学迭代思路代码实现Java版本C语言版本Python3版本 复杂度分析 方式三递归思路代码实现Java版本C语言版本Python3版本 复杂度分析 总结相似题目 标签递归 | 数学
题目
社团共有 num 位成员参与破冰游戏编号为 0 ~ num-1。成员们按照编号顺序围绕圆桌而坐。社长抽取一个数字 target
从 0 号成员起开始计数排在第 target 位的成员离开圆桌且成员离开后从下一个成员开始计数。
请返回游戏结束时最后一位成员的编号。示例 1输入num 7, target 4
输出1
示例 2输入num 12, target 5
输出0
提示1 num 10^5
1 target 10^6原题LeetCode LCR187
思路及实现
约瑟夫问题 这个问题是以弗拉维奥·约瑟夫命名的他是1世纪的一名犹太历史学家。他在自己的日记中写道他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘最终决定自杀并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人他们将向罗马军队投降不再自杀。约瑟夫斯把他的存活归因于运气或天意他不知道是哪一个。 —— 【约瑟夫问题】 详见约瑟夫问题
方式一迭代模拟用链表模拟这个游戏
思路
这是经典的约瑟夫问题Josephus Problem。我们可以模拟这个过程使用一个列表来存储成员编号每次计数到 target 时将当前成员移除列表然后计数到下一个成员。重复此过程直到列表里只剩下一个成员返回该成员的编号。
代码实现
Java版本
public int lastRemaining(int num, int target) {ListInteger members new ArrayList();for (int i 0; i num; i) {members.add(i);}int index 0;while (num 1) {index (index target - 1) % num; // 减1因为从0开始计数取余是因为是圆桌members.remove(index);num--;}return members.get(0);
} 说明 迭代地模拟成员被移出的过程index 表示每次需要移除成员的位置。 C语言版本
#include stdio.h
#include stdlib.hint lastRemaining(int num, int target) {// 创建一个动态数组来模拟成员围坐一圈的情况int *members (int *)malloc(num * sizeof(int));// 初始化成员编号for (int i 0; i num; i) {members[i] i;}int current 0; // 当前计数开始的位置int remaining num; // 剩余成员数while (remaining 1) {// 计算要移除成员的索引位置int removeIndex (current target - 1) % remaining;// 从数组中移除成员for (int j removeIndex; j remaining - 1; j) {members[j] members[j 1];}// 更新当前计数开始的位置current removeIndex % (remaining - 1);// 更新剩余成员数remaining--;}// 记录最后剩下的成员编号int lastMember members[0];// 释放动态数组所占用的内存free(members);return lastMember;
}// 测试程序
int main() {int num 7, target 4;printf(The last remaining member is: %d\n, lastRemaining(num, target));return 0;
} 说明 代码实现了迭代模拟方式来解决约瑟夫环问题。首先初始化成员编号然后根据游戏规则逐一模拟计数与成员被移除的过程。注意由于成员编号是从0开始所以移除成员的索引位置需要进行 target - 1 处理。每次有成员移除后都需要更新计数的起始位置以及剩余的成员数量。最终剩下的成员的编号即为所求。 此外代码还处理了动态分配内存的释放以避免内存泄漏问题。 Python3版本
def last_remaining(num, target):members list(range(num))index 0while num 1:index (index target - 1) % num # 减1因为从0开始计数取余是因为是圆桌members.pop(index)num - 1return members[0]说明 Python版本的实现思路与Java版本相同使用列表和迭代的方式模拟约瑟夫环的过程。 复杂度分析
时间复杂度O(num^2)因为每次删除操作都需要 O(num) 的时间空间复杂度O(num)存储成员编号需要的空间
方式二数学迭代
思路
在约瑟夫问题中可以找到递归的关系f(n, m) (f(n-1, m) m) % n其中f(n, m)表示第n轮中以m开始计数的最后胜利者的位置。
代码实现
Java版本
public int lastRemaining(int num, int target) {int res 0; // num1时最后剩下的成员编号for (int i 2; i num; i) {res (res target) % i;}return res;
}说明 基于递归关系迭代地求解最后剩下成员的编号避免了昂贵的数组删除操作。 C语言版本
#include stdio.hint lastRemaining(int num, int target) {int res 0; // 最开始编号为0的成员肯定会留下// 从第二位成员开始迭代直到num位成员for(int i 2; i num; i) {res (res target) % i;}return res;
}int main() {int num 7, target 4;printf(The last remaining member is: %d\n, lastRemaining(num, target));return 0;
} 说明 从1计数到 num代表每一轮的成员数。在每轮计算中 res 的值为上一轮中剩下成员的位置将其与 target 相加后对当前轮的成员数取余数得到新一轮中剩余成员的位置。 最后返回 res即为最后剩下成员的编号。 Python3版本
def last_remaining(num, target):res 0 # num1时最后剩下的成员编号for i in range(2, num 1):res (res target) % ireturn res说明 利用递归关系进行迭代求解 复杂度分析
时间复杂度O(num)只需迭代 num-1 次空间复杂度O(1)仅需常数个变量存储中间结果
方式三递归
思路
约瑟夫问题还可以采用递归的思路来解决。对于 num 个人的情况如果我们知道了 num-1 个人的情况下的胜利者的索引那么我们可以通过递归关系得到 num 个人时的最终胜利者。 递归关系如下 f(n, m) (f(n-1, m) m) % n 其中 f(1, m) 0f(n, m) 表示总数为 n计数为 m的情况下最后胜利者的索引。
代码实现
Java版本
public int lastRemaining(int num, int target) {return lastRemainingRec(num, target);
}private int lastRemainingRec(int num, int target) {if (num 1) {// 只有一个成员时他肯定是胜利者return 0;} else {// 递归计算 num-1 个成员时的胜利者的索引并应用递归关系return (lastRemainingRec(num - 1, target) target) % num;}
} 说明递归在每次调用中计算 num-1 的情况并将结果使用到 num 个成员的情况。 C语言版本
#include stdio.hint lastRemainingRec(int num, int target) {if (num 1) {// 只有一个成员时他肯定是胜利者return 0;} else {// 递归计算 num-1 个成员时的胜利者的索引并应用递归关系return (lastRemainingRec(num - 1, target) target) % num;}
}int lastRemaining(int num, int target) {return lastRemainingRec(num, target);
}int main() {int num 7, target 4;printf(The last remaining member is: %d\n, lastRemaining(num, target));return 0;
} 说明采用递归方式递归的边界情况是只剩一个成员时其编号为0。非边界情况使用递归函数计算。 Python3版本
def last_remaining_rec(num, target):if num 1:# 只有一个成员时他肯定是胜利者return 0else:# 递归计算 num-1 个成员时的胜利者的索引并应用递归关系return (last_remaining_rec(num - 1, target) target) % numdef last_remaining(num, target):return last_remaining_rec(num, target)# 示例
print(last_remaining(7, 4)) # 输出: 1
print(last_remaining(12, 5)) # 输出: 0 说明Python 版本的实现中同样使用递归直观地展示了解法的递归逻辑结构。 复杂度分析
时间复杂度O(num)因为递归函数将被调用 num 次。空间复杂度O(num)递归需要使用栈空间其大小取决于递归的深度最大为 num。
总结
方式描述优点缺点时间复杂度空间复杂度迭代模拟直接根据规则模拟整个游戏过程依次淘汰成员直观和易理解当成员数目较大时效率较低O(num^2)O(num)数学迭代通过数学公式递推最终结果逐步缩小问题规模时间效率高不需要昂贵的删除操作需要数学知识公式推导可能不够直观O(num)O(1)递归通过递归函数从基础情况逐步返回最终答案代码简洁易编写栈空间开销大可能会栈溢出O(num)O(num)迭代改进递归方法的迭代版本避免了栈溢出的问题避免了递归引起的栈溢出相对于直接递归可能理解起来稍微复杂O(num)O(1)
相似题目
题号名称难度相似点LeetCode-141Linked List CycleEasy使用快慢指针判断链表是否有环LeetCode-142Linked List Cycle IIMedium寻找链表中环的入口点LeetCode-202Happy NumberEasy利用快慢指针寻找循环LeetCode-287Find the Duplicate NumberMedium数组可以视为链表寻找环的入口LeetCode-206Reverse Linked ListEasy链表的基本操作LeetCode-234Palindrome Linked ListEasy链表操作和快慢指针LeetCode-160Intersection of Two Linked ListsEasy寻找两个链表的交点
