数据结构（零）：基础
#1 链表与数组
- 链表和数组是最基本的数据结构，是其他数据结构的基础
- 数组和链表的区别
- 数组和链表都是线性数据结构，区别在于数组具有索引，数组中的元素在内存中是连续存储的；链表是把一些分离独立的元素按引用链接到一起
- 数组能在 O(1) 时间内访问到元素，但需要 O(N) 时间插入、删除元素，与链表相反。
- 数组可以嵌套数组，得到多维数组。二维数组常和 dfs、bfs 遍历相关
python 中的栈和堆基于数组，而内置库 deque 是用双向链表实现的。
例题
数组：
-
0080 删除排序数组中的重复项 II
-
0283 移动零
-
0448 找到所有数组中消失的数字
-
0485 最大连续 1 的个数
-
0724 寻找数组的中心下标
-
0075 颜色分类
-
0128 最长连续序列
-
0189 旋转数组
-
0238 除自身以外数组的乘积
-
0041 缺失的第一个正数
-
0284 顶端迭代器
-
0287 寻找重复数 二维数组：
-
0048 旋转图像
-
0054 螺旋矩阵
-
0059 螺旋矩阵 II
-
0073 矩阵置零
-
0289 生命游戏
-
0463 岛屿的周长
-
0835 图像重叠
-
1992 找到所有的农场组 链表：
-
0707 设计链表
-
0002 两数相加
-
0024 两两交换链表中的节点
-
0082 删除排序链表中的重复元素 II
-
0237 删除链表中的节点
-
0061 旋转链表
-
0086 分隔链表
-
0328 奇偶链表
-
0725 分隔链表
-
0021 合并两个有序链表
-
0023 合并K个升序链表
-
0147 对链表进行插入排序
-
0148 排序链表 快慢指针：
-
0019 删除链表的倒数第 N 个结点
-
0141 环形链表
-
0142 环形链表 II
-
0160 相交链表
-
0876 链表的中间结点
-
0138 复制带随机指针的链表
-
0430 扁平化多级双向链表
-
0432 全 O(1) 的数据结构
-
1206 设计跳表
-
0206 反转链表
-
0092 反转链表 II
-
0025 K 个一组翻转链表
-
0143 重排链表
-
0234 回文链表
#2 字符串
- 字符串和数组很相似，具有索引，且元素在内存中是连续存储的
python 中的字符串是不可变的，不能直接修改、添加、删除元素，而应该用切片。
例题
- 0009 回文数
- 0165 比较版本号
- 0392 判断子序列
- 0831 隐藏个人信息
- 1169 查询无效交易
- 0068 文本左右对齐
- 0393 UTF-8 编码验证
- 0459 重复的子字符串
- 0686 重复叠加字符串匹配
- 0833 字符串中的查找与替换
- 0564 寻找最近的回文数
- 0866 回文素数
#3 哈希表
- 哈希表是针对查询，空间换时间的一种数据结构
- 一般能够在 O(1) 时间内插入、查询、删除元素，但不能通过下标访问元素
- 哈希表分为哈希集合和哈希映射
- 哈希集合存储非重复值
- 哈希映射存储 key 唯一的 (key,value) 对
python 中一般直接用内置库 set 和 dict 表示哈希集合和哈希映射。 另外还有一些特定用途的内置库，比如 Counter, defaultdict, OrderedDict。
例题
- 0705 设计哈希集合
- 0706 设计哈希映射
- 0535 设计哈希映射 TinyURL 的加密与解密
- 0217 存在重复元素
- 0349 两个数组的交集
- 0500 键盘行
- 0575 分糖果
- 0001 两数之和
- 0205 同构字符串
- 0219 存在重复元素 II
- 0599 两个列表的最小索引总和
- 0350 两个数组的交集 II
- 0409 最长回文串
- 0532 数组中的 k-diff 数对
- 0594 最长和谐子序列
- 0015 三数之和
- 0299 猜数字游戏
- 0447 回旋镖的数量
- 0454 四数相加 II
- 0554 砖墙
- 0710 黑名单中的随机数
- 0149 直线上最多的点数
- 0166 分数到小数
- 0336 回文对
- 1178 猜字谜 特殊的键
- 0036 有效的数独
- 0049 字母异位词分组
- 0318 最大单词长度乘积
- 0676 实现一个魔法字典
#4 栈与队列
- 栈是一个后入先出的数据结构，插入和删除都在末尾进行
- 队列是一个先入先出的数据结构，插入在末尾，删除在开头
python 中一般用数组实现栈，用内置库 deque 实现队列 额外地，dfs 的非递归形式借助栈实现，bfs 常借助队列实现
例题
- 0225 用队列实现栈
- 0232 用栈实现队列
- 0622 设计循环队列
- 0641 设计循环双端队列
- 0071 简化路径
- 0150 逆波兰表达式求值
- 0682 棒球比赛
- 0946 验证栈序列
- 1441 用栈操作构建数组
- 0155 最小栈
- 0341 扁平化嵌套列表迭代器
- 0895 最大频率栈
- 1381 设计一个支持增量操作的栈
#5 树
- 树是一种非线性的数据结构，本质是节点的有限集。其定义是递归的：
- 有且仅有一个特定的称为根（root）的节点
- 当节点数量 > 1 时，其余节点可分为若干个互不相交的有限集，其中每个集合也可以看作一颗树，称之为根的子树。
从图的观点来看，树也可视为一个拥有 N 个节点和 N-1 条边的一个有向无环图。
例题
遍历
- 0094 二叉树的中序遍历
- 0103 二叉树的锯齿形层序遍历
- 0144 二叉树的前序遍历
- 0145 二叉树的后序遍历
- 0872 叶子相似的树
- 0112 路径总和
- 0113 路径总和 II
- 0116 填充每个节点的下一个右侧节点指针
- 0117 填充每个节点的下一个右侧节点指针 II
- 0655 输出二叉树
- 0662 二叉树最大宽度 递归
- 0101 对称二叉树
- 0226 翻转二叉树
- 0508 出现次数最多的子树元素和
- 0606 根据二叉树创建字符串
- 0671 二叉树中第二小的节点
- 0814 二叉树剪枝
- 0106 从中序与后序遍历序列构造二叉树
- 0110 平衡二叉树
- 0124 二叉树中的最大路径和
- 0236 二叉树的最近公共祖先
- 0337 打家劫舍 III
- 0834 树中距离之和
- 0889 根据前序和后序遍历构造二叉树 二叉搜索树
- 0098 验证二叉搜索树
- 0108 将有序数组转换为二叉搜索树
- 0173 二叉搜索树迭代器
- 0235 二叉搜索树的最近公共祖先
- 0669 修剪二叉搜索树
- 0701 二叉搜索树中的插入操作
- 0096 不同的二叉搜索树
- 0095 不同的二叉搜索树 II
- 0450 删除二叉搜索树中的节点
- 0501 二叉搜索树中的众数
- 0530 二叉搜索树的最小绝对差
- 0538 把二叉搜索树转换为累加树
- 0099 恢复二叉搜索树
#6 堆
- 堆是一种特别的完全二叉树，每一个节点的值都大于等于或小于等于其孩子节点的值
- 堆可以在 O(logN) 时间内插入元素、删除根节点，在 O(1) 时间获得最大值或最小值。一般用于有序弹出元素的场景。
python 中一般用内置库 heapq 实现堆的操作（list 实现的），默认是小顶堆，即堆顶元素是最小值。
例题
- 0703 数据流中的第 K 大元素
- 1845 座位预约管理系统
- 0023 合并K个升序链表
- 0692 前K个高频单词
- 1046 最后一块石头的重量
- 0295 数据流的中位数
- 0355 设计推特
- 0373 查找和最小的 K 对数字
- 0786 第 K 个最小的素数分数
- 1801 积压订单中的订单总数
- 1834 单线程 CPU
- 0407 接雨水 II
- 0857 雇佣 K 名工人的最低成本
- 1439 有序矩阵中的第 k 个最小数组和
#7 图
- 图是一种比树形结构更复杂的非线性数据结构
- 树形结构中的结点是一对多的关系，且有明显的层次关系
- 图中的顶点是多对多的关系，无明显的层次关系。
- 按顶点连线（边）是否有方向，可以将图分为有向图和无向图
- 有些图的边还附带数据信息（权），被称为网或网络
- 图的遍历和树的遍历相似，但图中可能出现回路
- 因此常用一个辅助数组或哈希表 vis 记录访问过的顶点