重庆有多少网站,互联网营销模式有哪些,自媒体 wordpress,数据分析师工资#x1f308;个人主页#xff1a;慢了半拍 #x1f525; 创作专栏#xff1a;《史上最强算法分析》 | 《无味生》 |《史上最强C语言讲解》 | 《史上最强C练习解析》 #x1f3c6;我的格言#xff1a;一切只是时间问题。 1.线性表 线性表#xff08;linear list… 个人主页慢了半拍 创作专栏《史上最强算法分析》 | 《无味生》 |《史上最强C语言讲解》 | 《史上最强C练习解析》 我的格言一切只是时间问题。 1.线性表 线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储。 2.顺序表
2.1概念及结构 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储。在数组上完成数据的增删查改。 顺序表一般可以分为 1. 静态顺序表使用定长数组存储元素。 比特科
2.2 接口实现 静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了空 间开多了浪费开少了不够用。所以现实中基本都是使用动态顺序表根据需要动态的分配空间 大小所以下面我们实现动态顺序表。
2.3 数组相关面试题 1. 原地移除数组中所有的元素val要求时间复杂度为O(N)空间复杂度为O(1)。OJ链接 2. 删除排序数组中的重复项。OJ链接 3. 合并两个有序数组。OJ链
2.4 顺序表的问题及思考 问题 1. 中间/头部的插入删除时间复杂度为O(N) 2. 增容需要申请新空间拷贝数据释放旧空间。会有不小的消耗。 3. 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到 200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。 思考如何解决以上问题呢下面给出了链表的结构来看看。
3.链表
3.1 链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
3.2 链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 虽然有这么多的链表的结构但是我们实际中最常用还是两种结构
1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结 构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带 来很多优势实现反而简单了后面我们代码实现了就知道了。 3.3 链表的实现 3.4 链表面试题 1. 删除链表中等于给定值 val 的所有结点。 OJ链接 2. 反转一个单链表。 OJ链接 3. 给定一个带有头结点 head 的非空单链表返回链表的中间结点。如果有两个中间结点则 返回第二个中间结点。OJ链接 4. 输入一个链表输出该链表中倒数第k个结点。 OJ链接 5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有 结点组成的。OJ链接 6. 编写代码以给定值x为基准将链表分割成两部分所有小于x的结点排在大于或等于x的结 点之前 。OJ链接 7. 链表的回文结构。OJ链接 8. 输入两个链表找出它们的第一个公共结点。OJ链接 9. 给定一个链表判断链表中是否有环。 OJ链接 【思路】 快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表其实位置开始运行 如果链表 带环则一定会在环中相遇否则快指针率先走到链表的末尾。比如陪女朋友到操作跑步减 肥。 【扩展问题】 为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚 进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。 此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情 况因此在满指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 快指针一次走3步走4步...n步行吗 10. 给定一个链表返回链表开始入环的第一个结点。 如果链表无环则返回 NULL OJ链接 结论 让一个指针从链表起始位置开始遍历链表同时让一个指针从判环时相遇点的位置开始绕环 运行两个指针都是每次均走一步最终肯定会在入口点的位置相遇。 11. 给定一个链表每个结点包含一个额外增加的随机指针该指针可以指向链表中的任何结点 或空结点。 要求返回这个链表的深度拷贝。OJ链接 12. 其他 。ps链表的题当前因为难度及知识面等等原因还不适合我们当前学习以后大家自己 下去以后 Leetcode OJ链接 牛客 OJ链接
