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

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

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

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

我们下期不见不散~~

​​​​

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2024/4/5—力扣—下一个排列

2024/4/5—力扣—下一个排列

代码实现&#xff1a; 思路&#xff1a;两遍扫描 void swap(int *a, int *b) {int t *a;*a *b;*b t; }void reverse(int *nums, int l, int r) {while (l < r) {swap(nums l, nums r);l;r--;} }void nextPermutation(int *nums, int numsSize) {int i numsSize - 2;wh…
阅读更多...
手把手从零搭建ChatGPT网站midjourney-AI绘画系统，附详细搭建部署教程文档

手把手从零搭建ChatGPT网站midjourney-AI绘画系统，附详细搭建部署教程文档

一、系统前言 SparkAi创作系统是基于ChatGPT进行开发的Ai智能问答系统和Midjourney绘画系统&#xff0c;支持OpenAI-GPT全模型国内AI全模型。本期针对源码系统整体测试下来非常完美&#xff0c;那么如何搭建部署AI创作ChatGPT&#xff1f;小编这里写一个详细图文教程吧。已支持…
阅读更多...
前端开发攻略---用JavaScript打造炫酷数字变化动画效果：手写实现你的自定义动画函数！支持更改任意数字、动画速度

前端开发攻略---用JavaScript打造炫酷数字变化动画效果：手写实现你的自定义动画函数！支持更改任意数字、动画速度

1、演示 2、介绍 这篇文章将向您展示如何使用JavaScript来创建一个自定义的动画函数&#xff0c;以实现数字变化效果。我们将深入了解前端动画的本质&#xff0c;并通过手写代码来实现这个炫酷的数字变化动画效果。您将学到如何利用JavaScript来操作DOM元素&#xff0c;控制动画…
阅读更多...
知名专业定制线缆源头工厂推荐-精工电联：智能制造线缆的前沿技术探索

知名专业定制线缆源头工厂推荐-精工电联：智能制造线缆的前沿技术探索

优质定制线缆源头厂家推荐-精工电联&#xff1a;智能制造线缆的前沿技术探索 知名专业定制线缆源头工厂推荐-精工电联&#xff1a;智能制造线缆的前沿技 在科技飞速发展的当今时代&#xff0c;智能制造已成为工业4.0的核心驱动力。精工电联&#xff0c;作为智能制造领先的高品质…
阅读更多...
Pycharm中 Console 打不开

Pycharm中 Console 打不开

引言&#xff1a; 近年来&#xff0c;越来越多的高校洞察到了Pycharm为代表的编程IDE软件的重要性&#xff0c;已经购买了对应的版权。对于这些软件的使用&#xff0c;许多本科生可能还比较陌生&#xff0c;这系列博客主要总结了一些常见的BUG及对应的解决方案。本篇博客主要总…
阅读更多...
核心api实操-Activiti7从入门到专家（5）

核心api实操-Activiti7从入门到专家（5）

背景 上一节已经搭建了&#xff0c;具体的开发环境&#xff0c;数据库&#xff0c;并且找了一个可以用bpmnjs流程设计器&#xff0c;这一些&#xff0c;我们对核心api做个基础的实操&#xff0c;有个感性的认知&#xff0c;另外对数据库和基本数据流动有个理解。 部署 模板部…
阅读更多...
Java | Leetcode Java题解之第17题电话号码的字母组合

Java | Leetcode Java题解之第17题电话号码的字母组合

题目&#xff1a; 题解&#xff1a; class Solution {public List<String> letterCombinations(String digits) {List<String> combinations new ArrayList<String>();if (digits.length() 0) {return combinations;}Map<Character, String> phoneM…
阅读更多...
open-sora

open-sora

Open-Sora&#xff0c;高效复现类Sora视频生成方案开源&#xff01;魔搭社区最佳实践教程来啦&#xff01;https://mp.weixin.qq.com/s/WMQIDgZs2MBPGtx18XSXgw Open-Sora开源方案讲解开源但“平替”的方案。https://mp.weixin.qq.com/s/nPYCzgBA7hIsPZ6PCyXxKQOpen-Sora/docs…
阅读更多...
Qt信号与槽

Qt信号与槽

我们在使用Qt的时候&#xff0c;不使用Qt Designer 的方式进行开发&#xff0c;使用ui文件&#xff0c;信号与槽的连接方式是生成代码之后才能在setupUi函数里才能看到&#xff0c;或者需要进入Ui设计器里的信号槽模式里才能看到信号槽的连接。所以我们最好使用代码绘制界面。 …
阅读更多...
CCD机器视觉在工业生产中起到什么作用？

CCD机器视觉在工业生产中起到什么作用？

