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

目录

  • 题目
  • 思路及实现
    • 方式一:迭代模拟(用链表模拟这个游戏)
      • 思路
      • 代码实现
        • 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) {
    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-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寻找两个链表的交点

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/528009.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言 函数——函数的定义、调用和参数传递

目录 模块化编程&#xff08;Modular Programming&#xff09; 函数的分类 函数的定义 使用函数编程的好处 函数调用的基本方式 函数调用时的数据传递 函数调用的过程 main函数的特殊性 大话三国 分而治之 如果将main&#xff08;&#xff09;函数比作诸葛亮&#xff…

并行超算云计算使用步骤完整流程详情

本文目录 一、将项目传入并运云。二、创建项目的虚拟环境三、编辑run.sh脚本四、提交作业五、查看作业输出六、查看提交的作业号七、结束作业 一、将项目传入并运云。 二、创建项目的虚拟环境 打开终端 使用conda创建&#xff1a;conda create -n 环境名 python3.8查看conda下…

消息队列MQ的介绍和docker安装MQ

一、什么是mq? MQ全称 Message Queue&#xff08;消息队列&#xff09;&#xff0c;是在消息的传输过程中保存消息的容器。多用于分布式系统之间进行通信&#xff0c;解耦。 二、常见的mq产品 RabbitMQ、RocketMQ、ActiveMQ、Kafka、ZeroMQ、MetaMq RabbitMQ: One broker …

LINUX 下IPTABLES配置详解

-t<表>&#xff1a;指定要操纵的表&#xff1b; -A&#xff1a;向规则链中添加条目&#xff1b; -D&#xff1a;从规则链中删除条目&#xff1b; -i&#xff1a;向规则链中插入条目&#xff1b; -R&#xff1a;替换规则链中的条目&#xff1b; -L&#xff1a;显示规则链中…

【算法详解】二分查找

1. 二分查找算法介绍 「二分查找算法&#xff08;Binary Search Algorithm&#xff09;」&#xff1a;也叫做 「折半查找算法」、「对数查找算法」。是一种在有序数组中查找某一特定元素的搜索算法。 基本算法思想&#xff1a;先确定待查找元素所在的区间范围&#xff0c;在逐步…

界面组件DevExpress WinForms v23.2 - 功能区、富文本编辑器功能升级

DevExpress WinForms拥有180组件和UI库&#xff0c;能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForms能完美构建流畅、美观且易于使用的应用程序&#xff0c;无论是Office风格的界面&#xff0c;还是分析处理大批量的业务数据&#xff0c;它都能轻松胜…

软考 系统架构设计师系列知识点之云原生架构设计理论与实践(16)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之云原生架构设计理论与实践&#xff08;15&#xff09; 所属章节&#xff1a; 第14章. 云原生架构设计理论与实践 第3节 云原生架构相关技术 14.3.3 无服务器技术 1. 技术特点 2. 技术关注点 &#xff08;1&#xff…

四川一体化污水处理设备厂家如何挑选

如果您想寻找一家可靠的四川地区的污水处理设备厂家&#xff0c;以下是一些挑选的关键要素可以考虑&#xff1a; 1. 信誉和口碑&#xff1a;了解该厂家在业界的声誉和客户的评价&#xff0c;可以通过查阅相关的评论和建议&#xff0c;或者咨询其他业内人士来了解。 2. 技术实力…

数据生成 | Matlab实现基于SNN浅层神经网络的数据生成

数据生成 | Matlab实现基于SNN浅层神经网络的数据生成 目录 数据生成 | Matlab实现基于SNN浅层神经网络的数据生成生成效果基本描述模型描述程序设计参考资料 生成效果 基本描述 1.Matlab实现基于SNN浅层神经网络的数据生成&#xff0c;运行环境Matlab2021b及以上&#xff1b; …

【接口自动化】参数化替换

在做接口测试时&#xff0c;除了测单个接口&#xff0c;还需要进行业务链路间的接口测试 比如[注册-登陆]需要token鉴权的业务流 当我们用使用postman/jmeter等工具时&#xff0c;将注册接口的一些响应信息提取出来&#xff0c;放到登陆接口的请求中&#xff0c;来完成某个业务…

紫叶写作能用吗 #微信#知识分享

紫叶写作是一款非常好用、靠谱的论文写作工具&#xff0c;它旨在帮助用户快速高效地完成论文写作任务&#xff0c;并提供查重降重的功能。它不仅操作简单方便&#xff0c;而且功能强大&#xff0c;能够有效提高论文写作的效率和质量。 首先&#xff0c;紫叶写作提供了丰富的模板…

CKA 基础操作教程(五)

Kubernetes Ingress 理论学习 Ingress 提供从集群外部到集群内服务的 HTTP 和 HTTPS 路由。 流量路由由 Ingress 资源所定义的规则来控制。 Ingress 资源示例&#xff1a; apiVersion: networking.k8s.io/v1 # 指定 Kubernetes 中使用的 API 版本 kind: Ingress # 指定对象…

matlab使用教程(38)—傅里叶变换

1基本概念 傅里叶变换是一个数学公式&#xff0c;用于将按时间或空间采样的信号变换为按时序或空间频率采样的相同信号。 在信号处理中&#xff0c;傅里叶变换可以揭示信号的重要特征&#xff08;即其频率分量&#xff09;。 对于包含 n 个均匀采样点的向量 x &#xff0c;其…

为说阿拉伯语的国家进行游戏本地化

阿拉伯语是由超过4亿人使用的语言&#xff0c;并且是二十多个国家的官方语言。进入这些国家的市场并非易事——虽然他们共享一种通用语言&#xff0c;但每个国家都有自己独特的文化&#xff0c;有自己的禁忌和对审查的处理方式。这就是为什么视频游戏公司长期以来都远离阿拉伯语…

mac-m1pro芯片编译java项目慢且发热严重问题

目录 一、背景二、排查三、解决四、效果以及结果展示五、总结 一、背景 使用idea编译项目等操作&#xff0c;经常性发热严重&#xff0c;并且时间慢。直到昨天编译一个项目用时30分钟&#xff0c;电脑温度很高&#xff0c;并且有烧灼的味道&#xff0c;于是有了此篇文章。 二、…

Linux应用开发(3):Linux时间操作(time、mktime、localtime等)

1. 简述 在Linux系统中&#xff0c;时间操作函数是编程中经常使用的一部分&#xff0c;它们允许程序获取和设置系统时间&#xff0c;以及对时间进行各种处理。以下是一些常用的时间操作函数的详细介绍。 2. 时间操作 &#xff08;1&#xff09;time(): 获取1970年1月1日以来的…

TalkingData——Unity应用开发中集成统计分析工具

第一步:帐号注册 官方网站:TalkingData-移动.数据.价值 第二步:创建应用查看 appid 可以进入网站注册,注册好以后就可以创建应用 创建好应用后,点击 应用管理-》基本信息就可以查看自己的 AppID 第三步:申请对应平台的sdk 接下来就是申请sdk 这里是申请sdk的网站…

Unity MySql安装部署与Unity连接 上篇

1.前言 最近项目用到MySql&#xff0c;记录一下安装部署过程。 数据量过大或者需要管理用户数据的时候用mysql的话数据结构比较清晰明了&#xff0c;便于管理。 2.安装MySql Unity版本&#xff1a;2019.4.16 MySql版本&#xff1a;8.2.0 下载地址&#xff1a;MySql 下载…

使用Nodejs + express连接数据库mongodb

文章目录 先创建一个js文档安装 MongoDB 驱动程序&#xff1a;引入 MongoDB 模块&#xff1a;设置数据库连接&#xff1a;新建一个表试试执行数据库操作&#xff1a;关闭数据库连接&#xff1a; 前面需要准备的内容可看前面的文章&#xff1a; Express框架搭建项目 node.js 简单…

数字化智慧养老:引领老年人融入科技时代新生活

hello宝子们...我们是艾斯视觉擅长ui设计和前端开发10年经验&#xff01;希望我的分享能帮助到您&#xff01;如需帮助可以评论关注私信我们一起探讨&#xff01;致敬感谢感恩&#xff01; 人类社会已经步入了一个全新的数字时代。在这个时代&#xff0c;互联网、大数据、人工智…