当前位置: 首页 > news >正文

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

在这里插入图片描述
描述
编号为 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 的人开始报数&#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后&#xff0c;只剩下一个人&#xff0c;问最后留下的这个人编号是多少&#xff1f; O(n) 示例1 好环形链表的约瑟夫问题是一个经典的问…...

虾皮印尼买家号如何注册

虾皮&#xff08;Shopee&#xff09;是一个流行的电子商务平台&#xff0c;想要注册虾皮印尼买家号&#xff0c;可以按照以下步骤进行操作&#xff1a; 1、访问虾皮印尼站点&#xff1a;打开浏览器&#xff0c;输入虾皮印尼官网 2、点击"注册"&#xff1a;在网站的…...

SpringBoot WebService服务端客户端使用教程

服务端&#xff1a; 依赖 <!-- webservice相关依赖--><dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web-services</artifactId></dependency><dependency><groupId&…...

【Python 千题 —— 基础篇】字符串长度

题目描述 题目描述 获取字符串长度是编程过程中常用的操作之一。编写一个程序&#xff0c;输入一个字符串&#xff0c;然后输出字符串的长度。 输入描述 输入一个字符串。 输出描述 程序将输入的字符串的长度输出。 代码讲解 下面是本题的代码&#xff1a; # 描述: 输…...

AIGC - 入门向量空间模型

文章目录 向量和向量空间向量的运算什么是向量空间&#xff1f;向量空间的几个重要概念向量之间的距离曼哈顿距离&#xff08;Manhattan Distance&#xff09;欧氏距离&#xff08;Euclidean Distance&#xff09;切比雪夫距离&#xff08;Chebyshev Distance&#xff09; 向量…...

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…...

计算机网络第一章补充整理(计算机网络体系结构)

前言&#xff1a;以下整理内容&#xff0c;参考《计算机网络自顶向下》和哈工大的计网慕课 目录 计算机网络的体系结构的一些概念为什么采用分层结构&#xff1f;分层结构的优点分层结构的缺点 开放系统互连&#xff08;OSI&#xff09;参考模型物理层功能数据链路层功能网络层…...

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封装请求拦截器和相应拦截器&#xff0c;借助refreshToken实现无感刷新 // 导入 http 模块 import http from wechat-http // 基础路径&#xff0c;同时需添加合法请求域名 http.baseURL https://live-api.itheima.net // 配置请…...

Unity C#随笔:简述String和StringBuilder的区别

1.、String&#xff1a; 不可变性&#xff08;Immutability&#xff09;&#xff1a; String对象一旦被创建&#xff0c;就不能被修改。每次对String对象进行操作时&#xff0c;实际上是创建了一个新的String对象&#xff0c;然后对象的引用重新指向这个新的对象。性能&#x…...

图论相关算法

一、迪杰斯特拉(Dijkstra)算法 迪杰斯特拉算法使用类似广度优先搜索的方法解决了带权图的单源最短路径问题。这是一个贪心算法。 1.核心思想 &#xff08;1&#xff09;每次选中一个点&#xff0c;这个点满足两个条件&#xff1a; 未被选过距离最短 &#xff08;2&#xf…...

Python人工智能需要学什么

Python语言在人工智能开发领域有非常广泛的应用&#xff0c;随着人工智能平台的落地应用&#xff0c;未来采用Python语言来开发行业智能产品会是比较常见的选择。 然而进行人工智能开发仅凭Python语言是不够的&#xff0c;学习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 客户端指纹的方法&#xff0c;一般一个网站的证书是不变的&#xff0c;所以浏览器指纹也是稳定的&#xff0c;能区分不同的客户端。 requests库 Python requests库请求一个带JA3指纹网站的结果&#xff1a; import requestsheaders {authority: tls…...

web安全之XSS攻击

什么是XSS攻击 XSS&#xff08;Cross-Site Scripting&#xff09;又称跨站脚本&#xff0c;XSS的重点不在于跨站点&#xff0c;而是在于脚本的执行。XSS是一种经常出现在 Web 应用程序中的计算机安全漏洞&#xff0c;是由于 Web 应用程序对用户的输入过滤不足而产生的。 常见…...

【技巧】如何设置Excel表只输入固定内容?

如果你需要在Excel表格中输入固定的内容&#xff0c;可以设置“限制录入内容”&#xff0c;这样就只能输入设置好的内容&#xff0c;避免不小心输入错误信息。下面来看看如何设置吧。 首先&#xff0c;打开Excel表格后&#xff0c;选中需要输入固定内容的表格区域。 比如图片…...

手机抬手亮屏解锁,用到了哪些硬件?

随着时代发展&#xff0c;智能手机以丰富的功能及便利性&#xff0c;成为了人们必不可少的物品&#xff0c;其中人脸解锁功能是非常有用的功能&#xff0c;广受年轻人的喜爱&#xff0c;那么你知道她是如何实现吗&#xff1f;今天凡小亿带你们探索&#xff01; 手机抬手亮屏解锁…...

AI大模型高速发展,Web3还远吗?

在过去的几年里&#xff0c;人工智能&#xff08;AI&#xff09;和Web3技术都经历了令人瞩目的发展。AI大模型&#xff0c;特别是像GPT-3、GPT-4等这样的巨型语言模型&#xff0c;已经成为AI领域的明星&#xff0c;而Web3则代表了下一代互联网的愿景&#xff0c;具有去中心化和…...

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&#xff08;1&#xff09;组装查询条件&#xff08;2&#xff09;组装排序查询&#xff08;3&#xff09;组装删除查询&#xff08;4&#xff09;条件优先级&#xff08;5&#xff09;组装select子句&#xf…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...