CCD机器视觉尺寸测量是基于相对测量方法&#xff0c;通过可追溯性、放大校准、自动边缘提升和屏幕图像测量来计算实际尺寸。在精密测量中&#xff0c;放大倍数必须达到35倍或更高&#xff0c;才能达到微米级的精度。此时&#xff0c;视线宽度小于5mm。对于大于5mm的物体&#x…
阅读更多...
游戏提示找不到steam_api64.dll，无法继续执行代码的解决方法

游戏提示找不到steam_api64.dll，无法继续执行代码的解决方法

在我们日常沉浸在电脑世界中&#xff0c;尽情享受各类电子游戏带来的精彩与刺激时&#xff0c;偶尔会遭遇一些令人困扰的技术问题。这次&#xff0c;当您正全神贯注地启动心仪的游戏&#xff0c;期待着新一局冒险或竞技的开始&#xff0c;电脑屏幕上却冷不防地弹出一条警示信息…
阅读更多...
--每周分享--

--每周分享--

分享内容&#xff1a; 1.单链表的归并排序 2.一道有趣的思考题 分享细节&#xff1a; 单链表的归并排序 主要思想&#xff1a;递归 怎么理解&#xff1f;下面具体说明&#xff1a; 1.首先&#xff0c;我从整体的思考步骤说明&#xff1a;先分区&#xff0c;再排序&#…
阅读更多...
游标的定义和类型

游标的定义和类型

Oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 游标的基本概念 游标从字面上理解为游动的光标&#xff0c;可以使用 Excel 表格来想象游标的作用&#xff0c;游标指向每一行&#xff0c;通过游标访问每行数据。 在 Orac…
阅读更多...
二维相位解包理论算法和软件【全文翻译- 菲林(Flynn)最小不连续性方法（4.5）】

二维相位解包理论算法和软件【全文翻译- 菲林(Flynn)最小不连续性方法（4.5）】

4.5 菲林最小不连续性方法 在迄今为止对路径跟踪算法的讨论中，我们忽略了一种非常自然的方法，现在我们将对其进行描述。如果我们仔细观察图 4.42(a)中包裹相位数据中的条纹图案，就会发现 "条纹线 "或最亮像素和最暗像素之间的边界标志着从 0 到 2π 的过渡，它们…
阅读更多...
【LAMMPS学习】八、基础知识(1.5) LAMMPS 库接口

【LAMMPS学习】八、基础知识(1.5) LAMMPS 库接口

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…
阅读更多...
react17中配置webpack：使用@代表src目录

react17中配置webpack：使用@代表src目录

在vue的项目中可以使用表示src目录&#xff0c;使用该符号表示绝对路径&#xff0c;那么在react中想要使用怎么办呢&#xff1f; 在react中使用表示src目录是需要在webpack中配置的&#xff0c;在核心模块node_modules-》react-scripts-》config-》webpack.config.js中搜索找到…
阅读更多...
城市内涝与海绵城市规划设计中的水文水动力模拟

城市内涝与海绵城市规划设计中的水文水动力模拟

原文链接&#xff1a;城市内涝与海绵城市规划设计中的水文水动力模拟https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247601198&idx5&sn35b9e5e3961ea2f190f9742236a7217f&chksmfa820dc9cdf584df97633f64d19bdc3e5f7d1a5a85000c8f040e1953c51b9b39c87b5…
阅读更多...
【Linux】Socket编程接口 | 实现简单的UDP网络程序

【Linux】Socket编程接口 | 实现简单的UDP网络程序

文章目录 一、预备知识理解源IP地址和目的IP地址理解源mac地址和目的mac地址认识端口号理解源端口号和目的端口号理解“端口号&#xff08;PORT&#xff09;”和“进程ID&#xff08;PID&#xff09;” 认识TCP和UDP协议TCP协议UDP协议 网络字节序为什么网络字节序采用的是大端…
阅读更多...
华媒舍：7种方式，打造出旅游媒体套餐

华媒舍：7种方式，打造出旅游媒体套餐

现如今&#xff0c;伴随着旅游业发展与繁荣&#xff0c;更多旅游业发展从业人员越来越重视产品营销品牌基本建设&#xff0c;希望可以将自己的度假旅游产品和服务营销推广给更多的潜在用户。而建立一个优秀的旅游业发展媒体套餐内容品牌是吸引目标客户的重要步骤。下面我们就详…
阅读更多...
6.3Python之字典的内置方法

6.3Python之字典的内置方法

1、创建字典 dict.fromkeys() &#xff1a;可将列表、元组、集合转为字典 knowledgeL [语文, 数学, 英语] scoresD1 dict.fromkeys(knowledgeL, 60) print(scoresD1) knowledgeT (Chinese, Math, English) scoresD2 dict.fromkeys(knowledgeT, 60) print(scoresD2) knowl…
阅读更多...
最新文章

Copyright @ 2022~2023