【数据结构与算法】之8道顺序表与链表典型编程题心决!
个人主页:秋风起,再归来~
数据结构与算法
个人格言:悟已往之不谏,知来者犹可追
克心守己,律己则安!
目录
1、顺序表
1.1 合并两个有序数组
1.2 原地移除数组中所有的元素val
2、链表
2.1 移除链表元素
2.2 反转链表
2.3 合并两个有序链表
2.4 链表的中间节点
2.5 环形链表的约瑟夫问题
2.6 分割链表
3、完结散花
1、顺序表
1.1 合并两个有序数组
题目描述:
给你两个按 非递减顺序 排列的整数数组
nums1
和nums2
,另有两个整数m
和n
,分别表示nums1
和nums2
中的元素数目。请你 合并
nums2
到nums1
中,使合并后的数组同样按 非递减顺序 排列。注意:最终,合并后数组不应由函数返回,而是存储在数组
nums1
中。为了应对这种情况,nums1
的初始长度为m + n
,其中前m
个元素表示应合并的元素,后n
个元素为0
,应忽略。nums2
的长度为n
。示例 1:
输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [1,2,2,3,5,6] ,其中斜体加粗标注的为 nums1 中的元素。示例 2:
输入:nums1 = [1], m = 1, nums2 = [], n = 0 输出:[1] 解释:需要合并 [1] 和 [] 。 合并结果是 [1] 。示例 3:
输入:nums1 = [0], m = 0, nums2 = [1], n = 1 输出:[1] 解释:需要合并的数组是 [] 和 [1] 。 合并结果是 [1] 。 注意,因为 m = 0 ,所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。提示:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
OJ链接:合并两个有序数组
解题代码:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int tail=nums1Size-1;int p1=m-1;int p2=n-1;while(p1>=0&&p2>=0){if(nums1[p1]>nums2[p2]){nums1[tail--]=nums1[p1--];}else{nums1[tail--]=nums2[p2--];}}if(p1<0){while(p2>=0){nums1[tail--]=nums2[p2--];}}
}
1.2 原地移除数组中所有的元素val
题目描述:
给你一个数组
nums
和一个值val
,你需要 原地 移除所有数值等于val
的元素,并返回移除后数组的新长度。不要使用额外的数组空间,你必须仅使用
O(1)
额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以「引用」方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝 int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) {print(nums[i]); }示例 1:
输入:nums = [3,2,2,3], val = 3 输出:2, nums = [2,2] 解释:函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如,函数返回的新长度为 2 ,而 nums = [2,2,3,3] 或 nums = [2,2,0,0],也会被视作正确答案。示例 2:
输入:nums = [0,1,2,2,3,0,4,2], val = 2 输出:5, nums = [0,1,3,0,4] 解释:函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0 1,3,0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。提示:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
OJ链接移除元素
解题代码:
int removeElement(int* nums, int numsSize, int val) {if(numsSize<=0||nums==NULL)return 0;int cur=0;//用cur去遍历原数组int newNums=0;while(numsSize--){if(nums[cur]==val){cur++;}else{nums[newNums++]=nums[cur++];}}return newNums;
}
2、链表
2.1 移除链表元素
题目描述:
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]示例 2:
输入:head = [], val = 1 输出:[]示例 3:
输入:head = [7,7,7,7], val = 7 输出:[]提示:
- 列表中的节点数目在范围
[0, 104]
内1 <= Node.val <= 50
0 <= val <= 50
OJ链接:移除链表元素
解题代码:
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {if(head==NULL)return NULL;ListNode* newHead=(ListNode*)malloc(sizeof(ListNode));//创建一个带哨兵卫的头结点ListNode* newTail=newHead;ListNode* cur=head;while(cur){if(cur->val==val){cur=cur->next;}else{newTail->next=cur;newTail=newTail->next;cur=cur->next;}}newTail->next=NULL;return newHead->next;
}
2.2 反转链表
题目描述:
给你单链表的头节点
head
,请你反转链表,并返回反转后的链表。示例 1:
输入:head = [1,2,3,4,5] 输出:[5,4,3,2,1]示例 2:
输入:head = [1,2] 输出:[2,1]示例 3:
输入:head = [] 输出:[]提示:
- 链表中节点的数目范围是
[0, 5000]
-5000 <= Node.val <= 5000
题目链接:反转单链表
解题代码:
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {if(head==NULL)return NULL;ListNode* n1,*n2,*n3;n1=NULL;n2=head;n3=head->next;while(n2){n2->next=n1;n1=n2;n2=n3;if(n3){n3=n3->next;}}return n1;
}
2.3 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4]示例 2:
输入:l1 = [], l2 = [] 输出:[]示例 3:
输入:l1 = [], l2 = [0] 输出:[0]提示:
- 两个链表的节点数目范围是
[0, 50]
-100 <= Node.val <= 100
l1
和l2
均按 非递减顺序 排列OJ链接:合并两个有序链表
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode* newHead,*newTail;newTail=newHead=(ListNode*)malloc(sizeof(ListNode));ListNode* l1=list1;ListNode* l2=list2;while(l1&&l2){if((l1->val)<(l2->val)){newTail->next=l1;l1=l1->next;}else{newTail->next=l2;l2=l2->next;}newTail=newTail->next;}if(l1){newTail->next=l1;}else{newTail->next=l2;}return newHead->next;
}
2.4 链表的中间节点
给你单链表的头结点
head
,请你找出并返回链表的中间结点。如果有两个中间结点,则返回第二个中间结点。
示例 1:
输入:head = [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个中间结点,值为 3 。示例 2:
输入:head = [1,2,3,4,5,6] 输出:[4,5,6] 解释:该链表有两个中间结点,值分别为 3 和 4 ,返回第二个结点。提示:
- 链表的结点数范围是
[1, 100]
1 <= Node.val <= 100
OJ链接
链表的中间节点
typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {if(head==NULL)return NULL;ListNode* fast,*slow;fast=slow=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;
}
2.5 环形链表的约瑟夫问题
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?
数据范围: 1≤n,m≤10000
进阶:空间复杂度O(1),时间复杂度 O(n)
OJ链接:环形链表的约瑟夫问题
typedef struct ListNode ListNode;
ListNode* byNode(int x)
{ListNode* node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){exit(1);}node->val=x;return node;
}
ListNode* creatCircle(int x)
{ListNode* head=(ListNode*)malloc(sizeof(ListNode));//创建头结点if(head==NULL){exit(1);}ListNode* tail=head;for(int i=1;i<=x;i++){tail->next=byNode(i);tail=tail->next;}tail->next=head->next;return tail;
}int ysf(int n, int m ) {// write code here//创建循环链表并返回尾节点ListNode* prev=creatCircle(n);ListNode* cur=prev->next;int count=1;//报数while(cur!=cur->next){if(count==m){prev->next=cur->next;free(cur);cur=prev->next;count=1;//重置为1}else {prev=cur;cur=cur->next;count++;}}return cur->val;
}
2.6 分割链表
给你一个链表的头节点
head
和一个特定值x
,请你对链表进行分隔,使得所有 小于x
的节点都出现在 大于或等于x
的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。
示例 1:
输入:head = [1,4,3,2,5,2], x = 3 输出:[1,2,2,4,3,5]示例 2:
输入:head = [2,1], x = 2 输出:[1,2]提示:
- 链表中节点的数目在范围
[0, 200]
内-100 <= Node.val <= 100
-200 <= x <= 200
OJ链接:分割链表
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(head==NULL){return NULL;}//创建两个头结点ListNode* lessHead=(ListNode*)malloc(sizeof(ListNode));if(lessHead==NULL){exit(1);}ListNode* greaterHead=(ListNode*)malloc(sizeof(ListNode));if(greaterHead==NULL){exit(1);}ListNode* lessTail=lessHead;ListNode* greaterTail=greaterHead;lessHead->next=greaterHead->next=NULL;ListNode* cur=head;while(cur){if(cur->val<x){lessTail->next=cur;lessTail=lessTail->next;}else{greaterTail->next=cur;greaterTail=greaterTail->next;}cur=cur->next;}lessTail->next=greaterHead->next;greaterTail->next=NULL;return lessHead->next;
}
3、完结散花
好了,这期的分享到这里就结束了~
如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~
如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~
我们下期不见不散~~
相关文章:

