【数据结构】顺序表和链表经典题目

devtools/2024/9/22 17:37:28/

系列文章目录

链表
动态顺序表实现通讯录
顺序表


文章目录

  • 系列文章目录
  • 前言
  • 一、顺序表经典例题
    • 1. 移除元素
    • 2. 合并两个有序数组
  • 二、链表经典例题
  • 总结


前言

我们通过前面对顺序表和链表的讲解,让大家对它们有了基本了解。下面是对于这两个知识点的一些经典例题的讲解,让大家更好熟悉它们。


提示:以下是本篇文章正文内容,下面案例可供参考

一、顺序表经典例题

1. 移除元素

题目链接:移除元素
题目要求:
题目要求
题目示例
题目的要求十分简单:将nums数组中val的值得元素移除,并返回移除后nums数组中剩余元素的大小。
题目解法:

  1. 暴力解法:我们看到这道题目自然就会想到一种暴力解法,我们从头开始遍历这个数组,当遇到元素值与val相等,将该元素后面的元素全部向前移动一位,然后再从该位置接着遍历判断,直到到数组末尾。------------------ 这种解法的代码很容易实现,这里不实现。对于这个解法,我们很清楚的看到将数组元素往前移这个做法十分浪费时间,时间复杂度只有O(N^2),那么我们怎么减少它的时间呢?
  2. 双指针解法:(这里我们第一次提到这种解法,解释一下:双指针解法是用两个指针解决问题,但这两个指针并不一定是指针变量,也可以整型变量等等,但能通过这两个变量指向某个地址,下面会有展示)----------------------------- 首先,我们肯定需要一个指针能遍历整个数组,还要一个指向符合要求的数组,由于数组可以通过[]访问元素,我们这里定义了两个int类型:front,low(front用来遍历),它们开始都指向第一个元素。
    在这里插入图片描述

在遍历时会遇到两种情况:1. front指向的元素不等于val值,这时我们让front指向的元素赋值给low指向的元素,然后front,low都++;2. front指向的元素等于val值,直接front++。通过这两幅图帮助大家理解为什么这么做就能完成。
在这里插入图片描述
在这里插入图片描述
最后,当front走到最后,low+1就是我们需要的k值。
代码示例:

int removeElement(int* nums, int numsSize, int val) {int front = 0;int low = 0;for(front = 0; front < numsSize; front++){if(nums[front] != val){nums[low] = nums[front];low++;}}return low;
}

2. 合并两个有序数组

题目链接:合并两个有序数组
题目要求:
在这里插入图片描述
在这里插入图片描述
题目解法:

  1. 暴力解法:定义两个int类型n1,n2分别指向nums1,nums2,有两种情况:1. n1指向的元素大于n2指向的元素,将n1指向的元素及其后面的后移一位,将n2指向的元素插入n1指向的位置,然后n1++,n2++;2. n1指向的元素小于等于于n2指向的元素,直接n1++,但l1到了m时,l2还没到末尾,直接将l2后面的值赋值到l1后面,直至n2到最后。----------------- 这种解法同样耗时,O(N^2)。
  2. 逆向三指针:暴力解法使用了双指针,但是是正向的,我们发现正向无法快速解决问题时,不妨思考逆向解决。l1指向nums1最后一个有效数据,l2指向nums2最后一个元素,l3指向nums1最后一个元素。
    在这里插入图片描述
    同样会遇到两种情况:1. l1和l2指向的元素那个更大,就让l3指向的元素等于更大的那个,相等则随便哪个;2. 当其中一个小于0时,则让l3指向的元素等于另一个,直至另一个小于0。
    在这里插入图片描述
    代码示例:
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {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];l1--;l3--;}else{nums1[l3] = nums2[l2];l2--;l3--;}}while(l2 >= 0){nums1[l3] = nums2[l2];l2--;l3--;}
}

二、链表经典例题

1. 移除链表元素

题目链接:移除链表元素
题目要求:
在这里插入图片描述

题目解法:

  1. 暴力解法:我们遍历整个链表,当遇到与val相等的值,我们需要知道当前节点的上一个节点,并找到下一个不等于val的值得节点,时间复杂度只要O(N)。
  2. 新建链表:题目没有要求在该链表上修改,我们可以创建一个新链表,只需要将不等于val值得节点插入到该新链表即可,不需要得到该节点的上一个节点,回踩的坑比上面的解法更少。这个思路的代码很容易实现,我这直接给代码了。
    代码示例:
