【刷题】牛客网 NC132 环形链表的约瑟夫问题

在这里插入图片描述

NC132 环形链表的约瑟夫问题

  • 题目描述
  • 思路一(链表直通版)
  • 思路二(数组巧解版)
  • 思路三(变态秒杀版)
  • Thanks♪(・ω・)ノ谢谢阅读
  • 下一篇文章见!!!

题目描述

在这里插入图片描述
根据描述,该题思路类似于报数,第一想法就是构建环形链表。

思路一(链表直通版)

  1. 构建环形链表,赋予对应序号
  2. 进行约瑟夫问题
  3. 报到对应数,删除节点
  4. 一直到只剩一个节点。
typedef struct listnode{
    int val ;
    struct listnode* next;
} Listnode;

Listnode* buynode(int n ){
	//开辟空间
    Listnode* node = (Listnode*)malloc(sizeof(Listnode));
    //序号赋值
    node->val = n;
    //next 指针赋值
    node->next = NULL;
    //返回节点
    return node;
}
 Listnode* createlist(int n){
    //序号
    int i = 1;
    //创建头尾
    Listnode* phead ,*ptail;
    //先创建第一个节点
    phead = ptail = buynode(i++);
    //循环构建链表
    while(i<=n){
        ptail->next = buynode(i++);
        ptail = ptail->next;
    }
	//将头尾相连,构成循环链表
    ptail->next = phead;
    //返回头节点
    return phead;

 }
int ysf(int n, int m ) {
    // 创建环形链表
    Listnode * head = createlist(n);

    //约瑟夫问题
    //计数
    int count = 1 ;
    //定义 前指针 当前指针
    Listnode* cur ,*prev;
    cur = head;
    prev = NULL;
    while(cur->next != cur){
    	//报到指定数 删除节点
        if(count == m){
        	//前节点 的next指向 当前节点的下一个节点即可删除
            prev->next = cur->next;
            cur = cur->next;
            //报数重置
            count = 1;

        }else{
        	//没有报到指定数 则向后移动。
            prev = cur;
            cur = cur->next;
            count++;
        }
    }
   	//返回序号
    return cur->val;
}

来看运行效果:
在这里插入图片描述
运行很顺利

思路二(数组巧解版)

链表的实现虽然简洁,但是遇到较大数据时难免会开辟较大内存空间,所以我们可以使用数组模拟循环链表的过程。

  1. 创建数组,并赋予对应序号值
  2. 开始遍历计数,报到m 将数组前移覆盖删除即可
  3. 一直反复进行到只剩一个元素。
#define max_num 100001
int ysf(int n, int m ) {
    //初始化数组
    int man[100001];
    for(int i = 0;i<n;i++){
        man[i] = i + 1;
    }
    //计数
    int count = 1;
    //控制下标
    int i =0;
    while(n > 1 ){
        //如果报到对应数
        if(count == m){
        //向前覆盖删除元素
            for(int j = i;j < n-1;j++){
                man[j] = man[j + 1];
            }
            //计数重置
            count = 1;
            //人数减 1
            n--;
            //注意不需要将 i++ 因为删除过程 i 已经指向了后一个元素。
        }
        else{
        //不是对应数 i++ 计数加1
            i++;
            count++;
        }
		//保证不超出 n 范围
        i %= n;

    }
    //返回对应序号
    return man[i];
}

思路三(变态秒杀版)

该思路使用数学公式,进行快速计算
F(N,M)=(F(N-1,M)+M)%N
即我们可以通过目前幸存者逆推其一开始的序号。
而根据刚才的数组思路,可以知道最后的幸存者数组下标是0,所以我们便可以开始逆推。

int ysf(int n, int m ) {
    //F(N,M)=(F(N-1,M)+M)%N
    //最后幸存者下标为 0
    int p = 0;
    //从人数为2开始逆推,直到人数为n
    for (int i = 2; i <= n; i++) {
    	//依次移动
        p = (p + m) % i;
    }
    //记得将序号加一
    return p + 1;

}

Thanks♪(・ω・)ノ谢谢阅读

