【数据结构与算法】之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、完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

​​​​

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

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

相关文章

工程施工业务中-几分钟搭建一个设计图纸和现状倾斜叠加的微信可查看三维场景

0序 一个施工单位的朋友提出&#xff1a; 很多项目前期还并没有制作完善的【施工策划方案】&#xff0c;刚做了现场的无人机航测&#xff0c;这时候就需要频繁的相互沟通&#xff0c;也很难每次都带着电脑去交流、汇报。 尤其是领导经常比较忙&#xff0c;如果能提前让领导看一…

【三十六】【算法分析与设计】综合练习(3),39. 组合总和,784. 字母大小写全排列,526. 优美的排列

目录 39. 组合总和 对每一个位置进行枚举 枚举每一个数出现的次数 784. 字母大小写全排列 526. 优美的排列 结尾 39. 组合总和 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不…

【每日刷题】Day11

【每日刷题】Day11 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; 目录 1. 860. 柠檬水找零 - 力扣&#xff08;LeetCode&#xff09; 2. 976. 三角形的最大周长 - 力扣&#xff08;LeetCode&#xff09; 3.…

CMD命令窗口提示文字乱码

我下面说的是日文版系统&#xff0c;中文版会有差异。 一般情况下是 Shiftjis 通常我是用sakura editor来写bat&#xff0c;但是运行后会在cmd窗口出现乱码 test.bat set HENSU这是一个变数 echo %HENSU% pause 执行后出现乱码 原因是不做设置时&#xff0c;command prom…

Switch-case

Java switch case 语句 switch case 语句判断一个变量与一系列值中某个值是否相等&#xff0c;每个值称为一个分支。 语法 switch case 语句语法格式如下&#xff1a; switch(expression){case value ://语句break; //可选case value ://语句break; //可选//你可以有任意数量…

卫星影像联合无人机实现农业保险全生命周期监管监测

随着科技的进步&#xff0c;农业保险监管系统的发展日新月异。特别是近年来&#xff0c;随着卫星技术与无人机技术的结合&#xff0c;为农业保险监管系统带来了前所未有的革新。本文将深入探讨如何利用卫星与无人机方案构建高效的农业保险监管系统&#xff0c;并结合实例进行说…

python之堆的实现

堆本质是一个完全二叉树&#xff0c;分为大根堆和小根堆&#xff0c;大根堆每个结点的值都大于它的孩子的值&#xff0c;小根堆相反&#xff0c;每个结点的值都小于它的孩子的值 heapq是python的标准库&#xff0c;用于维护堆&#xff0c;非常方便 heapq库常用的几个函数 he…

快速实现一个Hibernate的例子

写第一个简单的Hibernate程序&#xff1a; 具体的开始第一个Hibernate程序之前: 找到jar包, hibernate 的核心包, mysql数据库的连接驱动包, junit测试包 ①创建Hibernate配置文件 ②创建持久化类 也是和数据库中数据表一一对应这个类 ③创建对象-关系映射文件 ④通过hibern…

Day17_学点JavaEE_转发、重定向、Get、POST、乱码问题总结

1 转发 转发&#xff1a;一般查询了数据之后&#xff0c;转发到一个jsp页面进行展示 req.setAttribute("list", list); req.getRequestDispatcher("student_list.jsp").forward(req, resp);2 重定向 重定向&#xff1a;一般添加、删除、修改之后重定向到…

Pandas部分应掌握的重要知识点

目录 Pandas部分应掌握的重要知识点一、DataFrame数据框的创建1、直接基于二维数据创建&#xff08;同时使用index和columns参数&#xff09;2、基于excel文件中的数据来创建 二、查看数据框中的数据和联机帮助信息1、查看特殊行的数据2、查看联机帮助的两种常见方法&#xff0…

Python制作下载图片的脚本

如果你感觉有收获&#xff0c;欢迎给我微信扫打赏码 ———— 以激励我输出更多优质内容 需求: 今天遇到一个需求,需要下载一个网站上连续的图片素材,一开始一个一个下载太麻烦,于是制作了一个python脚本快速下载 操作: import os #【os模块常用功能】文件的目录、路径操作…

HashMap的常见问题

Entry中的hash属性为什么不直接使用key的hashCode()返回值呢&#xff1f; 不管是JDK1.7还是JDK1.8中&#xff0c;都不是直接用key的hashCode值直接与table.length-1计算求下标的&#xff0c;而是先对key的hashCode值进行了一个运算&#xff0c;JDK1.7和JDK1.8关于hash()的实现…

学习数通HCIE选择誉天有什么优势?

誉天数通课程亮点 课程内容详实&#xff0c;千万级实训环境 涵盖数通技术全场景热门技术&#xff0c;涉及传统园区网&#xff0c;虚拟化园区网&#xff0c;广域互联技术&#xff0c;数据中心网络&#xff0c;网络自动化运维 专业机房环境&#xff0c;全真机教学演示&#xf…

【JavaEE初阶系列】——网络编程 TCP客户端/服务器 程序实现

目录 &#x1f6a9;TCP流套接字编程 &#x1f36d;ServerSocket API &#x1f36d;Socket API &#x1f36d;TCP服务器 &#x1f36d;TCP客户端 &#x1f6a9;TCP流套接字编程 俩个关键的类 ServerSocket (给服务器使用的类&#xff0c;使用这个类来绑定端口号&#xff0…

2024接口自动化测试入门基础知识【建议收藏】

接口自动化测试是指通过编写测试脚本和使用相关工具&#xff0c;对软件系统的接口进行自动化测试的过程。 今天本文从4个方面来介绍接口自动化测试入门基础知识 一、接口自动化测试是什么&#xff1f; 二、接口自动化测试流程&#xff1f; 三、接口自动化测试核心知识点有那些…

MySQL一些特殊功能的索引(6/16)

特殊功能性索引 B-Tree索引&#xff1a; InnoDB的默认索引类型&#xff0c;适用于多种查询操作。 可以用于等值查询、范围查询和索引列的组合查询。 创建B-Tree索引的示例&#xff1a; CREATE INDEX index_name ON table_name (column1, column2);全文索引&#xff08;FULLTEX…

力扣207.课程表

你这个学期必须选修 numCourses 门课程&#xff0c;记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出&#xff0c;其中 prerequisites[i] [ai, bi] &#xff0c;表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如…

基于springboot实现教师人事档案管理系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现IT技术交流和分享平台系统演示 摘要 我国科学技术的不断发展&#xff0c;计算机的应用日渐成熟&#xff0c;其强大的功能给人们留下深刻的印象&#xff0c;它已经应用到了人类社会的各个层次的领域&#xff0c;发挥着重要的不可替换的作用。信息管理作为计算…

事务,MySQL函数和索引详解

文章目录 事务简介提交方式手动提交事务 事务执行流程修改事务的默认提交方式 事务原理四大特性隔离级别 MySQL函数常见的日期函数判断函数case when字符串函数数字函数 MySQL性能(了解)索引概念分类MySQL索引语法数据结构(了解)BTreeBTree好处 优缺点优势劣势 创建原则 事务简…

python中time库的time.time()函数的作用是什么?

python中time库的time.time()函数的作用是什么&#xff1f; 作用&#xff1a;Python time time() 返回当前时间的时间戳&#xff08;1970纪元后经过的浮点秒数&#xff09;。 time()方法语法&#xff1a;time.time() #!/usr/bin/python # Write Python 3 code in this onlin…