typedef struct ListNode Listnode;
struct ListNode* removeElements(struct ListNode* head, int val) {Listnode* remove, * relast;remove = relast = NULL;if (head == NULL)return NULL;
Listnode* pcur = head;
while (pcur)
{if (pcur->val == val){pcur = pcur->next;}else{if (remove == NULL){remove = relast = pcur;pcur = pcur->next;}else{relast->next = pcur;relast = pcur;pcur = pcur->next;}}
}
if (relast)relast->next = NULL;return remove;
}

2. 反转链表

题目链接:反转链表
题目要求:
在这里插入图片描述

题目解法:
这题目没啥暴力解法,下面直接讲解我的使用方法:
三指针解法:我们要反转链表,就需要让当前节点的next指向它的上一个节点,同时要能找到它的下一个节点,所以需要三个指针。定义三个指针:prev,pcur,pnext。
prev指向当前节点上一个节点,pcur指向当前节点,pnext指向下一个节点。(我这里将参数head当做一个prev用,大家可以选择自己定义一个prev)
开始时,判断链表是否为空为空则返回NULL,否则pcur等于head,pnext = pcur->next,head->next = NULL,之后进入循环让pcur的next指向head,head等于pcur,pcur = pnext,pnext = pnext->next,直至pcur为空,返回pcur。
代码示例:

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* pcur = head;struct ListNode* pnext = NULL;if(pcur == NULL)return NULL;if(pcur->next == NULL)return head;pcur = pcur->next;pnext = pcur->next;head->next = NULL;while(pcur){pcur->next = head;head = pcur;pcur = pnext;if(pnext != NULL)pnext = pnext->next;}return head;
}

3. 合并两个有序链表

题目链接:合并两个有序链表
题目要求:
在这里插入图片描述

题目解法:

  1. 暴力解法:我们可以选择一个作为主链表,将另一个链表的值插入到主链表中,这样需要不断调整指针指向,虽然思路简单,但容易踩坑。
  2. 新建链表:我们同样可以像上面一样,新建一个链表即可,将指针指向的值更小的那个节点插入到新链表,当一个指针指向NULL时,将另一个指针全部插入到新链表即可。这个代码同样容易实现,这里直接展示代码。
    我的代码中使用了哨兵位,可以使新节点第一个节点不用单独if判断,更便捷。
    代码示例:
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {ListNode *l1=list1;ListNode *l2=list2;ListNode*pos=( ListNode*)malloc(sizeof(ListNode));pos->next=NULL;if(l1==NULL&&l2==NULL){return list1;}ListNode *cur=pos;while(l1&&l2){if(l1->val<l2->val){cur->next=l1;cur=cur->next;l1=l1->next;}else{cur->next=l2;cur=cur->next;l2=l2->next; }}if(l1){cur->next=l1;}if(l2){cur->next=l2;}ListNode *f=pos->next;
free(pos);
return f;
}

4. 链表的中间节点

题目链接:链表的中间节点
题目要求:
在这里插入图片描述

题目解法:

  1. 暴力解法:先遍历一遍链表,得到链表中有多少节点,然后节点 / 2,在从头开始找到该位置的节点即可。
  2. 快慢指针:暴力解法需要遍历两遍,这个解法只遍历一遍就得到结果。我们要找在中间的节点,那么我们只需要定义两个指针:pfast,plow,pfast每次走两个节点,plow每次走一个节点,当pfast为NULL时,plow不就指向中间节点了吗。
    代码示例:
struct ListNode* middleNode(struct ListNode* head) {struct ListNode* plow, *pfast;plow = pfast = head;while(pfast && pfast->next){plow = plow->next;pfast = pfast->next->next;}return plow;
}

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

题目链接:环形链表的约瑟夫问题
题目要求:
在这里插入图片描述

题目解法:
这道题可以使用顺序表,也可以使用链表解决。
对于顺序表,也可定义要求大小的数组并依次赋值,将报数为m的元素赋值为0,循环遍历时,遇到0就跳过,当到数组末尾时,让其重新指向数组开头。
这里我们提供链表的代码,上面的数组提供一种思路。
链表解法:我们创建一个符合题目要求的循环单链表,遇到报数为m的节点,将该节点删除,然后接着报数,当该节点的next指向自己时或计数器为1时,就是最后留下的人的编号。当然,大家也可以选择将报数为m的节点不删除,修改其值即可,与顺序表操作类似,但是链表的删除不需要移动其他节点,并不消耗什么时间。
代码示例:

typedef struct person
{int num;struct person* next;
}Per;
void cirlist(Per** pphead, int n)
{Per* pcur = *pphead;int i = 0;while (n--){Per* newnode = (Per*)malloc(sizeof(Per));if (newnode == NULL){perror("malloc");exit(1);}newnode->num = ++i;newnode->next = NULL;if (*pphead == NULL){*pphead = pcur = newnode;}else {pcur->next = newnode;pcur = newnode;}}pcur->next = *pphead;
}
int count(Per* phead, int m, int n)
{Per* prev = phead;Per* pcur = phead;Per* next = phead->next;int i = 0;while (n != 1){i++;if (i == m){prev->next = next;free(pcur);pcur = NULL;n--;i = 0;}else {prev = pcur;}pcur = next;next = next->next;}return prev->num;
}
int ysf(int n, int m) {// write code herePer* phead = NULL;cirlist(&phead, n);int number = count(phead, m, n);return number;
}

总结

这篇博客,我们讲解了两道顺序表题和五道链表题,最后一道使用了循环链表,希望大家能通过这几道题对顺序表和链表有更深的了解。

谢谢大家观看!!!


http://www.ppmy.cn/devtools/115570.html

相关文章

react + antDesignPro 企业微信扫码登录

效果 实现步骤 1、项目中document.ejs文件引入企微js链接 注意&#xff1a;技术栈是使用的react antDesignPro&#xff0c;不同的技术栈有不同的入口文件&#xff08;如vue在html文件引入&#xff09; <script src"https://wwcdn.weixin.qq.com/node/wework/wwopen/j…

进程间关系与进程守护

一、进程组 1、理解 每一个进程除了有一个进程 ID(PID)之外 还属于一个进程组&#xff0c; 进程组是一个或者多个进程的集合&#xff0c; 一个进程组可以包含多个进程。 每一个进程组也有一个唯一的进程组 ID(PGID)&#xff0c; 并且这个 PGID 类似于进程 ID&#xff0c; 同样…

pytorch 显存分配机制

pytorch 显存分配机制 pyTorch 的显存分配机制旨在高效利用 GPU 的显存&#xff0c;并减少不必要的显存分配和释放操作&#xff0c;从而提高模型训练和推理的性能。以下是 PyTorch 在使用 CUDA 进行显存分配和管理时的一些主要机制和特点&#xff1a; 1. 显存管理的基础 PyT…

【Linux取经之路】Linux项目自动化构建工具-make/makefile git三板斧

目录 关于make和makefile 一个案例 make和makefile的使用 makefile的基本语法 git的使用 关于make和makefile make是 Linux 系统中广泛使用的一个自动化构建工具&#xff0c;它根据用户定义的规则&#xff08;通常保存在一个名为 makefile的文件中&#xff09;来自动编译…

TCP: Textual-based Class-aware Prompt tuning for Visual-Language Model

文章汇总 存在的问题 原文&#xff1a;具有图像特定知识的图像条件提示符号在提升类嵌入分布方面的能力较差。 个人理解&#xff1a;单纯把"a photo of {class}"这种提示模版作为输入是不利于text encoder学习的 动机 在可学习的提示和每一类的文本知识之间建立…

【.NET全栈】ASP.NET实战—基于ASP.NET的求职系统设计与实现

文章目录 前言一、系统总体设计1、系统功能介绍2、系统架构简介 二、数据库设计1、数据表结构2、数据表关系 三、系统核心层设计1、ASP.NET AJAX客户端脚本扩展2、web.config系统配置3、数据访问类的设计4、业务对象类设计 四、表现层技术分析1、ASP.NET AJAX技术的应用2、基于…

扎克伯格的未来愿景:用智能眼镜引领数字社交新时代

Meta Connect 2024大会前夕&#xff0c;创始人马克扎克伯格的90分钟播客访谈&#xff0c;为我们描绘了Meta未来的蓝图。这场访谈&#xff0c;不仅是大会的热身&#xff0c;更是对科技未来的一次深刻洞察。 人工智能 - Ai工具集 - 未来办公人的智能办公生活导航网 扎克伯格的未…

上海泗博EtherNet/IP转PROFIBUS DP网关EPS-320IP成都地铁项目应用案例

背景&#xff1a; 地铁&#xff0c;作为城市的活力脉搏&#xff0c;不仅是衔接城市生活的关键纽带&#xff0c;更是现代城市交通体系中不可或缺的核心组成部分。因此&#xff0c;确保地铁的稳定运行对任何一座城市都至关重要。 上海泗博自动化&#xff0c;作为与成都地铁项目合…