“捡到一束光，日落时还给太阳”

数据结构初阶题解

  • 1.移除元素
  • 2.合并两个有序数组
  • 3.移除链表元素
  • 4.反转链表
  • 5.合并两个有序链表
  • 6.链表的中间结点
  • 7.环形链表的约瑟夫问题
  • 8.分割链表
  • 有感：其实我早就死了，死在破碎的三观里；死在飘渺的理想里；死在幻想的感情里；死在虚无的回忆里。但我好像我还活着，活在生活的压力里；活在社会的角落里；活在亲人的期盼里；活在儿时的梦里。

最近笔者在初学数据结构时遇到几道题目，做完后有些吃力，很多经验还没有总结，笔者打算针对这几道题目进行系统性的总结。由于笔者是个菜鸟，思路还没有那么熟练清晰，后续还会加以完善，大佬轻喷。另外欢迎各位大佬指出不足。

1.移除元素

题目来源：https://leetcode.cn/problems/remove-element/description/

题目原文：

在这里插入图片描述

题意解析：

给定一个数组和一个数值，要求删除数组中等于该数值的元素，并返回删除后数组的新长度。
注意：不能创建新数组来操作，以及删除后数组里的元素可以任意位置排序。

个人思路：

首先最开始的思路是创建一个新数组，然后遍历原数组，将不为删除的值的元素放到新数组中。但是题目要求不能创建新数组，所以这种思路在本题不适用。
第二种思路是在原数组中进行操作遍历删除。此方法也叫双指针法。
（1）创建两个指针src、dist,它们都指向第一个元素
（2）src遍历原数组，若元素 = 删除的值，src++
若元素 != 删除的值，nums[dist] = nums[src],dist++,src++
（3）src遍历完数组，循环结束，此时数组为新的数组。

还需要注意一点的是本题目要求返回新数组的长度，需要返回一个整形，所以我们使用数组下标的形式来写代码，本质上无疑异，方便做题。

个人代码：

int removeElement(int* nums, int numsSize, int val) 
{
    int src,dst;
    src = dst = 0;//初始化第一个元素下标为0
    while(src < numsSize)
    {
        if(nums[src] == val)
        {
            src++;
        }
        else
        {
            nums[dst] = nums[src];
            src++;
            dst++;
        }
    }
    return dst;//此时下标dst就是新数组的长度
}

2.合并两个有序数组

题目来源：https://leetcode.cn/problems/merge-sorted-array/description/

题目原文：

在这里插入图片描述

题意解析：

给定两个递增的数组，然后合并两个数组，要求新数组中元素也是递增的。

个人思路：

第一开始的思路是先把两个元素放到一个数组中去，然后在一个数组中进行冒泡排序。
但此方法代码量大，程序效率低。

第二种思路是比大小，两个数组中的元素比大小，从后往前比大小，元素大的往后放。在这个方法中不要遗漏了关键点，就是比大小的时候，两个数组都是递增的。

个人代码：

	 int l1 = m - 1;
     int l2 = n - 1;
     int l3 = m + n - 1;
     while(l1 >= 0 && l2 >= 0)
     {
         if(nums1[l1] > nums2[l2])
         {
             nums1[l3--] = nums1[l1--];
         }
         else
         {
             nums1[l3--] = nums2[l2--];
         }
     }
     while(l2 >= 0)//结束条件是第二个数组中的元素全都遍历到第一个元素中去
     {
        nums1[l3--] = nums2[l2--];
     }

3.移除链表元素

题目来源：https://leetcode.cn/problems/remove-linked-list-elements/description/

题目原文：

在这里插入图片描述

题意解析：

给定一个链表和节点的值，删除给定节点，返回新链表。

个人思路：

第一种思路是创建新链表，将不为给定删除的节点放到新链表中。

第二种思路是在原链表中进行删除操作。

特别注意链表可以是空链表，这点需要特别思考。

个人代码：

