常用数据结构#
Q线性数据结构（元素之间一对一线性关系）#
栈（Stack）#
核心规则：先进后出（LIFO），只有一端（栈顶）能进行增删操作，栈底封闭。
队列（Queue）#
核心规则：先进先出（FIFO），一端（队尾）入队，一端（队首）出队）
链表（Link List）#
核心结构：由一个个「节点」组成，每个节点包含「数据」和「下一个节点的引用」（类似链条），分单链表、双链表、循环链表。
优点：插入 / 删除中间元素效率高（只需修改节点引用，无需移动其他元素），内存分配灵活（无需连续内存）。
缺点：随机访问效率低（无索引，需从头节点遍历到目标节点），占用额外内存存储节点引用。
Q非线性数据结构（元素之间一对多/多对多关系）#
树（Tree）#
核心结构：分层树形结构，有且只有一个「根节点」，每个节点可以有多个子节点，无环（节点之间不会形成闭环）。
高频之类及其特点：
二叉树：每个节点最多有 2 个子节点（左、右子节点），是最基础的树结构，支持前 / 中 / 后 / 层序四种遍历。#
二叉搜索树（BST）：二叉树的升级版，左子树所有节点值 <根节点值，右子树所有节点值> 根节点值，支持高效查找 / 插入 / 删除（平均 O (logn)）。#
红黑树/AVL树：平衡二叉搜索树，避免二叉搜索树退化为链表，保证查找 / 插入 / 删除的高效性（底层用于字典、集合等）。#
图（Graph）#
核心结构： 由节点和边组成，允许有环，是最通用的复杂数据结构。
分类：按照边的方向可以划分为有向图和无向图，按照边的权重可以分为带权图和无权图。#
存储方式：邻接表（节省内存适合稀疏图），邻接矩阵（查找高效，适合稠密图）#
算法#
Q时间复杂度和空间复杂度的定义是什么？#
时间复杂度：描述算法执行的基本指令数随输入规模 n 的增长趋势，用大 O 表示（如 O (n)、O (logn)），通常关注最坏情况。
空间复杂度：描述算法内存空间随输入规模 n 的增长趋势，同样用大 O 表示，关注数据占用的空间。
Q常见时间复杂度的排序是什么？#
O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n·2ⁿ) < O(n·n!) < O(nⁿ)。
Q二分查找的适用条件及时间复杂度？#
- 适用条件：有序数组（升序或降序）。
- 原理：每轮将搜索范围缩小一半，直至找到目标或范围为空。
- 时间复杂度：O (logn)，空间复杂度 O (1)。
Q快速排序和归并排序的核心思想及复杂度对比？#
Q动态规划和分治算法的区别？#
分治算法：将问题拆分为独立子问题，递归求解后合并结果（如归并排序）。
动态规划：处理子问题重叠的场景，通过存储子问题结果避免重复计算（如爬楼梯、0-1 背包）。
Q贪心算法的适用条件及案例？#
适用条件：问题需满足贪心选择性质（局部最优可导出全局最优）和最优子结构。
案例：分发糖果（每个孩子至少 1 颗，评分高的孩子需比相邻孩子多），通过左右两次遍历确保局部最优。
Q回溯算法的基本步骤及案例？#
步骤：选择候选解→递归探索→验证条件→回溯（撤销选择）。
案例：N 皇后问题，通过递归尝试放置皇后，验证列和对角线无冲突，冲突则回溯。
常考力扣经典题#
链接：
20. 有效的括号 - 力扣（LeetCode）
70. 爬楼梯 - 力扣（LeetCode）
198. 打家劫舍 - 力扣（LeetCode）
53. 最大子数组和 - 力扣（LeetCode）
72. 编辑距离 - 力扣（LeetCode）
11. 盛最多水的容器 - 力扣（LeetCode）
134. 加油站 - 力扣（LeetCode）
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
15. 三数之和 - 力扣（LeetCode）
42. 接雨水 - 力扣（LeetCode）
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
110. 平衡二叉树 - 力扣（LeetCode）