本文主要总结了在LeetCode刷题过程中常用到的数据结构、方法技巧以及时间空间复杂度分析，为后续刷题提供思路。内容会根据本人刷题进度不断更新。
数据结构
链表
1. 快慢指针找环
分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
2. 快慢指针找链表前半部分尾节点
分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 指针的next节点或next.next节点为None，则slow节点指向链表前半部分尾节点。
3. 相交链表
分别设置两个指针从A链和B链同时向后遍历，当指针走到链表末端时，则替换成另一链表的表头继续走，如此这样，即可找到相交的起始节点，若同时走到了链表末尾还未找到相交点，则两链表无交点。该方法时间度为O(m+n)，空间复杂度为O(1)。
前缀树
前缀树（字典树）是处理字符串常见的数据结构。
前缀树的3个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
def searchPrefix(self, prefix: str) -> “Trie”: # 查找前缀，返回前缀节点，找不到返回None
常用方法
动态规划
-
动态规划：能将大问题拆成几个小问题，且满足无后效性、最优子结构性质
（1）递推关系->状态转移方程
（2）注意状态转移顺序
（3）观察转移规律：减少空间复杂度（如查找最长回文子串：中心扩展算法）；减少时间复杂度
-
动态规划+滚动数组（减小空间复杂度）
回溯
-
回溯：把问题的解空间转化成了图或树的结构表示，然后使用深度优先搜索遍历解空间，遍历的过程中记录和寻找所有可行解或者最优解，对于不可行解进行剪枝。
（1）定义问题的解空间，转化成树（解空间树：子集树/排列树）
（2）剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。
（3）回溯法的实现方法：递归和递推（即迭代）
-
回溯时间复杂度：所有可行解长度之和
-
不考虑搜索路径顺序时，注意不要重复搜索相同路径
时间空间复杂度分析
其他
边界情况
- 输入为空（如空数组、空字符串等）的情况
- 下标为0、1或末尾的特殊情况
- 注意无输出结果的情况
- 初始值的定义
易错点
- 指针出界
- Python中的对象之间赋值时是按引用传递的，如果需要拷贝对象或传递函数参数，需要使用标准库中的copy模块
技巧
- 448.找数组中消失的数字：通过原地修改数组中数字的正负来标记数组中是否有该位置下标对应的数字，从而不使用额外空间即可找到数组中消失的数字
- 3.无重复最长子串：通过双指针滑动窗口遍历字符串，通过哈希集合记录字符是否出现过
- 11.生最多水的容器： 双指针法，初始双指针分别指向数组首尾，指针每次移动都弃短板，并记录当前最大容量
- 17.电话号码字母组合： 哈希表，存储每个数字对应的所有可能的字母；回溯，从一条路往前走，能进则进，不能进则退回来，换一条路再试，即以深度优先的方式搜索解空间
- 数字排列组合去重：可先排序后去重
- 46.全排列：回溯+交换数组元素，提升时空效率
- 49. 字母异位词分组： 哈希表，collections.defaultdict(list)列表字典，用排序后的字符串作为字典的键，则每次不用遍历查找要放入哪个数组
- 200.岛屿数量：网格类问题的 DFS 遍历方法，类似图或树上的DFS
- 207.课程表：典型的拓扑排序问题（对于图 G中的任意一条有向边 (u, v)，u在排列中都出现在 v的前面）