1.创建新链表
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    typedef struct ListNode ListNode;
    
    ListNode* newhead,*newtail;
    newhead = newtail = NULL;
    ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val != val)
        {
            if(newhead == NULL)//新链表为空链表
            {
                newhead = newtail = pcur;
            }
            else
            {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail)//此时需要将新链表的尾节点置为空，不然会死循环。
    {
        newtail->next = NULL;
    }
    return newhead;

2.遍历原链表，删除指定位置链表
struct ListNode* removeElements(struct ListNode* head, int val) 
{
    typedef struct ListNode ListNode;
    while ( NULL != head & head->val == val) //判断头节点是否为空节点
    {
        head = head->next;
    }//此时头节点不可能是val了
    if (NULL == head) {
        return head;
    }
    ListNode* pcur = head->next; 
    ListNode* prev = head;
    while(pcur)
    {
        
        if(pcur->val == val)
        {
    		ListNode* Next = pcur->next;
            prev->next = Next;
            pcur = Next;
            
        }
        else
        {
            prev = pcur;
            pcur = pcur->next;
            
        }
        
    }
    return head;
}

4.反转链表

题目来源：https://leetcode.cn/problems/reverse-linked-list/description/

题目原文：

在这里插入图片描述
提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

题意解析：

给定一个链表，现将原链表的头尾顺序倒置，然后输出。

个人思路：

第一个思路是创建新链表，将原链表的节点头插到新链表中，这样就实现了
第二个思路是使用三个指针,完成链表翻转，此方法难以想到，需要多加注意。

个人代码：

2.三个指针,完成链表翻转
    if(head == NULL)
    {
        return head;
    }
    ListNode* n1,*n2,*n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;//改变n2的指向
        n1 = n2;
        n2 = n3;
        if(n3)
        {
            n3 = n3->next;
        }
        
    }
    return n1;


1.创建新链表，进行头插操作
struct ListNode* reverseList(struct ListNode* head) 
{
    typedef struct ListNode ListNode;
    //1.遍历头插
    ListNode* pcur = head;
    ListNode* newhead = NULL;
    ListNode* newtail = NULL;
    while(pcur)
    {
        if(newhead == NULL)
        {
            newhead = newtail = pcur;
            pcur = pcur->next;
        }
        else
        {
            ListNode* next = pcur->next;
            pcur->next = newhead;
            newhead = pcur; 
            pcur = next;
        }
        
        
    }
    if(newtail)
    {
        newtail->next = NULL;
    }
    return newhead;

5.合并两个有序链表

题目来源：https://leetcode.cn/problems/merge-two-sorted-lists/description/

题目原文：

在这里插入图片描述
提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

题意解析：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

个人思路：

创建新的空的链表，遍历原链表，将节点值小的拿到新链表中进行尾插操作。遍历的结果只有两者情况：第一个链表为空或者第二个链表为空。

个人代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
    typedef struct ListNode ListNode;
    ListNode* l1 = list1;
    ListNode* l2 = list2;
    if(list1 == NULL)//判断原链表是否为空
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    ListNode* newhead,*newtail;//创建新链表
    newhead = newtail = (ListNode*)malloc(sizeof(ListNode));//创建哨兵位，不必再判断新链表是否为空
    while(l1 && l2)
    {
        if(l1->val < l2->val)
        {
            newtail->next = l1;
            newtail = newtail->next;
            l1 = l1->next;
        }
        else
        {
            newtail->next = l2;
            newtail = newtail->next;
            l2 = l2->next;
        }
    }
    if(l1)
    {
        newtail->next = l1;
    }
    if(l2)
    {
        newtail->next = l2;
    }
    ListNode* ret = newhead->next;
    free(newhead);
    newhead = NULL;
    return ret;
}

6.链表的中间结点

题目来源：https://leetcode.cn/problems/middle-of-the-linked-list/description/

题目原文：

在这里插入图片描述

题意解析：

给定单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

个人思路：

快慢指针法：slow每次走一步，fast每次走两步
（1）若节点为奇数个，循环条件是fast->next== NULL，此时slow指向的是中间节点
（2）若节点为偶数个，循环条件是fast==NULL, 此时slow指向的是中间节点

个人代码：

