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

单链表的应用(2)

环形链表的约瑟夫问题

编号为 1nn 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
在这里插入图片描述

  • 利用链表实现
    思路:(1)创建一个不带头单向循环链表,需要注意的是链表创建后返回的结点是最后一个结点,为的是链表可快速找到第一个结点和最后一个结点
    (2)创建结构体指针prevcur,分别代表最后一个结点和第一个结点,因为cur已经为第一个结点,因此count=1。遍历链表直到pcurnext还是pcur(即链表中只含有一个结点)时退出循环,循环过程中当countm时需要将当前位置的pcur置空,count重置为1。不为count时,只需将链表往后执行即可
    (3)退出循环后,返回cur->val即可
 typedef struct ListNode ListNode;ListNode* ListBuyNode(int x){ListNode* node=(ListNode*)malloc(sizeof(ListNode));if(node == NULL){perror("malloc:");exit(1);}node->val=x;node->next=NULL;return node; }ListNode* CreatList(int n)
{ListNode* head=ListBuyNode(1);ListNode* tail=head;for(int i=2;i<=n;i++){ListNode* node=ListBuyNode(i);tail->next=node;tail=tail->next;}tail->next=head;return tail;// !!!
}int ysf(int n, int m ) 
{ListNode* prev=CreatList(n);ListNode* cur=prev->next;int count=1;while(cur->next != cur){if(count == m){prev->next=cur->next;free(cur);cur=prev->next;count=1;}else {prev=cur;cur=cur->next;count++;}}return cur->val;
}
  • 利用循环语句实现
    思路:(1)利用i,形成一个可循环遍历的类似圆形的数组
    (2)利用j,来判断报的数,当报的数正好为m时,将a[i]赋值为1,并且不进行下面的循环,直到数组中仅剩一个数组的值为0
    (3)退出循环,遍历数组输出值为0的数组的下标
#include<stdio.h>int main()
{int n = 0;int m = 0;scanf("%d %d",&n,&m);int a[30] = { 0 };int count = 0;int i = 0;int j = 0;while (count < n - 1){i++;if (i>n)i = 1;if (a[i] == 0){j++;if (j % m == 0){count++;a[i] = 1;j = 0;}}}for (i = 1; i < n; i++){if (a[i] != 1){printf("%d\n", i);break;}}return 0;
}

在这里插入图片描述

分割链表

给你一个链表的头节点 head 和一个特定值 x ,请你对链表进行分隔,使得所有小于x的节点都出现在 大于或等于x的节点之前。
你不需要保留每个分区中各节点的初始相对位置。
在这里插入图片描述
思路:(1)判断head是否为空,空则直接返回head
(2)创建两个两个带头单向不循环链表,一个存放小于x的值的结点,一个存放大于等于x的值的结点。lessheadgreaterhead分别为两个链表的头结点,lesstailgreatertail分别为两个链表的尾结点。
(3)创建一个pcur代替head进行链表遍历,当pcurval小于x时将pcur存入less链表,大于等于x时将pcur存入greater链表
(4)遍历结束判断greatertail是否为空,不为空则将greatertailnext赋值为空,再将lesstailnext赋值为greatertailnext,将大小链表连接在一起
(5)创建retail赋值为lessheadnext,再将lesshead进行free置空,最后返回retail即可

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x)
{if(head == NULL){return head;}ListNode* lesshead=(ListNode*)malloc(sizeof(ListNode));ListNode* greaterhead=(ListNode*)malloc(sizeof(ListNode));ListNode* lesstail=lesshead;ListNode* greatertail=greaterhead;ListNode* pcur=head;while(pcur){if((pcur->val) < x){lesstail->next=pcur;lesstail=lesstail->next;pcur=pcur->next;}else{greatertail->next=pcur;greatertail=greatertail->next;pcur=pcur->next;}}if(greatertail)greatertail->next=NULL;lesstail->next=greaterhead->next;ListNode* retail=lesshead->next;free(lesshead);lesshead=NULL;return retail;
}

在这里插入图片描述

