数据结构八股(一)

参考这个https://blog.csdn.net/weixin_52341045/article/details/134395797?fromshareblogdetailsharetypeblogdetailsharerId134395797sharereferPCsharesource2401_82607598sharefromfrom_link链表队列和栈的区别链表是一种物理存储单元上非连续的一种数据结构看名字我们就知道他是一种链式的结构就像一群人手牵着手一样。链表有单向的双向的还有环形的。队列是一种特殊的线性表他的特殊性在于我们只能操作他头部和尾部的元素中间的元素我们操作不了我们只能在他的头部进行删除尾部进行添加。就像大家排队到银行取钱一样先来的肯定要排到前面后来的只能排在队尾所有元素都要遵守这个操作没有VIP会员所以走后门插队的现象是不可能存在的他是一种先进先出的数据结构。我们来看一下队列的数据结构是什么样的。栈也是一种特殊的线性表他只能对栈顶进行添加和删除元素。栈有入栈和出栈两种操作他就好像我们把书一本本的摞起来最先放的书肯定是摞在下边最后放的书肯定是摞在了最上面摞的时候不允许从中间放进去拿书的时候也是先从最上面开始拿不允许从下边或中间抽出来。简述快速排序过程1选择一个基准元素,通常选择第一个元素或者最后一个元素,2通过一趟排序将待排序的记录分割成独立的两部分其中一部分记录的元素值均比基准元素值小。另一部分记录的元素值比基准值大。3此时基准元素在其排好序后的正确位置4然后分别对这两部分记录用同样的方法继续进行排序直到整个序列有序。快速排序算法的原理是对冒泡排序的⼀种改进不稳定平均/最好时间复杂度 O(nlogn)元素基本有序时最坏时间复杂度O(n²)空间复杂度 O(logn)。⾸先选择⼀个基准元素通过⼀趟排序将要排序的数据分割成独⽴的两部分⼀部分全部⼩于等于基准元素⼀部分全部⼤于等于基准元素再按此⽅法递归对这两部分数据进⾏快速排序。 快速排序的⼀次划分从两头交替搜索直到 low 和 high 指针重合⼀趟时间复杂度 O(n)整个算法的时间复杂度与划分趟数有关。最好情况是每次划分选择的中间数恰好将当前序列等分经过 log (n) 趟划分便可得到⻓度为 1 的⼦表 这样时间复杂度O(nlogn)。最坏情况是每次所选中间数是当前序列中的最⼤或最⼩元素这使每次划分所得⼦表其中⼀个为空表 这样⻓度为 n 的数据表需要 n 趟划分整个排序时间复杂度O(n²)。简述各类排序算法时间复杂度、空间复杂度、稳定性对比下面有详细直接插⼊排序的原理稳定平均/最差时间复杂度 O(n²)元素基本有序时最好时间复杂度 O(n)空间复杂度 O(1)。每⼀趟将⼀个待排序记录按其关键字的⼤⼩插⼊到已排好序的⼀组记录的适当位置上直到所有待排序 记录全部插⼊为⽌。直接插⼊没有利⽤到要插⼊的序列已有序的特点插⼊第 i 个元素时可以通过⼆分查找找到插⼊位置insertIndex再把 i~insertIndex 之间的所有元素后移⼀位把第 i 个元素放在插⼊位置上。希尔排序的原理⼜称缩⼩增量排序是对直接插⼊排序的改进不稳定平均时间复杂度 O(n^1.3^)最差时间复杂度O(n²)最好时间复杂度 O(n)空间复杂度 O(1)。把记录按下标的⼀定增量分组对每组进⾏直接插⼊排序每次排序后减⼩增量当增量减⾄ 1 时排序完毕。直接选择排序的原理不稳定时间复杂度 O(n²)空间复杂度 O(1)。每次在未排序序列中找到最⼩元素和未排序序列的第⼀个元素交换位置再在剩余未排序序列中重复 该操作直到所有元素排序完毕。堆排序的原理是对直接选择排序的改进不稳定时间复杂度 O(nlogn)空间复杂度 O(1)。将待排序记录看作完全⼆叉树可以建⽴⼤根堆或⼩根堆⼤根堆中每个节点的值都不⼩于它的⼦节点 值⼩根堆中每个节点的值都不⼤于它的⼦节点值。以⼤根堆为例在建堆时⾸先将最后⼀个节点作为当前节点如果当前节点存在⽗节点且值⼤于⽗节点就将当前节点和⽗节点交换。在移除时⾸先暂存根节点的值然后⽤最后⼀个节点代替根节点并作 为当前节点如果当前节点存在⼦节点且值⼩于⼦节点就将其与值较⼤的⼦节点进⾏交换调整完堆 后返回暂存的值。冒泡排序的原理稳定平均/最坏时间复杂度 O(n²)元素基本有序时最好时间复杂度 O(n)空间复杂度 O(1)。⽐较相邻的元素如果第⼀个⽐第⼆个⼤就进⾏交换对每⼀对相邻元素做同样的⼯作从开始第⼀对 到结尾的最后⼀对每⼀轮排序后末尾元素都是有序的针对 n 个元素重复以上步骤 n -1 次排序完毕。当序列已经有序时仍会进⾏不必要的⽐较可以设置⼀个标志记录是否有元素交换如果没有直接结束⽐较。快速排序的原理是对冒泡排序的⼀种改进不稳定平均/最好时间复杂度 O(nlogn)元素基本有序时最坏时间复杂度O(n²)空间复杂度 O(logn)。⾸先选择⼀个基准元素通过⼀趟排序将要排序的数据分割成独⽴的两部分⼀部分全部⼩于等于基准 元素⼀部分全部⼤于等于基准元素再按此⽅法递归对这两部分数据进⾏快速排序。快速排序的⼀次划分从两头交替搜索直到 low 和 high 指针重合⼀趟时间复杂度 O(n)整个算法的时间复杂度与划分趟数有关。最好情况是每次划分选择的中间数恰好将当前序列等分经过 log(n) 趟划分便可得到⻓度为 1 的⼦表 这样时间复杂度 O(nlogn)。最坏情况是每次所选中间数是当前序列中的最⼤或最⼩元素这使每次划分所得⼦表其中⼀个为空表 这样⻓度为 n 的数据表需要 n 趟划分整个排序时间复杂度 O(n²)。排序算法怎么选择数据量规模较⼩考虑直接插⼊或直接选择。当元素分布有序时直接插⼊将⼤⼤减少⽐较和移动记录的次数如果不要求稳定性可以使⽤直接选择效率略⾼于直接插⼊。数据量规模中等选择希尔排序。数据量规模较⼤考虑堆排序元素分布接近正序或逆序、快速排序元素分布随机和归并排序稳定性。⼀般不使⽤冒泡。排序有哪些分类排序可以分为内部排序和外部排序在内存中进⾏的称为内部排序当数据量很⼤时⽆法全部拷⻉到内存需要使⽤外存称为外部排序。内部排序包括⽐较排序和⾮⽐较排序⽐较排序包括插⼊/选择/交换/归并排序⾮⽐较排序包括计数/基数/桶排序。插⼊排序包括直接插⼊/希尔排序选择排序包括直接选择/堆排序交换排序包括冒泡/快速排序。什么是 AVL 树AVL 树是平衡⼆叉查找树平衡二叉树又称为AVL树是一种特殊的二叉搜索树增加和删除节点后通过树形旋转重新达到平衡。右旋是以某个节点为中⼼ 将它沉⼊当前右⼦节点的位置⽽让当前的左⼦节点作为新树的根节点也称为顺时针旋转。同理左旋是以某个节点为中⼼将它沉⼊当前左⼦节点的位置⽽让当前的右⼦节点作为新树的根节点也称为逆时针旋转。什么是红⿊树红⿊树 是 1972 年发明的称为对称⼆叉 B 树1978 年正式命名红⿊树。主要特征是在每个节点上增加⼀个属性表示节点颜⾊可以红⾊或⿊⾊。红⿊树和 AVL 树 类似都是在进⾏插⼊和删除时通过旋转保持⾃身平衡从⽽获得较⾼的查找性能。与 AVL 树 相⽐红⿊树不追求所有递归⼦树的⾼度差不超过 1保证从根节点到叶尾的最⻓路径不超过最短路径的 2 倍所以最差时间复杂度是 O(logn)。红⿊树通过重新着⾊和左右旋转更加⾼效地完成了插⼊和删除之后的⾃平衡调整。红⿊树在本质上还是⼆叉查找树它额外引⼊了 5 个约束条件 ① 节点只能是红⾊或⿊⾊。 ② 根节点必须是⿊⾊。 ③ 所有 NIL 节点都是⿊⾊的。 ④ ⼀条路径上不能出现相邻的两个红⾊节点。 ⑤ 在任何递归⼦树中根节点到叶⼦节点的所有路径上包含相同数⽬的⿊⾊节点。这五个约束条件保证了红⿊树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果⼀个树的左⼦节点或右⼦节点不存在则均认定为⿊⾊。红⿊树的任何旋转在 3 次之内均可完成。AVL 树和红⿊树的区别红⿊树的平衡性不如 AVL 树它维持的只是⼀种⼤致的平衡不严格保证左右⼦树的⾼度差不超过 1。这导致节点数相同的情况下红⿊树的⾼度可能更⾼也就是说平均查找次数会⾼于相同情况的 AVL 树。在插⼊时红⿊树和 AVL 树都能在⾄多两次旋转内恢复平衡在删除时由于红⿊树只追求⼤致平衡因此红⿊树⾄多三次旋转可以恢复平衡⽽ AVL 树最多需要 O(logn) 次。AVL 树在插⼊和删除时将向上回溯确定是否需要旋转这个回溯的时间成本最差为 O(logn)⽽红⿊树每次向上回溯的步⻓为 2回溯成本低。因此⾯对频繁地插⼊与删除红⿊树更加合适。B 树和B 树的区别B 树中每个节点同时存储 key 和 data⽽B 树中只有叶⼦节点才存储 data⾮叶⼦节点只存储 key。InnoDB 对 B 树进⾏了优化在每个叶⼦节点上增加了⼀个指向相邻叶⼦节点的链表指针形成了带有顺序指针的 B 树提⾼区间访问的性能。B 树的优点在于 ① 由于B 树在⾮叶⼦节点上不含数据信息因此在内存⻚中能够存放更多的key数据存放得更加紧密具有更好的空间利⽤率访问叶⼦节点上关联的数据也具有更好的缓存命中率。 ② B树的叶⼦结点都是相连的因此对整棵树的遍历只需要⼀次线性遍历叶⼦节点即可。⽽ B 树则需要进⾏每⼀层的递归遍历相邻的元素可能在内存中不相邻所以缓存命中性没有 B树好。但是 B 树也有优点由于每个节点都包含 key 和 value因此经常访问的元素可能离根节点更近访问也更迅速二叉树各种树的定义满二叉树只有度为0的结点和度为2的结点并且度为0的结点都在同一层上。完全二叉树除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层节点都集中在该层最左边的若干位置。优先级队列即堆是一颗完全二叉树结点数为n的完全二叉树的叶子结点数量为n/2n为偶数(n1)/2n为奇数通常使用数组存储完全二叉树下标为i的结点的父结点下标为(i-1)/2左孩子结点下标为2i1右孩子结点下标为2i2叶子结点又称终端结点是指没有子结点的结点。总结点数 叶子结点数 度为 1 结点数 度为 2 结点数。二叉搜索树有序树若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树。平衡二叉树又称为AVL树是一种特殊的二叉搜索树它不仅满足二叉搜索树的性质而且左子树和右子树的高度之差的绝对值小于等于1左子树和右子树也是平衡二叉树。其在插入和删除操作后会通过自平衡的调整保持树的高度平衡从而提高搜索、插入和删除等操作的效率。C中map、set、multiset、multimap底层都是红黑树红黑树是平衡二叉树的一种特殊实现增删查的时间复杂度为Olog n。而unordered_set和unordered_map底层是哈希表增删查的时间复杂度为O1单支树非叶子结点只有一个孩子节点且方向一致哈夫曼树压缩和解压缩用到的特殊二叉树是哈夫曼树对应的方法是哈夫曼编码。结点路径长度两个节点中间隔线条数树的路径长度除根结点外其他结点到根结点路径长度之和结点带权路径长度从该结点到根结点路径长度与结点上权的乘积树带权路径长度树中所有叶子结点的带权路径长度之和构造方法首先从权值列表中选择最小的两个结点将其设置为左右较小为左较大为右孩子结点并设置其根节点的权值为两个权值之和并将该结点加入到权值列表删除权值列表中这两个最小结点。重复上述步骤直至权值列表只有一个值后完成创建。哈夫曼树的带权路径长度最短。哈夫曼树没有度为1的结点若有n个叶子结点则有n-1个非叶子结点所有结点数目为2n-1。红黑树红黑树是一种自平衡的二叉搜索树它在插入和删除操作后能够通过旋转和重新着色来保持树的平衡。具有以下特点每个节点要么是红色要么是黑色。根节点是黑色。每个叶子节点NIL节点是黑色。如果一个节点是红色则其子节点必须是黑色。从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。堆堆是一个完全二叉树即除了最后一层其他层都满最后一层从左往右连续填充其节点满足如下性质最大堆Max Heap任意节点的值都 ≥ 其子节点根节点是最大值最小堆Min Heap任意节点的值都 ≤ 其子节点根节点是最小值LRU 最近最少使用算法LRU 是一种缓存 淘汰算法当缓存空间已满时优先淘汰最长时间未被访问的数据。实现的方式是哈希表双向链表结合。具体实现步骤如下使用哈希表存储数据的键值对键为缓存的键值为对应的节点。使用双向链表存储数据节点链表头部为最近访问的节点链表尾部为最久未访问的节点。当数据被访问时如果数据存在于缓存中则将对应节点移动到链表头部如果数据不存在于缓存中则将数据添加到缓存中同时创建一个新节点并插入到链表头部。当缓存空间已满时需要淘汰最久未访问的节点即链表尾部的节点。使用ACM方式构建树输入一行数据第一个数字为结点总数后面按层序遍历字符数组的方式输入结点如果结点为空则输入##includeiostream #includevector using namespace std; struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(int x) :val(x), left(nullptr), right(nullptr) { } }; int main() { int n; cin n; char c; vectorTreeNode* vec(n); for (int i 0; i n; i) { cin c; vec[i] new TreeNode(c); } for (int i 0; i n; i) { if (vec[i]-val #) continue; int leftIndex 2 * i 1, rightIndex 2 * i 2; if (leftIndex n vec[i]-val ! #) vec[i]-left vec[leftIndex]; else vec[i]-left nullptr; if (rightIndex n vec[i]-val ! #) vec[i]-right vec[rightIndex]; else vec[i]-right nullptr; }//给每个结点 绑定 它的左孩子和右孩子,让数组里的结点从 “孤立点” 变成一棵真正的树。 TreeNode* root vec[0]; // root即为结果 return 0; }二叉树遍历深度优先遍历先往深走遇到叶子结点再往回走。有前序遍历、中序遍历、后序遍历的递归法和迭代法实现6个其中中序遍历的迭代方法需要特殊记忆中间结点的顺序即为遍历方式前序遍历中左右中序遍历左中右后续遍历左右中广度优先遍历有层序遍历通过迭代法实现1个需要特殊记忆前序遍历递归法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector res; void traversal(TreeNode* root) { if (root nullptr) return ; res.push_back(root-val); traversal(root-left); traversal(root-right); } vector preorderTraversal(TreeNode* root) { traversal(root); return res; } };迭代法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector preorderTraversal(TreeNode* root) { vector res; stack st; if (root ! nullptr) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-right ! nullptr) st.push(node-right); if (node-left ! nullptr) st.push(node-left); //栈是“后进先出”所以要先压右再压左 } return res; } };中序遍历递归法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector res; void traversal(TreeNode* root) { if (root nullptr) return ; traversal(root-left); res.push_back(root-val); traversal(root-right); } vector inorderTraversal(TreeNode* root) { traversal(root); return res; } };迭代法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector inorderTraversal(TreeNode* root) { vector res; stack st; TreeNode* node root; while (node ! nullptr || !st.empty()) { if (node ! nullptr) { st.push(node); node node-left; } else { node st.top(); st.pop(); res.push_back(node-val); node node-right; } } return res; } };后序遍历递归法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector res; void traversal(TreeNode* root) { if (root nullptr) return ; traversal(root-left); traversal(root-right); res.push_back(root-val); } vector postorderTraversal(TreeNode* root) { traversal(root); return res; } };迭代法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector postorderTraversal(TreeNode* root) { vector res; stack st; if (root ! nullptr) st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); res.push_back(node-val); if (node-left ! nullptr) st.push(node-left); if (node-right ! nullptr) st.push(node-right); } reverse(res.begin(), res.end()); return res; } };层序遍历迭代法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector levelOrder(TreeNode* root) { vector res; queue que; if (root ! nullptr) que.push(root); while (!que.empty()) { vector vec; int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); vec.push_back(node-val); if (node-left ! nullptr) que.push(node-left); if (node-right ! nullptr) que.push(node-right); } res.push_back(vec); } return res; } };时间复杂度这个写的清晰一点https://blog.csdn.net/Pumpkin_O/article/details/140277205?fromshareblogdetailsharetypeblogdetailsharerId140277205sharereferPCsharesource2401_82607598sharefromfrom_link时间复杂度就是算法的时间度量记为T(n)O(f(n))表示随着问题规模n的增大算法执行时间的增长率和f(n)的增长率相同称为算法的渐进时间复杂度简称时间复杂度。步骤首先常数1取代加法常数其次只保留最高阶项并把最高阶项的系数设为1。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。Func1中count语句总共执行了多少次// 请计算一下Func1中count语句总共执行了多少次 void Func1(int N) { int count 0; for (int i 0; i N; i) { for (int j 0; j N; j) { count; } } for (int k 0; k 2 * N; k) { count; } int M 10; while (M--) { count; } printf(%d\n, count); }实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。常见复杂度对比单层循环时间复杂度计算公式循环趟数循环变化关系循环停止条件联立解方程列出循环趟数t及每轮循环i的变化值找到t与i的关系确定循环停止条件联立两式解方程写结果i n*n; whlie(i ! 1) i i/2;第一步列出循环趟数t和每轮循环i的变化值第二步找到t和i的关系i (n2)/2t第三步确定循环停止条件i 1第四步联立第二步和第三步两式解方程所以得到的时间复杂度为列出循环趟数 t 以及每轮 i 的变化值找到 t 和 i 的关系确定停止条件联立方程//计算下面代码的时间复杂度 int i 1; while(in) i i*2;列出循环趟数 t 及每轮 i 的变化值找到 i 与 t 的关系i2^t确定停止条件: in联立12方程: 得出2^tn。即t两层循环时间复杂度计算公式外层循环变化与内层执行次数求和列出循环中i的变化值写出内层语句的执行次数求和写结果int m 0, i , j; for(i 1; in;i) for(j 1;j2*i;j) m;第一步列出循环中i的变化值第二步写出内层语句的执行次数第三步求和写结果 2468…2*n n(n1) 所以时间复杂度为1.列出外层循环趟数t12.列出外层循环中i的变化值3.列出内层语句的执行次数t24.求内层语句的执行次数t2之和S多层循环时间复杂度计算公式方法一抽象为计算三维物体体积for(i0;in;i) for(j0;ji;j) for(k0;kj;k)方法二列式求和排序算法重点冒泡排序平均时间复杂度O(n2)、空间复杂度O(1)、稳定排序相等元素位置不变选择排序平均时间复杂度O(n2)、空间复杂度O(1)、非稳定排序插入排序平均时间复杂度O(n2)、空间复杂度O(1)、稳定排序快速排序平均时间复杂度O(nlog2n)、空间复杂度O(1)、非稳定排序希尔排序插入排序的优化版本。平均时间复杂度通常被认为是介于O(n)和O(n2)之间与增量序列有关Hibbard 增量序列和 Knuth 增量序列等都可以使希尔排序达到 O(nlog2n) 的平均时间复杂度、空间复杂度O(1)、非稳定排序归并排序分治法平均时间复杂度O(nlog2n)、空间复杂度O(n)、稳定排序堆排序时间复杂度O(nlog2n)、空间复杂度O(1)、非稳定排序跳表跳表的本质是在一个有序链表上加入多层索引来优化快速查找跳表的搜索是从第一个元素的最上面索引开始搜索1然后搜索第一层的13然后进入下一层索引直至找到目标元素了解即可后面遇到再补充。。