下一篇文章见!!!

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

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

相关文章

【C语言】探索数据结构:单链表和双链表

目录 &#x1f4a1;链表的概念和结构 &#x1f4a1;链表的分类 &#x1f4a1;无头单向非循环链表&#xff08;单链表&#xff09;的实现 定义节点结构 单链表的尾部插入 单链表的头部插入 单链表的尾部删除 单链表的头部删除 在指定位置插入前数据 在指定位置之后插入数…

TypeScript 学习笔记(Day3)

「写在前面」 本文为 b 站黑马程序员 TypeScript 教程的学习笔记。本着自己学习、分享他人的态度&#xff0c;分享学习笔记&#xff0c;希望能对大家有所帮助。推荐先按顺序阅读往期内容&#xff1a; 1. TypeScript 学习笔记&#xff08;Day1&#xff09; 2. TypeScript 学习笔…

科技云报道:新趋势下,国产数据库或“春山可望”

科技云报道原创。 从540亿元到1286亿元——这是中国通信标准化协会大数据技术标准推进委员会针对中国数据库行业给出的一份预测报告。 报告指出&#xff0c;未来五年&#xff0c;中国数据库行业将从百亿级市场跨越成为千亿级市场。 最近两年&#xff0c;中国的数据库行业似乎…

用tar压缩一个文件夹下的所有文件,包括文件夹本身

当你使用tar命令压缩一个文件夹时&#xff0c;默认情况下会包含该文件夹本身及其下所有的文件和子目录。因此&#xff0c;之前的命令同样适用于包括文件夹本身在内的所有内容&#xff1a; tar -czvf archive_name.tar.gz directory_to_compress/ c 表示创建一个新的归档文件。…

使用Eclipse搞Android项目报错

相信现在都没什么人还会用Eclipse来开发的了。 不过安装完后&#xff0c;打开Eclipse会提示我的Jdk版本不符合 --------------------------- Incompatible JVM --------------------------- Version 1.8.0_391 of the JVM is not suitable for this product. Version: 17 or g…

【三维重建】运动恢复结构(SfM)

运动恢复结构是通过三维场景的多张图像&#xff0c;恢复出该场景的三维结构信息以及每张图片对应的摄像机参数。 欧式结构恢复(内参已知&#xff0c;外参未知) 欧式结构恢复问题&#xff1a; 已知&#xff1a;1、n个三维点在m张图像中的对应点的像素坐标 2、相机内参 求解&…

mysql入门到精通003-基础篇-SQL