相关文章:

单链表的应用(2)

环形链表的约瑟夫问题 编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数&#xff0c;报到 m 的人离开。 下一个人继续从 1 开始报数。 n-1 轮结束以后&#xff0c;只剩下一个人&#xff0c;问最后留下的这个人编号是多少&#xff1f; 利用链表实现 思路&#xff1…...

【Boost | C++】使用Boost库创建文件夹

#include <boost/filesystem.hpp> #include <iostream> bool CreateDirectory(const std::string &dir_path) {try {if (...

月报总结|Moonbeam 10月份大事一览

万圣节快乐&#xff01;时间一晃眼&#xff0c;10月已经迈入尾声&#xff0c;也即将迎来寒冷的冬天。但与季节相反&#xff0c;加密产业近期的发展可以说是高潮起伏&#xff0c;热度不断攀升。Moonbeam在10月中也发布了许多重大的更新&#xff0c;如Uniswap V3前段上线、众贷DO…...

Latex安装记录

Title:Latex 基本概念 Tex:是一种具有编译和排版功能的基础语言&#xff0c;相当于C语言。 Latex:&#xff1a;LaTex是 Tex 的扩展版本&#xff0c;拥有多种宏包&#xff0c;能实现比 Tex 更多的功能。 TexLive&#xff1a;是一种 Tex 语言的发行版本。 Texstudio: 一种软件相…...

JavaEE-博客系统2(功能设计)

本部分内容&#xff1a;实现博客列表页&#xff1b;web程序问题的分析方法&#xff1b;实现博客详情页&#xff1b; 该部分的代码如下&#xff1a; WebServlet("/blog") public class BlogServlet extends HttpServlet {//Jackson ObjectMapper类(com.fasterxml.jac…...

2023年【高处安装、维护、拆除】免费试题及高处安装、维护、拆除找解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 高处安装、维护、拆除免费试题根据新高处安装、维护、拆除考试大纲要求&#xff0c;安全生产模拟考试一点通将高处安装、维护、拆除模拟考试试题进行汇编&#xff0c;组成一套高处安装、维护、拆除全真模拟考试试题&a…...

antv/g6之交互模式mode

什么是mode 在 AntV G6 中&#xff0c;“mode” 是用于配置图表交互模式的一种属性。通过设置 “mode”&#xff0c;可以控制图表的行为&#xff0c;以满足不同的交互需求。可能在不同的场景需要展现的交互行为不一样。比如查看模式下点击一个点就选中的状态&#xff0c;在编辑…...

基于8086电压表系统仿真系统设计

**单片机设计介绍&#xff0c;1665基于8051单片机与1601LCD的计算器设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 一个基于8086的电压表系统仿真系统可以分为硬件和软件两部分。 硬件部分包括输入设备&#xff08;例如模拟…...

Docker与微服务实战——基础篇

Docker与微服务实战——基础篇 第一章 Docker 简介1.1 docker 理念1.2 容器与虚拟机比较 第二章 Docker 安装2.1 前提说明2.2 Docker的基本组成2.2.1 镜像&#xff08;image&#xff09;2.2.2 容器&#xff08;container&#xff09;2.2.3 仓库&#xff08;repository&#xff…...

旧手机搭建linuxcentos

centos服务器搭建termux搭建centos旧手机搭建linux服务器ubuntu旧手机搭建网站旧手机搭建linux debian ubuntu centos 旧手机搭建宝塔搭建 32位Linux搭建宝塔 Linuxdeploy搭建宝塔 旧手机搭建服务器有需要的来 包答疑包售后 Linuxdeploy需要root mobile搭建服务器 脚本/工具...

使用pandas处理excel文件【Demo】

一、代码示例 import pandas as pd from pandas import Series,DataFrame from pandasql import sqldf import matplotlib.pyplotidInfos DataFrame(pd.read_excel(home_data.xlsx))print(idInfos.head(2))print(idInfos.dtypes)# print(idInfos[:][姓名]) # 自定义一个函数s…...