【数据结构与算法】之8道顺序表与链表典型编程题心决!
个人主页:秋风起,再归来~ 数据结构与算法 个人格言:悟已往之不谏,知来者犹可追 克心守己,律己则安! 目录 1、顺序表 1.1 合并两个有序数组 1.2 原地移除数组中所有的元素va…...
Go 源码之旅-开篇
欢迎来到《Go 源码之旅》专栏!在这个专栏中,我们将深入探索 Go 编程语言的内部数据结构的工作原理,一起踏上一段令人兴奋的源码之旅。 我们将一步步解析关键的数据结构底层工作原理以及一些常用框架的设计原理及其源码。 无论你是初学者还是…...
spring的事件推送
本质上是设计模式中的观察者模式。 一、什么是观察者模式 观察者模式是一种行为型设计模式,它定义了一种一对多的依赖关系,当一个对象的状态发生改变时,其所有依赖者都会收到通知并自动更新。 二、什么是spring的事件推送 在 Spring 的事…...

计算机网络—HTTPS协议详解:工作原理、安全性及应用实践
🎬慕斯主页:修仙—别有洞天 ♈️今日夜电波:ヒューマノイド—ずっと真夜中でいいのに。 1:03━━━━━━️💟──────── 5:06 🔄 ◀️ ⏸…...

卫星遥感影像在农业方面的应用及评价
一、引言 随着科技的进步,卫星遥感技术在农业领域的应用越来越广泛。卫星遥感技术以其宏观、快速、准确的特点,为农业生产和管理提供了有力的技术支撑。本文将对卫星遥感在农业方面的应用进行详细介绍,并通过具体案例进行说明。 二、…...

