【牛客网刷题(数据结构)】:环形链表的约瑟夫问题

描述
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
O(n)
示例1
好环形链表的约瑟夫问题是一个经典的问题,它的描述如下:有n个人围成一圈,从第一个人开始报数,报到m的人出圈,剩下的人继续从1开始报数,直到剩下最后一个人。现在给定n和m,求最后剩下的人的编号
这个问题可以使用环形链表来解决。具体来说,我们可以先构建一个包含n个节点的环形链表,然后从第一个节点开始遍历链表,每次遍历m个节点,将第m个节点从链表中删除。重复这个过程直到链表中只剩下一个节点为止,这个节点就是最后剩下的节点
输入:
5,2
返回值:
3
说明:
开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开
1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开
1,3,5,从5开始报数,5->1,1->2编号为1的人离开
3,5,从3开始报数,3->1,5->2编号为5的人离开
最后留下人的编号是3
示例2
输入:
1,1
复制
返回值:
1
关于环形链表的约瑟夫问题,具体思路如下:
首先创建一个环形链表,链表中每个节点代表一个人,节点编号从1开始递增。
然后从第一个节点开始报数,每报到第m个人就将该节点从链表中删除。
删除节点后,从下一个节点重新开始报数,重复上述步骤,直到只剩下一个节点为止。
下面是C++代码实现:
#include <iostream>
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};int josephus(int n, int m) {ListNode* head = new ListNode(1);ListNode* cur = head;for (int i = 2; i <= n; i++) {cur->next = new ListNode(i);cur = cur->next;}cur->next = head; // 将链表首尾相连while (cur->next != cur) { // 只剩下一个节点时结束循环for (int i = 1; i < m; i++) {cur = cur->next;}ListNode* tmp = cur->next;cur->next = tmp->next;delete tmp;}int ans = cur->val;delete cur;return ans;
}int main() {int n, m;cin >> n >> m;cout << josephus(n, m) << endl;return 0;
}
C语言代码实现
#include <stdio.h>
#include <stdlib.h>// 定义链表节点结构体
typedef struct Node {int num; // 节点编号struct Node *next; // 指向下一个节点的指针
} Node;// 创建环形链表
Node *createList(int n) {Node *head = NULL, *tail = NULL;for (int i = 1; i <= n; i++) {Node *p = (Node *)malloc(sizeof(Node));p->num = i;if (head == NULL) {head = p;} else {tail->next = p;}tail = p;}tail->next = head; // 将尾节点指向头节点,形成环形链表return head;
}// 约瑟夫问题求解
void josephus(Node *head, int m) {Node *p = head, *prev = NULL;while (p->next != p) { // 只剩下一个节点时结束循环for (int i = 1; i < m; i++) {prev = p;p = p->next;}prev->next = p->next; // 删除节点printf("%d ", p->num);free(p);p = prev->next; // 从下一个节点重新开始报数}printf("%d\n", p->num);free(p);
}int main() {int n, m;printf("请输入总人数n和报数m:");scanf("%d%d", &n, &m);Node *head = createList(n);josephus(head, m);return 0;
}
相关文章:
【牛客网刷题(数据结构)】:环形链表的约瑟夫问题
描述 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少? O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问…...
虾皮印尼买家号如何注册
虾皮(Shopee)是一个流行的电子商务平台,想要注册虾皮印尼买家号,可以按照以下步骤进行操作: 1、访问虾皮印尼站点:打开浏览器,输入虾皮印尼官网 2、点击"注册":在网站的…...
SpringBoot WebService服务端客户端使用教程
服务端: 依赖 <!-- webservice相关依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web-services</artifactId></dependency><dependency><groupId&…...
【Python 千题 —— 基础篇】字符串长度
题目描述 题目描述 获取字符串长度是编程过程中常用的操作之一。编写一个程序,输入一个字符串,然后输出字符串的长度。 输入描述 输入一个字符串。 输出描述 程序将输入的字符串的长度输出。 代码讲解 下面是本题的代码: # 描述: 输…...
AIGC - 入门向量空间模型
文章目录 向量和向量空间向量的运算什么是向量空间?向量空间的几个重要概念向量之间的距离曼哈顿距离(Manhattan Distance)欧氏距离(Euclidean Distance)切比雪夫距离(Chebyshev Distance) 向量…...
python中使用xml.dom.minidom模块读取解析xml文件
python中可以使用xml.dom.minidom模块读取解析xml文件 xml.dom.minidom模块应该是内置模块不用下载安装 对于一个xml文件来说比如这个xml文件的内容为如下 <excel version"1.0" author"huangzhihui"><table id"1"><colum id&qu…...
计算机网络第一章补充整理(计算机网络体系结构)
前言:以下整理内容,参考《计算机网络自顶向下》和哈工大的计网慕课 目录 计算机网络的体系结构的一些概念为什么采用分层结构?分层结构的优点分层结构的缺点 开放系统互连(OSI)参考模型物理层功能数据链路层功能网络层…...
2023_Spark_实验十七:导入招聘大数据(项目)
一、爬虫爬取的招聘网站数据 二、在MySQL中创建空表 SET FOREIGN_KEY_CHECKS0;-- ---------------------------- -- Table structure for jd_jobs -- ---------------------------- DROP TABLE IF EXISTS jd_jobs; CREATE TABLE jd_jobs (job_name text,job_date text,minSale…...
小程序无感刷新
下载wechat-http依赖 npm install wechat-http封装请求拦截器和相应拦截器,借助refreshToken实现无感刷新 // 导入 http 模块 import http from wechat-http // 基础路径,同时需添加合法请求域名 http.baseURL https://live-api.itheima.net // 配置请…...
Unity C#随笔:简述String和StringBuilder的区别
1.、String: 不可变性(Immutability): String对象一旦被创建,就不能被修改。每次对String对象进行操作时,实际上是创建了一个新的String对象,然后对象的引用重新指向这个新的对象。性能&#x…...
图论相关算法
一、迪杰斯特拉(Dijkstra)算法 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。 1.核心思想 (1)每次选中一个点,这个点满足两个条件: 未被选过距离最短 (2…...
Python人工智能需要学什么
Python语言在人工智能开发领域有非常广泛的应用,随着人工智能平台的落地应用,未来采用Python语言来开发行业智能产品会是比较常见的选择。 然而进行人工智能开发仅凭Python语言是不够的,学习Python人工智能需要学习哪些知识呢? 一、Python…...
Java 获取请求真实IP
获取IP地址为 127.0.0.1, 或者内网地址 Nginx配置, 只有 proxy_pass 时只能获取到 127.0.0.1 location / {proxy_pass http://127.0.0.1:8080; }修改为 location / {#保留代理之前的host 包含客户端真实的域名和端口号proxy_set_header Host $host; #保留代理之前的真实客…...
Python突破浏览器TLS/JA3 指纹
JA3 是一种创建 SSL/TLS 客户端指纹的方法,一般一个网站的证书是不变的,所以浏览器指纹也是稳定的,能区分不同的客户端。 requests库 Python requests库请求一个带JA3指纹网站的结果: import requestsheaders {authority: tls…...
web安全之XSS攻击
什么是XSS攻击 XSS(Cross-Site Scripting)又称跨站脚本,XSS的重点不在于跨站点,而是在于脚本的执行。XSS是一种经常出现在 Web 应用程序中的计算机安全漏洞,是由于 Web 应用程序对用户的输入过滤不足而产生的。 常见…...
【技巧】如何设置Excel表只输入固定内容?
如果你需要在Excel表格中输入固定的内容,可以设置“限制录入内容”,这样就只能输入设置好的内容,避免不小心输入错误信息。下面来看看如何设置吧。 首先,打开Excel表格后,选中需要输入固定内容的表格区域。 比如图片…...
手机抬手亮屏解锁,用到了哪些硬件?
随着时代发展,智能手机以丰富的功能及便利性,成为了人们必不可少的物品,其中人脸解锁功能是非常有用的功能,广受年轻人的喜爱,那么你知道她是如何实现吗?今天凡小亿带你们探索! 手机抬手亮屏解锁…...
AI大模型高速发展,Web3还远吗?
在过去的几年里,人工智能(AI)和Web3技术都经历了令人瞩目的发展。AI大模型,特别是像GPT-3、GPT-4等这样的巨型语言模型,已经成为AI领域的明星,而Web3则代表了下一代互联网的愿景,具有去中心化和…...
CSS 滚动驱动动画 animation-range
animation-range 语法 normallength-percentagetimeline-range-name 具名时间线范围 named timeline rangecovercontainentry 和 entry-crossingexit 和 exit-crossing 兼容性 animation-range 这个属性可同时对 scroll progress timeline 和 view progress timeline 这两种不…...
快速学习MyBatisPlus
文章目录 前言一、条件构造器和常用接口1.wapper介绍2.QueryWrapper(1)组装查询条件(2)组装排序查询(3)组装删除查询(4)条件优先级(5)组装select子句…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
Redis数据倾斜问题解决
Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中,部分节点存储的数据量或访问量远高于其他节点,导致这些节点负载过高,影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...
sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!
简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求,并检查收到的响应。它以以下模式之一…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
鸿蒙(HarmonyOS5)实现跳一跳小游戏
下面我将介绍如何使用鸿蒙的ArkUI框架,实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...
Linux操作系统共享Windows操作系统的文件
目录 一、共享文件 二、挂载 一、共享文件 点击虚拟机选项-设置 点击选项,设置文件夹共享为总是启用,点击添加,可添加需要共享的文件夹 查询是否共享成功 ls /mnt/hgfs 如果显示Download(这是我共享的文件夹)&…...
P10909 [蓝桥杯 2024 国 B] 立定跳远
# P10909 [蓝桥杯 2024 国 B] 立定跳远 ## 题目描述 在运动会上,小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时࿰…...
基于谷歌ADK的 智能产品推荐系统(2): 模块功能详解
在我的上一篇博客:基于谷歌ADK的 智能产品推荐系统(1): 功能简介-CSDN博客 中我们介绍了个性化购物 Agent 项目,该项目展示了一个强大的框架,旨在模拟和实现在线购物环境中的智能导购。它不仅仅是一个简单的聊天机器人,更是一个集…...
