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

【数据结构与算法】之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道顺序表与链表典型编程题心决!

个人主页&#xff1a;秋风起&#xff0c;再归来~ 数据结构与算法 个人格言&#xff1a;悟已往之不谏&#xff0c;知来者犹可追 克心守己&#xff0c;律己则安&#xff01; 目录 1、顺序表 1.1 合并两个有序数组 1.2 原地移除数组中所有的元素va…...

Go 源码之旅-开篇

欢迎来到《Go 源码之旅》专栏&#xff01;在这个专栏中&#xff0c;我们将深入探索 Go 编程语言的内部数据结构的工作原理&#xff0c;一起踏上一段令人兴奋的源码之旅。 我们将一步步解析关键的数据结构底层工作原理以及一些常用框架的设计原理及其源码。 无论你是初学者还是…...

spring的事件推送

本质上是设计模式中的观察者模式。 一、什么是观察者模式 观察者模式是一种行为型设计模式&#xff0c;它定义了一种一对多的依赖关系&#xff0c;当一个对象的状态发生改变时&#xff0c;其所有依赖者都会收到通知并自动更新。 二、什么是spring的事件推送 在 Spring 的事…...

计算机网络—HTTPS协议详解:工作原理、安全性及应用实践

&#x1f3ac;慕斯主页&#xff1a;修仙—别有洞天 ♈️今日夜电波&#xff1a;ヒューマノイド—ずっと真夜中でいいのに。 1:03━━━━━━️&#x1f49f;──────── 5:06 &#x1f504; ◀️ ⏸…...

卫星遥感影像在农业方面的应用及评价

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

docker pull镜像的时候指定arm平台

指定arm平台 x86平台下载arm平台的镜像包 以mysql镜像为例 docker pull --platform linux/arm64 mysqldocker images查看镜像信息 要查看Docker镜像的信息&#xff0c;可以使用docker inspect命令。这个命令会返回镜像的详细信息&#xff0c;包括其元数据和配置。 docker i…...

如何通过OceanBase V4.2 动态采样优化查询性能

OceanBase v4.2 推出了优化器动态采样的功能&#xff0c;在SQL运行过程中&#xff0c;该功能会收集需要的统计信息&#xff0c;协助优化器制定出更好的执行计划&#xff0c;进一步提升了查询性能。 影响查询性能的因素是什么&#xff1f;为何你的优化器效果不佳&#xff1f; …...

Vue3---基础1(认识,创建)

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

JAVA集合ArrayList

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

Bitmap OOM

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

基于深度学习的人脸表情识别系统(PyQT+代码+训练数据集)

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

Qt 中的项目文件解析和命名规范

&#x1f40c;博主主页&#xff1a;&#x1f40c;​倔强的大蜗牛&#x1f40c;​ &#x1f4da;专栏分类&#xff1a;QT❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 目录 一、Qt项目文件解析 1、.pro 文件解析 2、widget.h 文件解析 3、main.cpp 文件解析 4、widget.cpp…...

【chatGPT】我:在Cadence Genus软件中,出现如下问题:......【4】

我 在Cadence Genus中&#xff0c;tcl代码为&#xff1a;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中的应用

在软件开发中&#xff0c;设计模式是解决特定问题的一种模板或者指南。它们是在多年的软件开发实践中总结出的有效方法。JAVA设计模式广泛应用于各种编程场景中&#xff0c;以提高代码的可读性、可维护性和扩展性。本文将介绍单例模式&#xff0c;这是一种常用的创建型设计模式…...

手把手教你创建新的OpenHarmony 三方库

创建新的三方库 创建 OpenHarmony 三方库&#xff0c;建议使用 Deveco Studio&#xff0c;并添加 ohpm 工具的环境变量到 PATH 环境变量。 创建方法 1&#xff1a;IDE 界面创建 在现有应用工程中&#xff0c;新创建 Module&#xff0c;选择"Static Library"模板&a…...

从零开始,如何成功进入IT行业?

0基础如何进入IT行业&#xff1f; 简介&#xff1a;对于没有任何相关背景知识的人来说&#xff0c;如何才能成功进入IT行业&#xff1f;是否有一些特定的方法或技巧可以帮助他们实现这一目标&#xff1f; 在当今数字化时代&#xff0c;IT行业无疑是一个充满活力和机遇的领域。…...

【数组】5螺旋矩阵

这里写自定义目录标题 一、题目二、解题精髓-循环不变量三、代码 一、题目 给定⼀个正整数 n&#xff0c;⽣成⼀个包含 1 到 n^2 所有元素&#xff0c;且元素按顺时针顺序螺旋排列的正⽅形矩阵。 示例: 输⼊: 3 输出: [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 二、解题精髓…...

Sora视频生成模型:开启视频创作新纪元

随着人工智能技术的飞速发展&#xff0c;视频生成领域也迎来了前所未有的变革。Sora视频生成模型作为这一领域的佼佼者&#xff0c;凭借其卓越的性能和创新的应用场景&#xff0c;受到了广泛的关注与好评。本文将对Sora视频生成模型进行详细介绍&#xff0c;带您领略其魅力所在…...

OpenAI现已普遍提供带有视觉应用程序接口的GPT-4 Turbo

OpenAI宣布&#xff0c;其功能强大的GPT-4 Turbo with Vision模型现已通过公司的API全面推出&#xff0c;为企业和开发人员将高级语言和视觉功能集成到其应用程序中开辟了新的机会。 PS&#xff1a;使用Wildcard享受不受网络限制的API调用&#xff0c;详情查看教程 继去年 9 月…...

Swift中的元组属性

在Swift中&#xff0c;元组属性指的是一个元组作为结构体、类或枚举的属性。可以将一个元组作为属性来存储和访问多个值。 例如&#xff0c;考虑以下的Person类&#xff1a; class Person {var name: Stringvar age: Intvar address: (String, Int)init(name: String, age: I…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

Oracle11g安装包

Oracle 11g安装包 适用于windows系统&#xff0c;64位 下载路径 oracle 11g 安装包...