【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)

简介: 【经典算法】LCR187:破冰游戏(约瑟夫问题,Java/C/Python3/JavaScript实现含注释说明,Easy)

题目

社团共有 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) {
    List<Integer> 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.h>
int 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 = 0
    while num > 1:
        index = (index + target - 1) % num # 减1因为从0开始计数,取余是因为是圆桌
        members.pop(index)
        num -= 1
    return 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; // num=1时最后剩下的成员编号
    for (int i = 2; i <= num; i++) {
        res = (res + target) % i;
    }
    return res;
}

说明:

基于递归关系迭代地求解最后剩下成员的编号,避免了昂贵的数组删除操作。

C语言版本
#include <stdio.h>
int 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  # num=1时最后剩下的成员编号
    for i in range(2, num + 1):
        res = (res + target) % i
    return res

说明:

利用递归关系进行迭代求解

复杂度分析

  • 时间复杂度:O(num),只需迭代 num-1 次
  • 空间复杂度:O(1),仅需常数个变量存储中间结果

方式三:递归

思路

约瑟夫问题还可以采用递归的思路来解决。对于 num 个人的情况,如果我们知道了 num-1 个人的情况下的胜利者的索引,那么我们可以通过递归关系得到 num 个人时的最终胜利者。

递归关系如下:

f(n, m) = (f(n-1, m) + m) % n

其中 f(1, m) = 0,f(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.h>
int 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 0
    else:
        # 递归计算 num-1 个成员时的胜利者的索引,并应用递归关系
        return (last_remaining_rec(num - 1, target) + target) % num
def 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-141 Linked List Cycle Easy 使用快慢指针判断链表是否有环
LeetCode-142 Linked List Cycle II Medium 寻找链表中环的入口点
LeetCode-202 Happy Number Easy 利用快慢指针寻找循环
LeetCode-287 Find the Duplicate Number Medium 数组可以视为链表,寻找环的入口
LeetCode-206 Reverse Linked List Easy 链表的基本操作
LeetCode-234 Palindrome Linked List Easy 链表操作和快慢指针
LeetCode-160 Intersection of Two Linked Lists Easy 寻找两个链表的交点
相关文章
|
1月前
|
前端开发 JavaScript Java
计算机Java项目|java游戏账号交易系统
计算机Java项目|java游戏账号交易系统
计算机Java项目|java游戏账号交易系统
|
14天前
|
Java 索引
Java实现扑克牌游戏 | 随机发牌 ( 过程拆分详解+完整代码 )
Java实现扑克牌游戏 | 随机发牌 ( 过程拆分详解+完整代码 )
|
20天前
|
JavaScript 前端开发 Java
java 执行 javascript 代码
java 执行 javascript 代码
18 6
|
17天前
|
Java 编译器
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
Java健壮性 Java可移植性 JDK, JRE, JVM三者关系 Java的加载与执行原理 javac编译与JAVA_HOME环境变量介绍 Java中的注释与缩进 main方法的args参数
19 1
|
1月前
|
前端开发 JavaScript Java
计算机Java项目|游戏美术外包管理信息系统
计算机Java项目|游戏美术外包管理信息系统
|
1月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
20天前
|
Java C# 容器
第一行Java代码的注释和相关解读
第一行Java代码的注释和相关解读
10 0
|
21天前
|
Java
使用java编写猜数字游戏
使用java编写猜数字游戏
12 0
|
26天前
|
数据采集 前端开发 JavaScript
Python爬虫技术:动态JavaScript加载音频的解析
Python爬虫技术:动态JavaScript加载音频的解析
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