1、目录 2、SQL通用语法及分类 2.1 SQL通用语法 2.2 SQL分类 3、SQL DDL数据库操作 3.1 SQL DDL表操作-创建&查询 3.1.1 表操作-查询 3.1.2 表操作-创建 create table tb_user(id int comment 编号,name varchar(50) comment 用户名,age int comment 用户名,gender varch…

mysql .ibd 文件过大清理方法

问题 有一个 info_track 表用来临时存储告警推送数据&#xff0c;逻辑处理完成后&#xff0c;会执行 Delete 语句删除对应的记录。 问题&#xff1a;项目现场运行了几个月后&#xff0c;发现磁盘空间莫名占用了过多的存储&#xff0c;> 100GB&#xff0c;且无法释放。 生…

Halcon 拟合

文章目录 算子更多xld算子更多区域算子 Blob 分析案例预处理图像增强降噪图像降噪 图像增强Halcon 基于圆的拟合 Halcon 共线联合案例Halcon 拟合动画案例Halcon 拟合椭圆 算子 二值化算子 &#xff08;二值化后获取的都是区域&#xff09; 二值化算子 clip_region_rel 剪切区域…

【总线接口】3.常见总线、接口GPIO、I2C、SPI、I2S、Modbus

初接触硬件&#xff0c;五花八门的总线、接口一定会让你有些疑惑&#xff0c;我尝试用一系列文章来解开你的疑惑。 系列文章 【总线接口】1.以Xilinx开发板为例&#xff0c;直观的认识硬件接口 【总线接口】2.学习硬件这些年接触过的硬件接口、总线 大汇总 【总线接口】3.常见…

单片机开发通用功能组件

mcu_reuse_development_module 单片机可复用、可通用开发组件&#xff0c;是以中间件思想开发的一套功能模块&#xff0c;将具有代表性或使用次数较多的功能和协议栈封装为独立的组件供开发者使用&#xff0c;开发者仅需通过组件提供的接口对接驱动层和应用层即可使用组件功能…

【PyTorch实战演练】Fast R-CNN中的RoI(Region of Interest)池化详解

文章目录 0. 前言1. ROI池化的提出背景2. RoI池化的结构与工作原理3. RoI池化的作用及意义4. RoI使用示例 0. 前言 按照国际惯例&#xff0c;首先声明&#xff1a;本文只是我自己学习的理解&#xff0c;虽然参考了他人的宝贵见解及成果&#xff0c;但是内容可能存在不准确的地方…

Kaggle竞赛系列_SpaceshipTitanic金牌方案分析_数据分析

文章目录 【文章系列】【前言】【比赛简介】【正文】&#xff08;一&#xff09;数据获取&#xff08;二&#xff09;数据分析1. 缺失值2. 重复值3. 属性类型分析4. 类别分析5. 分析目标数值占比 &#xff08;三&#xff09;属性分析1. 对年龄Age分析&#xff08;1&#xff09;…

Activiti工作流引擎

一、工作流介绍&#xff1a; 1.1 概念&#xff1a; 工作流(Workflow)&#xff0c;就是通过计算机对业务流程自动化执行管理。它主要解决的是“使在多个参与者之间按照某种预定义的规则自动进行传递文档、信息或任务的过程&#xff0c;从而实现某个预期的业务目标&#xff0c;或…

【golang】22、functional options | 函数式编程、闭包

文章目录 一、配置 Option1.1 options1.2 funcitonal options 一、配置 Option 1.1 options https://commandcenter.blogspot.com/2014/01/self-referential-functions-and-design.html I’ve been trying on and off to find a nice way to deal with setting options in a…

Flink中StateBackend(工作状态)与Checkpoint(状态快照)的关系

State Backends 由 Flink 管理的 keyed state 是一种分片的键/值存储&#xff0c;每个 keyed state 的工作副本都保存在负责该键的 taskmanager 本地中。另外&#xff0c;Operator state 也保存在机器节点本地。Flink 定期获取所有状态的快照&#xff0c;并将这些快照复制到持…

Python面向对象编程:探索代码的结构之美

文章目录 一、引言二、为什么学习面向对象编程2.1 提高代码的可维护性&#xff1a;通过封装、继承和多态实现模块化设计2.2 提升代码的复用性&#xff1a;通过类和对象的创建实现代码的重用 三、类和对象的基本概念3.1 类和对象的定义和关系&#xff1a;类是对象的模板&#xf…

通过Nacos权重配置,实现微服务金丝雀发布效果(不停机部署)

在微服务项目迭代的过程中&#xff0c;不可避免需要上线&#xff1b;上线对应着部署&#xff0c;或者升级部署&#xff1b;部署对应着修改,修改则意味着风险。 传统的部署都需要先停止旧系统&#xff0c;然后部署新系统&#xff0c;之后需要对新系统进行全面的功能测试&#xf…

力扣hot100 n皇后 满注释版 通俗易懂

Problem: 51. N 皇后 文章目录 思路Code 思路 &#x1f468;‍&#x1f3eb; 参考地址 考虑每一行哪个位置放皇后判断是否合法递归下一行 Code class Solution {int n;char[][] board;List<List<String>> res new ArrayList<>();public List<List&l…

python_蓝桥杯刷题记录_笔记_入门2

前言 现在正式进入蓝桥杯的刷题啦&#xff0c;用python来做算法题&#xff0c;因为我之前其实都是用C来做题的&#xff0c;但是今年的话我打算换python来试试&#xff0c;很明显因为也才这学期接触python 加上之前C做题也比较菜&#xff0c;所以我打算用python重新来做题&#…