struct ListNode* middleNode(struct ListNode* head) 
{
    typedef struct ListNode ListNode;
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

7.环形链表的约瑟夫问题

题目来源：https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a

题目原文：

在这里插入图片描述

题意解析：

编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
下一个人继续从 1 开始报数。n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

个人思路：

创建环形链表，遍历链表，计数计到m的节点销毁。直到链表只剩一个节点时退出循环

个人代码：

typedef struct ListNode ListNode;
 ListNode* buynode(int x)
 {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    if(node == NULL)
    {
        exit(1);
    }
    node->val = x;
    node->next = NULL;
    return node;
 }
 ListNode* createcic(int n)
 {
    //创建第一个节点
    ListNode* phead = buynode(1);
    ListNode* ptail = phead;
    for(int i = 2;i <= n;i++)
    {
        ptail->next = buynode(i);
        ptail = ptail->next;
    }
    ptail->next = phead;
    return ptail;
 }
int ysf(int n, int m ) 
{
    //1.创建带环链表
    ListNode* prev = createcic(n);
    //2.遍历链表，删除节点
    ListNode* pcur = prev->next;
    int count = 1;
    while(pcur->next != pcur)
    {
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;

        }
        else 
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

8.分割链表

题目来源：https://leetcode.cn/problems/partition-list-lcci/description/

题目原文：

在这里插入图片描述

题意解析：

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。你不需要 保留 每个分区中各节点的初始相对位置。

个人思路：

第一种思路在原链表上进行修改，遍历原链表，若节点的值大于或等于x，尾插再原链表后，然后删除旧的链表。
此方法需要定义多个指针变量，删除链表需要定义prev指针，尾插需要定义新的尾部变量。

第二种思路是创建大小链表，分别遍历大、小链表，然后将小链表的尾节点和大节点的第一个节点首位相连。

个人代码：

struct ListNode* partition(struct ListNode* head, int x)
{
    typedef struct ListNode ListNode;
    if(head == NULL)
    {
        return head;
    }
    //创建两个带头链表
    ListNode* lesshead,*lesstail;
    ListNode* bighead,*bigtail;
    lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));
    bighead = bigtail = (ListNode*)malloc(sizeof(ListNode));
    //遍历原链表，将原链表中的节点尾插到大小链表中
    ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val < x)
        {
            //尾插到小链表中
            lesstail->next = pcur;
            lesstail = lesstail->next;
        }
        else
        {
            //尾插到大链表中
            bigtail->next = pcur;
            bigtail = bigtail->next;
        }
        pcur = pcur->next;
    }
    //将bigtail->next初始化的同时还置为NULL，防止死循环
    bigtail->next = NULL;
    //首位相连
    lesstail->next = bighead->next;
    
    ListNode* ret = lesshead->next;
    free(lesshead);
    free(bighead);
    lesshead = bighead = NULL;
    return ret;
}

完。。。

有感：其实我早就死了，死在破碎的三观里；死在飘渺的理想里；死在幻想的感情里；死在虚无的回忆里。但我好像我还活着，活在生活的压力里；活在社会的角落里；活在亲人的期盼里；活在儿时的梦里。

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

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

相关文章

[AHK]自定义消息实现两个脚本之间通信

[AHK]自定义消息实现两个脚本之间通信

自己编写的两个脚本&#xff0c;用自定义消息实现&#xff0c;一个脚本控制另一个脚本&#xff0c;让被控脚本挂起或退出。 从aaa.ahk向bbb.ahk发送一个消息&#xff0c;bbb.ahk捕获消息后再进行处理&#xff0c;比如&#xff1a; 从aaa.ahk中向bbb.ahk发送特定的数字&#xff…
阅读更多...
gpt-6有望成为通用工具

gpt-6有望成为通用工具

OpenAI CEO山姆奥特曼&#xff08;Sam Altman&#xff09;在最新的博客访谈中&#xff0c;提到gpt-6有望成为通用工具。 奥特曼还认为&#xff0c;目前的模型不够聪明&#xff0c;“使用GPT-2进行科学研究曾被认为是不切实际的想法。而如今&#xff0c;虽然人们使用GPT-4进行科…
阅读更多...
短视频评论ID批量爬虫提取获客软件|DY评论下载采集工具

短视频评论ID批量爬虫提取获客软件|DY评论下载采集工具