docker pull镜像的时候指定arm平台
指定arm平台 x86平台下载arm平台的镜像包 以mysql镜像为例 docker pull --platform linux/arm64 mysqldocker images查看镜像信息 要查看Docker镜像的信息,可以使用docker inspect命令。这个命令会返回镜像的详细信息,包括其元数据和配置。 docker i…...
如何通过OceanBase V4.2 动态采样优化查询性能
OceanBase v4.2 推出了优化器动态采样的功能,在SQL运行过程中,该功能会收集需要的统计信息,协助优化器制定出更好的执行计划,进一步提升了查询性能。 影响查询性能的因素是什么?为何你的优化器效果不佳? …...

Vue3---基础1(认识,创建)
变化 相对于Vue2,Vue3的变化: 性能的提升 打包大小减少 41% 初次渲染快 55%,更新渲染快133% 内存减少54% 源码的升级 使用 proxy 代替 defineProperty 实现响应式 重写虚拟 DOM 的实现和 Tree-shaking TypeScript Vue3就可以更好的支持TypeSc…...

JAVA集合ArrayList
目录 ArrayList概述 add(element) 用法 add(index, element)用法 remove(element)用法 remove(index)用法 get(index)用法 set(index,element) 练习 test1 定义一个集合,添加字符串,并进行遍历&…...

Bitmap OOM
老机器Bitmap预读仍然OOM,无奈增加一段,终于不崩溃了。 if (Build.VERSION.SDK_INT < 21)size 2; 完整代码: Bitmap bitmap; try {//Log.e(Thread.currentThread().getStackTrace()[2] "", surl);URL url new URL(surl);…...

基于深度学习的人脸表情识别系统(PyQT+代码+训练数据集)
基于深度学习的人脸表情识别系统(PyQT代码训练数据集) 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现 前言 本项目是基于mini_Xception深度学习网络模型的人脸表情识别系统&#x…...

Qt 中的项目文件解析和命名规范
🐌博主主页:🐌倔强的大蜗牛🐌 📚专栏分类:QT❤️感谢大家点赞👍收藏⭐评论✍️ 目录 一、Qt项目文件解析 1、.pro 文件解析 2、widget.h 文件解析 3、main.cpp 文件解析 4、widget.cpp…...
【chatGPT】我:在Cadence Genus软件中,出现如下问题:......【4】
我 在Cadence Genus中,tcl代码为:foreach clk $clk_list{ set clkName [lindex $clk_list 0] set targetFreq [lindex $clk_list 1] set uncSynth [lindex $clk_list 4] set clkPeriod [lindex “%.3f” [expr 1 / $targetFreq]] … } 以上代码出现如下…...
单例模式(Singleton Pattern)在JAVA中的应用
在软件开发中,设计模式是解决特定问题的一种模板或者指南。它们是在多年的软件开发实践中总结出的有效方法。JAVA设计模式广泛应用于各种编程场景中,以提高代码的可读性、可维护性和扩展性。本文将介绍单例模式,这是一种常用的创建型设计模式…...

手把手教你创建新的OpenHarmony 三方库
创建新的三方库 创建 OpenHarmony 三方库,建议使用 Deveco Studio,并添加 ohpm 工具的环境变量到 PATH 环境变量。 创建方法 1:IDE 界面创建 在现有应用工程中,新创建 Module,选择"Static Library"模板&a…...
从零开始,如何成功进入IT行业?
0基础如何进入IT行业? 简介:对于没有任何相关背景知识的人来说,如何才能成功进入IT行业?是否有一些特定的方法或技巧可以帮助他们实现这一目标? 在当今数字化时代,IT行业无疑是一个充满活力和机遇的领域。…...

【数组】5螺旋矩阵
这里写自定义目录标题 一、题目二、解题精髓-循环不变量三、代码 一、题目 给定⼀个正整数 n,⽣成⼀个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正⽅形矩阵。 示例: 输⼊: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 二、解题精髓…...
Sora视频生成模型:开启视频创作新纪元
随着人工智能技术的飞速发展,视频生成领域也迎来了前所未有的变革。Sora视频生成模型作为这一领域的佼佼者,凭借其卓越的性能和创新的应用场景,受到了广泛的关注与好评。本文将对Sora视频生成模型进行详细介绍,带您领略其魅力所在…...

OpenAI现已普遍提供带有视觉应用程序接口的GPT-4 Turbo
OpenAI宣布,其功能强大的GPT-4 Turbo with Vision模型现已通过公司的API全面推出,为企业和开发人员将高级语言和视觉功能集成到其应用程序中开辟了新的机会。 PS:使用Wildcard享受不受网络限制的API调用,详情查看教程 继去年 9 月…...
Swift中的元组属性
在Swift中,元组属性指的是一个元组作为结构体、类或枚举的属性。可以将一个元组作为属性来存储和访问多个值。 例如,考虑以下的Person类: class Person {var name: Stringvar age: Intvar address: (String, Int)init(name: String, age: I…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
tomcat入门
1 tomcat 是什么 apache开发的web服务器可以为java web程序提供运行环境tomcat是一款高效,稳定,易于使用的web服务器tomcathttp服务器Servlet服务器 2 tomcat 目录介绍 -bin #存放tomcat的脚本 -conf #存放tomcat的配置文件 ---catalina.policy #to…...