【Maven】<dependencyManagement>详解

<dependencyManagement> 元素是 Maven POM 文件中的一个非常重要的元素&#xff0c;它用于集中管理项目中所有模块的依赖项版本&#xff0c;允许您在父 POM 中定义依赖版本&#xff0c;然后在子模块中引用这些版本而不需要显式指定版本号。这可以大大减少维护成本&#x…...

apache-tomcat-9.0.29 安装配置教程

链接&#xff1a;https://pan.baidu.com/s/100buXYpn8w8xjI2KdvHk2Q?pwd2mwc 提取码&#xff1a;2mwc 1.将压缩包解压到指定文件夹下 2.进入bin文件夹下 3.找到setclasspath.bat文件 4.推荐用notepad打开文件&#xff0c;并做如下配置&#xff08;可解决tomcat启动闪退问题&…...

精品基于Python的图书借阅归还管控系统

《[含文档PPT源码等]精品基于Python的图书管控系统》该项目含有源码、文档、PPT、配套开发软件、软件安装教程、项目发布教程、包运行成功&#xff01; 软件开发环境及开发工具&#xff1a; 开发语言&#xff1a;python 使用框架&#xff1a;Django 前端技术&#xff1a;Ja…...

gorm的自动化工具gen

gorm的自动化工具gen 官方 https://gorm.io/zh_CN/gen/假设数据库结构如 这里使用gen-tool 安装 go install gorm.io/gen/tools/gentoollatest用法 gentool -hUsage of gentool:-c string配置文件名、默认值 “”、命令行选项的优先级高于配置文件。 -db string指定Driver…...

dubbo没有找到生产者

1、没有找到生产者 com.alibaba.dubbo.rpc.RpcException: No provider available from registry 127.0.0.1:2181 for service .... , please check status of providers(disabled, not registered or in blacklist)2、 查看是不是 对应的providers 没有 注册上去 找到 zk 对应…...

论文阅读——What Can Human Sketches Do for Object Detection?(cvpr2023)

论文&#xff1a;https://openaccess.thecvf.com/content/CVPR2023/papers/Chowdhury_What_Can_Human_Sketches_Do_for_Object_Detection_CVPR_2023_paper.pdf 代码&#xff1a;What Can Human Sketches Do for Object Detection? (pinakinathc.me) 一、 Baseline SBIR Fram…...

统计学习方法 牛顿法和拟牛顿法

文章目录 统计学习方法 牛顿法和拟牛顿法牛顿法拟牛顿法DFP 算法BFGS 算法Broyden 类算法 统计学习方法 牛顿法和拟牛顿法 学习李航的《统计学习方法》时&#xff0c;关于牛顿法和拟牛顿法的笔记。 牛顿法&#xff08;Newton method&#xff09;和拟牛顿法&#xff08;quasi-…...

React基础知识02

一、通过属性来传值&#xff08;props&#xff09; react中可以使用属性&#xff08;props&#xff09;可以传递给子组件&#xff0c;子组件可以使用这些属性值来控制其行为和呈现输出。 例子&#xff1a; // 1.1 父组件 import React, { useState } from react // 1.2引入子…...

Oracle(10)Managing Undo Data

目录 一、基础知识 1、AUM :Init Parameters AUM:初始化参数 2、AUM:Other Parameters AUM:其他参数 3、AUM:Sizing an UNDO TS AUM:调整UNDOTS的大小 4、AUM :Undo Quota AUM:撤消配额 5、Get Undo Segment Info 获取撤消段信息 二、基础操作 1、AUM:UNDO Tablespace …...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

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 位数字。 输…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档&#xff09;&#xff0c;如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下&#xff0c;风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

Java毕业设计:WML信息查询与后端信息发布系统开发

JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发&#xff0c;实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构&#xff0c;服务器端使用Java Servlet处理请求&#xff0c;数据库采用MySQL存储信息&#xff0…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能

1. 开发环境准备 ​​安装DevEco Studio 3.1​​&#xff1a; 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK ​​项目配置​​&#xff1a; // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...