短视频评论批量抓取软件&#xff1a;智能拓客&#xff0c;精准抓取用户反馈 在当今数字化营销时代&#xff0c;了解用户的需求和反馈对于企业的发展至关重要。而作为流行的短视频平台&#xff0c;短视频评论蕴含了丰富的用户信息和市场洞察。为了帮助企业高效获取这些宝贵数据…
阅读更多...
一秒内传输50万对纠缠光子？！纽约市量子网络刷新纪录

一秒内传输50万对纠缠光子？！纽约市量子网络刷新纪录

量子网络技术行业的领军企业Qunnect宣布&#xff0c;在纽约市的GothamQ网络上&#xff0c;其偏振量子比特的传输性能刷新了纪录。Qunnect利用现有的商用光缆实现了每秒传输50万对高保真度纠缠光子的速率&#xff0c;且该网络的正常运行时间超过了99%。 纽约34公里长的GothamQ量…
阅读更多...
LIUNX文件系统

LIUNX文件系统

目录 1.磁盘的物理结构 2.CHS定位法 3.磁盘的逻辑存储 4.系统层面 inode.block[15] 创建文件的流程 查找文件的流程 了解文件系统&#xff0c;首先要了解磁盘是如何存储和读取数据的。 1.磁盘的物理结构 可以理解这个盘上有很多的小磁铁&#xff0c;通过旋转盘面和摆动…
阅读更多...
C# 整数转罗马数字

C# 整数转罗马数字

罗马数字包含以下七种字符:I&#xff0c;V&#xff0c;X&#xff0c;L&#xff0c;C,D和M。 例如&#xff0c;罗马数字2写做 II &#xff0c;即为两个并列的 1。12 写做XII&#xff0c;即为XII。27写做 XXVII,即为XXV II 。 通常情况下&#xff0c;罗马数字中小的数字在大的数字…
阅读更多...
显示msvcp140.dll丢失要如何解决？这5种方法高效修复msvcp140.dll

显示msvcp140.dll丢失要如何解决？这5种方法高效修复msvcp140.dll

msvcp140.dll是Microsoft Visual C Redistributable软件包中的一个文件&#xff0c;主要用于支持使用C编程语言编写的软件的正常运行。如果你的电脑出现缺少msvcp140.dll的错误消息&#xff0c;可能会影响到某些程序的启动和运行。然而&#xff0c;不必过度担心&#xff0c;因为…
阅读更多...
【SQL每日一练】分组过滤练习题

【SQL每日一练】分组过滤练习题

文章目录 前言MySQL语法注意&#xff1a; 前言 题目&#xff1a;现在运营想查看每个学校用户的平均发贴和回帖情况&#xff0c;寻找低活跃度学校进行重点运营&#xff0c;请取出平均发贴数低于5的学校或平均回帖数小于20的学校。 drop table if exists user_profile; CREATE …
阅读更多...
JavaSE：继承 多态

JavaSE：继承 多态

继承 继承的本质 子类能够使用父类的方法和变量 使用场景&#xff1a;代码复用 在一个类中实现了一个很复杂的方法&#xff0c;给一个新类重新实现这个方法&#xff0c;我们直接继承即可 public class Student {public String sno;public void study() {System.out.printl…
阅读更多...
2024妈妈杯数学建模思路A题思路汇总分析 MathorCup建模思路分享

2024妈妈杯数学建模思路A题思路汇总分析 MathorCup建模思路分享

C题&#xff1a;移动通信网络中PCI规划问题 &#xff08;完整版内容放在文末了&#xff09; 2024MathorCup A题完整思路完整数据可执行代码后续高质量成品论文 l 难度评分: 3.5/5 l 开放度评分: 3/5 l 适合专业: 通信工程、计算机科学、电子工程 l 主要算法: 图论算法、…
阅读更多...
02 - Git 之命令 + 删除 + 版本控制 + 分支 + 标签 + 忽略文件 + 版本号

02 - Git 之命令 + 删除 + 版本控制 + 分支 + 标签 + 忽略文件 + 版本号

