算法提升 (三)基础数据结构

简介: 算法提升 (三)基础数据结构

链表


阅读这篇文章之前需要有初阶数据结构的基础


关于链表的结构如果还有不了解的同学可以参考下我的这篇文章


链表的详细介绍


1. 反转单链表


给定单链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。


这个题目在算法方面其实没有太多的技巧


主要是锻炼下我们的coding能力


我们来看图

98973384de454d2cae8f08c164aac8ba.png


单次的操作大概是这样子的


我们将当前的指针指向前面一个指针 这样子操作就完成啦


后面其实就是迭代操作


prev到pos位置


pos到next位置


next到最后的位置


代码表示如下


struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return NULL;
    }
    // 设置两个种子很 一个前指针一个后指针一个当前指针
    struct ListNode* prev =NULL;
    struct ListNode* pos =head;
    struct ListNode* next =head;
    while(pos)
    {
        next=next->next;
        pos->next = prev;
        prev = pos;
        pos =next;
    }
    return prev;
}


没有什么难度


2. 反转双链表


给定双链表的头节点 head ,请反转链表,并返回反转后的链表的头节点。


这个的思路和前面反转单链表完全一致 按照上面的思路搞就可以


这里不再赘述


3. 删除链表中的重复项


给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。


我们先考虑一种特殊情况 当我们的头就是我们要删除的节点的时候是不是要用头删啊


并且这个时候还需要移动头的位置


直到我们当前的数据不是我们要删除的数据了 是不是头才能确定下来 大家想想看是不是


之后就很简单了


cur找重复项 prev记录前面的值


如果cur是重复项的话 prev就指向cur的next


之后prev走到cur的位置 cur往前跑 不断循环 之后返回head就可以了


代码表示如下


struct ListNode* deleteNode(struct ListNode* head, int val)
{
    // 首先判断 如果整个链表为空 直接返回一个空就好
    if(head==NULL)
    {
        return NULL;
    }
    // 之后我们使用两个指针来进行删除 一个当前指针 一个next指针 
    struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));
    cur = head;
    // 前面以及判断过head不为空 这里放心用
    while(cur && cur ->val == val)
    {
        prev = cur;
        cur=cur->next;
        free(prev);
        head = cur;
    }
    // 后面开始考虑普通情况
    while(cur)
    {
        // 开始找要删的数据 找不到就往前遍历
        if(cur->val==val)
        {
            prev ->next = cur->next;
            prev = cur;
            cur = cur->next;
            free(prev);
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}


队列和栈


还是跟前面一样 在看后面的内容之前需要有队列相关知识


具体大家可以看看我写的这两篇文章啊


初阶数据结构 队列


初阶数据结构 栈


1. 循环队列


这道题前面的博客已经写过了 这里简单介绍下思路


920452487c074c7ba328fb4625845440.png


首先我们可以设置两个指针 分别指向头尾


但是我们这里发现 不太好判断队列的空 满是吧


那么这里我们可以增加一个参数 size


如果size= 0


是不是就代表队列为空


如果size = 最大值


是不是就代表队列为满


对这道题有兴趣的同学可以看看我的这篇博客 试着用我这里提供的方法将这个循环队列写出来


循环队列


2. 特殊栈


要求我们实现一个特殊的栈


它有两个功能


一个功能和基础的栈一样


还有一个功能是能够返回这个栈里面的最小值


这个思路也很简单


我们用两个栈来实现就好了


一个栈实现全部的普通功能


一个栈压栈的时候


1 如果为空 就压栈第一个元素


2 如果不为空 压栈当前元素和栈内最小元素两者的较小值

035dcd58edef4219b0ee089c39b9db61.png



这样子就可以啦


3. 队列与栈


用两个队列实现栈


用两个栈实现队列


这两个题目前面的博客中均有涉及


大家可以移步观看


队列实现栈


栈实现队列


总结


简单介绍了几种基本数据结构的面试题目


由于博主水平优先所以出现错在所难免 希望大佬看到可以指正


如果帮助到大家别忘了一键三连啊


阿尼亚 哇酷哇酷!

相关文章
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
124 4
|
3月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
101 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
13天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
50 20
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
112 23
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
65 1
|
3月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
51 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
60 0
|
3月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
55 4
|
3月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
39 0
数据结构与算法学习十四:常用排序算法总结和对比

热门文章

最新文章