OJ第四篇

文章目录

  • 链表分割
  • 环形链表
  • 有效的括号

链表分割

链接: 链表分割
在这里插入图片描述

虽然这个题牛客网中只有C++,但是无所谓,我们只要知道C++是兼容C的就可以了

至于说这个题的思路,我们就弄两个链表,把小于x的结点放到一个链表中,剩下的放到另一个链表中,最后把两个链表串起来就可以了

实现方式的话有两种,一种是链表带哨兵位,一种是不带,带哨兵位的话处理起来比较简单,很多判断条件是不需要的,不带的话就相对要麻烦一些,但是你如果对链表的操作比较熟悉的话,其实还行

下面是带哨兵位的实现

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *cur=pHead;struct ListNode *head1,*head2,*tail1,*tail2;//1的是小值,2的是大值//开辟哨兵位head1=tail1=(struct ListNode *)malloc(sizeof(struct ListNode ));head2=tail2=(struct ListNode *)malloc(sizeof(struct ListNode ));
while(cur){struct ListNode *next=cur->next;if(cur->val<x){tail1->next=cur;tail1=tail1->next;tail1->next=NULL;}else{tail2->next=cur;tail2=tail2->next;tail2->next=NULL;}cur=next;
}
//把两个链表接到一起,如果第一个链表为空也无所谓
tail1->next=head2->next;struct ListNode *head=head1->next;free(head1);//没用的就free掉free(head2);
return head;}
};

下面是不带哨兵位的实现

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode *cur=pHead;struct ListNode *head1=NULL,*head2=NULL,*tail1=NULL,*tail2=NULL;//一般都是定义两组指针,一组管理一个链表while(cur){struct ListNode *tmp=cur;cur=cur->next;if(tmp->val<x){
if(tail1==NULL){//如果链表为空head1=tail1=tmp;tail1->next=NULL;
}
else{tail1->next=tmp;tail1=tail1->next;tail1->next=NULL;
}}else{
if(tail2==NULL){head2=tail2=tmp;tail2->next=NULL;
}
else{tail2->next=tmp;tail2=tail2->next;tail2->next=NULL;
}}}//合并两个链表if(head1==NULL){//判断第一个表是否为空return head2;}else{tail1->next=head2;return head1;}}
};

环形链表

链接:环形链表
在这里插入图片描述

这个题的话需要一些数学推理去找它们之间的关系,要不然不太好说

我们假如说起始位置到入环处的距离为a,入环出到相遇处距离为b,环的周长为c,在之前,我们已经能判断一个链表中是否有环了,就是通过两个指针,一个fast一回走两步,一个slow一回走一步,那么它们两个之间有一定的数学关系,就是2*(a+b)=a+nc+b,化简一下为c-b+c(n-1)=a,这是什么意思啊?就是一个指针从头走,一个指针从相遇处走,以相同的速度,最后就会在那个相遇入环点相遇

下面我们来实现一下

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head,*slow=head;
while(fast&&fast->next){//能出循环就没有环,有环在循环中返回
fast=fast->next->next;
slow=slow->next;if(fast==slow){
struct ListNode *tmp=fast;
while(tmp!=head){//相同时停止,并返回这个点
tmp=tmp->next;
head=head->next;
}
return head;}
}
return NULL;
}

我们之前找过两个相交链表的相交位置,这里我们如果把相遇点的前一个位置的next置为空,就可以了,需要注意前一个只能是fast的前一个

下面我们来实现一下

//找相交点的函数
//思路就是计算两个链表的长度,长的先走差的长度数,最后同时走,相同了就找到了
struct ListNode *meetpoint(struct ListNode *s1,struct ListNode *s2){int num1=0;int num2=0;struct ListNode *head1=s1,*head2=s2;while(head1){num1++;head1=head1->next;}while(head2){num2++;head2=head2->next;}struct ListNode *thelong=s1,*theshort=s2;if(num2>num1){thelong=s2;theshort=s1;}int num=abs(num1-num2);//求差的长度数while(num){thelong=thelong->next;num--;}while(thelong!=theshort){thelong=thelong->next;theshort=theshort->next;}return thelong;
}struct ListNode *detectCycle(struct ListNode *head) {struct ListNode *fast=head,*slow=head;
while(fast&&fast->next){struct ListNode *fastprev=fast->next;//记录一下fast的上个位置
fast=fast->next->next;slow=slow->next;if(fast==slow){fastprev->next=NULL;return meetpoint(head,slow);}
}
return NULL;
}