1 Git相关概念 1.1 以下所谈三个区&#xff0c;文件并不只是简单地在三个区转移&#xff0c;而是以复制副本的方式转移 使用 Git 管理的项目&#xff0c;拥有三个区域&#xff0c;分别是 Working area工作区&#xff08;亦称为 工作树Working Tree&#xff09;、stage area …
阅读更多...
vscode按ctrl+鼠标左键没反应

vscode按ctrl+鼠标左键没反应

vscode按ctrl鼠标左键没反应 问题问题解决 问题 新买的阿里云服务器,在连接vscode后,按ctrl鼠标左键没反应,怎么办? 问题解决 你没有在vscode上安装c的相关插件,安装之后才可以实现按ctrl鼠标左键跳转到函数的定义
阅读更多...
书生·浦语大模型第二期实战营（4）笔记

书生·浦语大模型第二期实战营（4）笔记

Finetune 为什么要微调 适应下游任务 两种微调范式 上面的是增量训练 下面的是指令微调 数据格式 微调方案 lora&#xff1a; 在基座模型的基础上再套用一个小模型 XTuner 简介 快速上手 LnternLM2 1.8B 多模态LLM
阅读更多...
springdoc-openapi使用

springdoc-openapi使用

springdoc-openapi使用 一、引入pom二、新增配置类OpenApiConfig四、Controller层示例五、配置文件新增内容六、验证 一、引入pom <dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-ui</artifactId><version>1…
阅读更多...
IT如何与业务双向奔赴，高效并驱共“盈”企业发展

IT如何与业务双向奔赴，高效并驱共“盈”企业发展

随着经济和技术的飞速发展&#xff0c;在当前数字化时代中&#xff0c;如何进行有效的数字化转型、运用新技术&#xff0c;特别是让AI技术融入企业的具体业务场景、快速实现应用场景的落地、确保企业不落后于时代发展&#xff0c;是每一位CIO都会面临的一项挑战。 IT部门在企业…
阅读更多...
Centos7.9 脚本一键部署nextcloud，配置Nginx代理Https。

Centos7.9 脚本一键部署nextcloud，配置Nginx代理Https。

目录 一键安装nextcloud 出现错误TypeError Cannot read properties of undefined (reading ‘writeText‘) 生成自签名SSL证书 编辑Nginx配置文件 启动Nginx 一键安装nextcloud 本脚本参考文章&#xff0c;本文较长建议先看完在操作&#xff01;&#xff01;&#xff01;…
阅读更多...
基于数据库现有表导出为设计文档

基于数据库现有表导出为设计文档

1.查询 SELECTCOLUMN_NAME 字段名,COLUMN_COMMENT 字段描述,COLUMN_TYPE 字段类型,false as 是否为主键 FROMINFORMATION_SCHEMA.COLUMNS wheretable_NAME region -- 表名2.查询结果 3.导出为excel
阅读更多...
考研OSchap1计算机系统概述

考研OSchap1计算机系统概述

目录 一、概念 p1 二、功能 p3 1.作为计算机资源的管理者 &#xff08;1&#xff09;文件管理 &#xff08;2&#xff09;存储器管理 &#xff08;3&#xff09;处理机管理 &#xff08;4&#xff09;设备管理 2.作为用户与计算机硬件系统之间的接口 &#xff08;1&…
阅读更多...
VMware与新插入的虚拟机 版本不兼容解决方法

VMware与新插入的虚拟机 版本不兼容解决方法

1、找到虚拟机目录文件 2、用记事本打开修改版本号&#xff08;找到虚拟机版本号&#xff09; 3、如图所示为版本15的型号 4、修改virtualHW.version "15"&#xff08;引号里面对应上面版本号&#xff09; 5、修改成功
阅读更多...
UKP3d，AutoPDMS设置埋地数据导出至AutoPSA的查看方法

UKP3d，AutoPDMS设置埋地数据导出至AutoPSA的查看方法

一用户在设置了埋地数据&#xff0c;导出至AutoPSA未有数据。具体操作方法如下&#xff1a; AutoPSA里提供两种埋地计算&#xff0c;一是仿start计算&#xff1b;二是仿CII计算 1.AutoPSA10.0仿start计算新埋地模块的操作方法&#xff1a; AutoPSA10.0新埋地模块需要用户根据实…
阅读更多...
最新文章

Copyright @ 2022~2023