有效的括号

链接:有效的括号
在这里插入图片描述

这个题是用栈来实现的,正好利用了栈的特性,左括号入栈,右括号判断出栈,如果不匹配就返回false

bool isValid(char * s){ST st;STInit(&st);
while(*s){if(*s=='('||*s=='['||*s=='{'){//左括号入栈STPush(&st,*s);}else{if(STEmpty(&st)){//栈为空并且要处理的字符为右括号STDestroy(&st);return false;}char tmp=STTop(&st);//匹配栈顶元素和要处理的元素if(*s==')'&&tmp!='('||*s==']'&&tmp!='['||*s=='}'&&tmp!='{'){return false;}else{STPop(&st);}}s++;
}
if(!STEmpty(&st)){//true的话最后栈应该为空
STDestroy(&st);return false;
}
else{STDestroy(&st);return true;
}
}

我们在这个函数之前是需要自己创建栈的,并且要实现它的一些功能,我们之前也有代码,可以看之前的博客
链接:栈和队列

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2023年10月工作经验及问题整理总结

目录 1.window自带的base64加密解密 2.ElementUI修改鼠标移动到表格的背景色 3.vscode保存时几万个eslint错误 4.Git 拉取Gitee仓库报错&#xff1a;“fatal: unable to access ": Failed to connect to 127.0.0.1 port 1080: Connection r... 4.1本地查看Git是否使用…

Java版本spring cloud + spring boot企业电子招投标系统源代码

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…

spark stream入门案例:netcat准实时处理wordCount(scala 编程)

目录 案例需求 代码 结果 解析 案例需求&#xff1a; 使用netcat工具向9999端口不断的发送数据&#xff0c;通过SparkStreaming读取端口数据并统计不同单词出现的次数 -- 1. Spark从socket中获取数据&#xff1a;一行一行的获取 -- 2. Driver程序执行时&#xff0c…

加固数据安全:Java助力保护Excel文件,让数据无懈可击

摘要&#xff1a;本文由葡萄城技术团队于CSDN原创并首发。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 Excel文件保护是常用的一种功能&#xff0c;文件保护主要有三种&#xff1a; 添…

单目3D自动标注

这里介绍两种 1. 基于SAM的点云标注 Seal&#xff1a;是一个多功能的自监督学习框架&#xff0c;能够通过利用视觉基础模型的现成知识和2D-3D的时空约束分割自动驾驶数据集点云 Scalability&#xff1a;可拓展性强&#xff0c;视觉基础模型蒸馏到点云中&#xff0c;避免2D和…

SaaS人力资源管理系统的Bug

SaaS人力资源管理系统的Bug Bug1【18】 这里我是直接把代码复制过来的&#xff0c;然后就有一个空白 这是因为它的代码有问题&#xff0c;原本的代码如下所示 <el-table-column fixed type"index" label"序号" width"50"></el-table…

Linux性能优化--性能追踪:受CPU限制的应用程序(GIMP)

10.0 概述 本章包含了一个例子&#xff1a;如何用Linux性能工具在受CPU限制的应用程序中寻找并修复性能问题。 阅读本章后&#xff0c;你将能够&#xff1a; 在受CPU限制的应用程序中明确所有的CPU被哪些源代码行使用。用1trace和oprofile弄清楚应用程序调用各种内部与外部函…

KNN-近邻算法 及 模型的选择与调优(facebook签到地点预测)

什么是K-近邻算法&#xff08;K Nearest Neighbors&#xff09; 1、K-近邻算法(KNN) 1.1 定义 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别&#xff0c;则该样本也属于这个类别。 来源&#xff1a;KNN算法最早是由Cover和Hart提…

【JVM面试】从JDK7 到 JDK8, JVM为啥用元空间替换永久代?

系列文章目录 【JVM系列】第一章 运行时数据区 【面试】第二章 从JDK7 到 JDK8, JVM为啥用元空间替换永久代&#xff1f; 大家好&#xff0c;我是青花。拥有多项发明专利&#xff08;都是关于商品、广告等推荐产品&#xff09;。对广告、Web全栈以及Java生态微服务拥有自己独到…

VSS、VDD、VBAT、VSSA

引言 在学习设计TM32时&#xff0c;发现芯片除了GPIO引脚外还会引出许多引脚&#xff0c;以STM32F407ZGT6为例除了GPIO引脚还会有以下引脚 如VSS、VDD、VBAT、VSSA、NRST、VREF、VDDA、VCAP_1、VCAP_2、PDR_ON这些引脚。他们有何作用&#xff0c;电路设计中应如何连接&#x…

迅为RK3588开发板使用RKNN-Toolkit-lite2运行测试程序

1 首先也需要部署运行环境&#xff0c;将库文件放入 RK3588 开发板上&#xff0c;我们将网盘资料“iTOP-3588 开发 板 \02_ 【 iTOP-RK3588 开 发 板 】 开 发 资 料 \12_NPU 使 用 配 套 资 料 \05_Linux_librknn_api\librknn_api\aarch64”路径下的文件通过U盘拷贝到开发板的…

LLM-RAG-WEB 大模型+文件+可视化界面

注意&#xff1a;这里只是简单实现了功能和界面&#xff0c;文件对话也暂时只支持一个文件&#xff0c;如果跳到模型对话再切换回文件对话会文件会删除重置会话&#xff0c;但模型对话切换回来时保留之前会话的。 1、代码&#xff08;使用步骤说明在链接里&#xff09; 参考下…

SQLite4Unity3d安卓 在手机上创建sqlite失败解决

总结 要在Unity上运行一次出现库&#xff0c;再打包进APK内 问题 使用示例代码的创建库 var dbPath string.Format("Assets/StreamingAssets/{0}", DatabaseName); #else// check if file exists in Application.persistentDataPathvar filepath string.Format…

Wireshark新手小白基础使用方法

一、针对IP抓取 1、过滤格式&#xff1a; &#xff08;1&#xff09;、ip.src eq x.x.x.x &#xff08;2&#xff09;、ip.dst eq x.x.x.x &#xff08;3&#xff09;ip.src eq x.x.x.x or ip.dst eq x.x.x.x 二、针对端口过滤 1、过滤格式&#xff1a; &#xff08;1&a…

百度智能云千帆大模型平台 2.0 产品技术解析

本文整理自 2023 年 9 月 5 日百度云智大会 - 智能计算&大模型技术分论坛&#xff0c;百度智能云 AI &大数据平台总经理忻舟的主题演讲《百度智能云千帆大模型平台 2.0 产品技术解析》。 这是关于技术主题的论坛&#xff0c;我首先问大家三个开发者的小问题。 第一个问…

如何使用RockPlus MES系统帮助SMT行业实现降本增效

SMT&#xff08;Surface Mount Technology&#xff09;是现代电子行业中主要的组装技术&#xff0c;广泛应用于电子产品的生产。SMT工艺涵盖了锡膏印刷、元器件贴装和回流焊接。经过这些关键工序&#xff0c;元器件被精确固定在电路板上&#xff0c;完成一个电子产品组装。 SM…

SpringCloud: feign整合sentinel实现降级

一、加依赖&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache…

excel+requests管理测试用例接口自动化框架

背景&#xff1a; 某项目有多个接口&#xff0c;之前使用的unittest框架来管理测试用例&#xff0c;将每个接口的用例封装成一个py文件&#xff0c;接口有数据或者字段变动后&#xff0c;需要去每个py文件中找出变动的接口测试用例&#xff0c;维护起来不方便&#xff0c;为了…

Spring AOP归纳与总结

前言 AOP的核心思想是面向切面编程。AOP规范定义了多种概念&#xff0c;常用的aop框架有spring aop和AspectJ&#xff0c;两者功能和性能差异较大&#xff0c;现在默认的AOP框架是AspectJ&#xff0c;下面逐渐归纳其相关概念、功能及实现原理。 1. 概念 1. 切面&#xff1a;…

从零开始学习 Java:简单易懂的入门指南之线程池(三十六)

线程池 1.1 线程状态介绍1.2 线程池-基本原理1.3 线程池-Executors默认线程池1.4 线程池-Executors创建指定上限的线程池1.5 线程池-ThreadPoolExecutor1.6 线程池-参数详解1.7 线程池-非默认任务拒绝策略 1.1 线程状态介绍 当线程被创建并启动以后&#xff0c;它既不是一启动…