hot100心得
Hot100 二刷笔记
哈希（3/3）
1. 两数之和
使用哈希表实现
49. 字母异位词分组
灵神：可以使用带默认值得字典类型defaultdict，还有sorted函数可以给字符串排序，会把字符串拆成字符然后排序，使用完sorted函数需要使用join函数把字符连接起来。
具体实现：用 defaultdict(list) 初始化一个带默认值的哈希表d，用s遍历strs中的元素，直接用sorted函数可以按字符排序，然后再套用join函数合并，赋值给sorted_s，以sorted_s为key，在哈希表中加入value：s。遍历完返回哈希表中的值，并将其转为list类型（list{d.values()）。
- 时间复杂度 O(nmlogm)， 其中 n 为 strs 的长度，m 为 strs[i] 的长度。每个字符串排序需要 O(mlogm) 的时间，有 n 个字符串。
- 空间复杂度 O(nm)
- Python 实现
129. 最长连续序列
灵神：使用哈希表实现，遍历哈希表，如果当前元素-1也在哈希表中就直接跳过（continue），等后面遍历到没有更小的连续数的时候再开始计算答案；如果没有更小的连续数了，就初始化一个中间变量y用来计算答案，使用一个while循环如果y在哈希表中，则y++，否则跳出循环，和之前的ans值比较，记录答案在ans中。
- 小优化：ans的长度*2大于等于整个数组的长度，则不会再有比ans大的答案了，直接break循环
- 时间复杂度 O(n)
- 空间复杂度 O(m)
- Python 实现
双指针（4/4）
283. 移动零
灵神：
- 原地栈：把非零数全部移到前面，stack_size记录非零数的位置，stack_size之后的全部置为零；
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
- 双指针+交换元素
11. 盛最多水的容器
灵神：初始化ans=0，和双指针left和right，循环边界是left<right，计算area然后取ans和当前area的较大值赋值给ans，然后比较left和right的高度，移动较小的值。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
15. 三数之和
灵神：类似于盛最多水的容器和两数之和2，先排序nums，遍历所有数表示为x，0-x为target；遇到重复数就continue；
- 两个小优化：
- 优化一：如果x+nums[i+1]+nums[i+2]>0, 就没有数可以等于0了，就直接break；
- 优化二：如果x+nums[-2]+nums[-1]<0，就说明这个x的太小了，continue换下一个x；
- 时间复杂度 O(n^2)
- 空间复杂度 O(1)
- Python 实现
42. 接雨水
灵神：
- 前后缀最大值
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
- 相向双指针
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
滑动窗口（2/2）
3. 无重复字符的最长子串
灵神：哈希表+双指针。初始化一个哈希表用来记录遍历过的字符串的字符出现的次数，for循环遍历，right指针和遍历元素x对应，while遇到cnt[x]大于1，就把左指针对应的字符的计数减去1，左指针加1.
- 时间复杂度 O(n)
- 空间复杂度 O(m)，m为不重复字符总数
- Python 实现
438. 找到字符串中所有字母异位词
灵神：不定长滑窗，方法类似于3.无重复字符的最长子串，当当前位置减去left+1的长度等于p的长度，就将left加入答案中。
具体实现：使用Counter初始化cnt统计p中字母出现次数，然后初始化数组ans，left为0，用enumerate遍历s，遍历到的当前下标为right，元素为c：然后cnt中的c出现次数-=1，while循环：如果cnt[c]小于0，则cnt[s[left]]+=1，然后将left右移。如果当前位置下标减去左指针然后+1，等于p字符串的长度，就将left加入到ans中。最后返回ans。
- 时间复杂度 O(m+n)
- 空间复杂度 $\mathcal{O}(|\Sigma|)$，其中 ∣Σ∣=26 是字符集合的大小。返回值不计入。
- Python 实现
子串（3/3）
560. 和为K的子数组
灵神：首先求前缀和，然后参考两数和，s[j]-s[i]=k，则s[i] = s[j]-k，遍历前缀和，
先ans+=cnt[sj-k]，再 cnt[sj]+=1。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
239. 滑动窗口最大值
灵神：初始化ans记录答案，初始化双端队列q, 用来储存元素的下标；循环遍历数组下标和值，while循环：q不为空，且q的最后一个值小于等于当前值，则移除q的最后一个值；将当前值的下标移入队列；如果队列中下标之差大于k-1，则移除第一个元素；遍历到下标大于k-1的位置时，将队列第一个元素移入ans。
- 时间复杂度 O(n)
- 空间复杂度 O(min{k,U})，U=len(set(min(nums)))
76. 最小覆盖子串
灵神：首先用哈希表分别统计s子串和t中字母出现次数；初始化 ansLeft和ansRight为-1和len(s)；初始化left=0；循环遍历s，right为下标，c为值：右端点移入子串，s的子串是否涵盖t：如是，判断新的子串是否更短，是则更新，不是则逐步移动做断点；如果ansLeft没有更新过，则没找到子串t；否则返回子串。
- 时间复杂度：O(∣Σ∣m+n)，其中 m 为 s 的长度，n 为 t 的长度，∣Σ∣ 为字符集合的大小，本题字符均为英文字母，所以 ∣Σ∣=52。
- 空间复杂度：O(∣Σ∣)。如果创建了大小为 128 的数组，则 ∣Σ∣=128。
- Python 实现
普通数组（5/5）
53. 最大子数组和
灵神：
前缀和+贪心算法：初始化min_pre记录最小前缀和，pre记录前缀和，都初始化为0，ans记录答案初始化为-inf。遍历数组nums，更新pre = pre+nums[i]，然后更新ans为ans和（pre-min_pre）的较大值，再更新min_pre为pre和min_pre的较小值。遍历结束，返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
动态规划+空间优化
状态转移方程如下：
$f[i]=\left{\begin{array}{ll}
\text { nums }[i], & i=0 \
\max (f[i-1], 0)+\text { nums }[i], & i \geq 1
\end{array}\right.$时间复杂度 O(n)
空间复杂度 O(1)
Python 实现
56. 合并区间
灵神：先使用sort函数排序所有区间的左端点（sort(key=lamdba p:p[0]），然后初始化数组ans，使用变量p变量区间，如果ans不为空，且ans[-1][1]大于p[0]，就可以合并，将ans[-1][1]更新为他自己的值与p[1]值取较大值，否则就将p加入到ans。最后返回ans。
- 时间复杂度 O(nlogn)
- 空间复杂度 O(1)
- Python 实现
189. 轮转数组
灵神：先整体反转，然后再k和n取余数，然后再将前k个元素和剩余元素分别反转。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
238. 除了自身以外数组的乘积
灵神：顺序遍历计算前i个的乘积，倒序遍历计算后i个的乘积，然后除了nums[i]位置的数组的乘积就是pre[i]*suf[i]。
- 时间复杂度 O(n)
- 空间复杂度 O(n)，空间优化以后是 O(1)
- Python 实现
41. 缺失的第一个正数
灵神：使用学号与学生对应的想法，如果不对应就交换到对应位置，会有重复元素，重复元素当影分身看待，分为当前为真身，在正确的位置上，和当前是影分身，真身在正确的位置上（nums[i] != nums[nums[i] - 1]）的方法来判断；交换完之后再遍历，看是否都在正确的位置上了，返回第一个不在的。
具体实现：初始化n为nums长度，遍历nums，while循环，条件：如果nums[i]在(0,n]的范围中，且真身不在正确的位置上（判断方法如上），j就赋值为nums[i]-1，交换i和j位置的元素。再循环遍历nums，如果位置正确（nums[i]≠i+1），就返回i+1。遍历完没有找到，说明都在位置上，则返回n+1。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
矩阵（4/4）
73. 矩阵置零
灵神：初始化两个数组，一个存储列为零的位置，一个存储行为零的位置，如果有零则数组对应列或者行为true；然后两层循环遍历两个数组，如果两个数组中有一个为0，则矩阵的该位置置为0.
- 时间复杂度 O(mn)
- 空间复杂度 O(m+n)
- Python 实现
54. 螺旋矩阵
灵神：标记。首先再类外初始化一个方向数组DIRS = (0, 1), (1, 0), (0, -1), (-1, 0) # 右下左上，再写类中的方法，初始化 m,n,数组ans,变量i,j,di为零；然后循环（for _ in range(m*n)）：将matrix[i][j]加入答案，标记已访问（赋值为None），用x、y表示更新下一步的位置，判断下一步的位置是否可行，即x、y是否在界内，以及是否被访问过（如可行，di右转90度），更新i,j走下一步；最后返回ans。
- 时间复杂度 O(mn)
- 空间复杂度 O(1)
- Python 实现
101. 旋转图像
灵神：两次翻转等于一次旋转，先转置，再左右翻转（翻转可以使用python的reverse函数）
- 时间复杂度 $O(n^2)$
- 空间复杂度 O(1)
- Python 实现
240. 搜索二维矩阵
灵神：初始化 m,n i,j 从右上角开始遍历；while循环，边界条件是还有剩余元素（如果找到则返回 True，否则当前元素小于target，则删除这一行；如果大于则删除这一列）；最终循环结束，没找到就返回false。
- 时间复杂度 O(m+n)
- 空间复杂度 O(n)
- Python 实现
链表（14/14）
160. 相交链表
灵神：如果不相交就一直next，p和q如果遍历完自己的链表就指向对面的链表，最后返回p或者q。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
206. 反转链表
灵神：头插法，初始化pre = None, cur = head, 循环边界就是cur不会空，nxt为cur.next，然后把cur的next指向pre，pre指向cur，cur指向nxt。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
234. 回文链表
灵神：先找到中间节点，然后再从中介节点反转链表；然后遍历反转后的后一半链表是否和前一半链表的值一致。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
141. 环形链表
142. 环形链表2
灵神：先找到快慢节点相交的节点，然后slow节点和head节点同时next，相遇的节点就是环开始的节点。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
21. 合并两个有序链表
灵神：初始化一个哨兵节点，给cur赋值为哨兵节点，while循环，边界条件：list1和list2都不为空。如果list1的值小，则cur.next指向list1，list1指向下一个节点；否则，list2同理。然后cur也指向下一个节点。循环结束，如果list1不为空，则cur.next指向list1；否则，指向list2。最后返回dummy.next
- 时间复杂度 O(m+n)
- 空间复杂度 O(1)
- Python 实现
2. 两数相加
灵神：迭代的方法，使用哨兵节点，创建一个新链表（cur = dummy = ListNode() )，初始化一个变量carry，while循环，边界条件为 l1 或者 l2 或者 carry 不为空，如果l1不为空，就可以把它的值加入到carry中，并将l1指向下一个节点；l2同理。使用ListNode()初始化cur.next的值为carry的余数，下一次循环的carry为当前carry//10。返回dummy.next。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
19. 删除链表的倒数第N个节点
灵神：使用前后指针（left和right），并且由于需要考虑链表只有一个节点，删除后为空的情况，使用哨兵节点，首先right指针先移动N个位置，然后左右指针一起移动，边界条件右指针不为空。最后左指针就会指向第N个节点的前一个位置。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
20. 两两交换链表中的节点
灵神：使用哨兵节点，node0指向哨兵节点，node1指向head，边界条件node1和node1.next不为空，初始化node2,3分别为node1,2的next，然后反转node0,1,2 的指向，然后把node0,1移动到下一组，返回dummy.next.
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
25. K个一组反转链表
灵神：初始化n为0记录链表长度，cur赋值为head，首先求出链表长度，初始化p0为哨兵节点dummy，pre为None，cur为head，while循环，进入条件为n≥k，n减去k，然后k次循环：nxt指向cur的next，更新cur的下一个节点为pre，更新pre为cur，cur为nxt。然后nxt赋值为p0的下一个节点，nxt的下一个节点为cur，p0的下一个节点为pre，p0更新为nxt。最后返回dummy.next。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
138. 随机链表的复制
灵神：如果原链表为空，则返回空；首先复制原链表节点，然后遍历原链表节点，复制原节点的random（cur.next.random=cur.random.next)，最后遍历新链表，分离新旧节点（删除原链表/恢复原链表）。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
148. 排序链表
灵神：使用分治或者归并，
23. 合并K个升序链表
146. LRU缓存
灵神：使用双向链表，定义一个双向链表的节点类（包含prev、next、key、value）；在init函数中，初始化capacity、哨兵节点、哈希表；定义get_node函数，先判断key是否在哈希表中，不在则返回空，否则从哈希表获取node，调用remove函数移除node，使用put_front函数移到前面，返回node；定义remove函数，两行代码改变x.next.prev和x.prev.next即可；定义put_front函数，将x节点放入dummy之后；实现get函数，只需要调用get_node函数，然后返回给node变量，如果node为空返回-1，否则返回node的值；实现put函数，调用get_node函数，如果node已经存在则改变node的值，返回，如果没有则更新哈希表，调用put_front函数，最后判断哈希表长度是否超出capacity范围。
- 时间复杂度：所有操作均为 O(1)。
- 空间复杂度：O(min(p,capacity))，其中 p 为 put 的调用次数。
- Python 实现
二叉树（15/15）
94. 二叉树的中序遍历
官方题解：在类中定义另一个函数inorder(参数为self、节点root、答案列表res），边界条件为root为空，则返回，然后递归左子树，将root的值放入res，再递归右子树。在中序遍历函数中，初始化数组res，然后调用inorder函数，最后返回res。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
104. 二叉树的最大深度
灵神：递归，递归边界：如果节点为空，返回0。先递归左子树，然后递归右子树，最后返回左子树和右子树的深度的较大值+1。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
226. 翻转二叉树
灵神：递归，递归边界：如果root为空，则返回空。翻转左子树，返回赋值给left；翻转右子树，返回赋值给right；left赋值给root.right，right赋值给root.left；返回root。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
101. 对称二叉树
灵神：写一个判断两树是否相同的函数isSameTree（100. 相同的树），讲函数改编为判断左右子树是否相同；主函数调用isSameTree，传入左子树和右子树。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
543. 二叉树的直径
灵神：递归求左右子树深度，更新ans，ans为左子树深度加右子树深度与ans取最大值；递归边界条件就是节点为空，返回-1；不为空，返回子树的深度。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
102. 二叉树的层序遍历
灵神：队列，如果root为空，则返回空；初始化ans记录答案，队列q（deque()），将root放入队列，循环边界：q为空，初始化val，for循环遍历q中元素，将q中节点popleft出来，然后值加入val，如果有左子树则将左子树放入q，如果有右子树则再放入右子树。循环最后把val放入ans中。返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
108. 将有序数组转换为二叉搜索树
灵神：
写法一：如果数组nums为空，直接返回None；初始化m为数组nums中间值，left为递归nums左半部分（除m），right为递归nums右半部分（除m），最后返回定义一个TreeNode节点，self.val =nums[m]，self.left = left, self.right = right。
写法二：直接return TreeNode(nums[m], dfs(left, m), dfs(m + 1, right))
- 时间复杂度：O(n)，其中 n 是 nums 的长度。每次递归要么返回空节点，要么把 nums 的一个数转成一个节点，所以递归次数是 O(n) 的，所以时间复杂度是 O(n)。需要注意，Python 的第一种写法有切片的复制开销，二叉树的每一层都需要花费 O(n) 的时间，一共有 O(logn) 层，所以时间复杂度是 O(nlogn)；第二种写法避免了切片的复制开销，时间复杂度是 O(n)。
- 空间复杂度：O(n)。如果不计入返回值和切片的空间，那么空间复杂度为 O(logn)，即递归栈的开销。
- Python 实现
98. 验证二叉搜索树
灵神：后序遍历，定义dfs函数：如果root为空则返回inf,-inf；递归左子树，返回左子树的最大最小值，递归右子树，返回右子树的最大最小值，然后和当前节点的值进行判断，是否符合二叉搜索树，如果不符，则返回-inf,inf；然后返回左子树和x中的较小值，右子树和x的较大值（x为当前节点值）。如果递归结果为inf，则返回false，否则为true。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
230. 二叉搜索树中第K小的元素
灵神：（中序遍历）记录答案，初始化ans为dfs的外部变量用来记录答案，定义函数：声明k，ans为nonlocal，如果当前节点是否为空或者k是否为0，则直接返回；然后递归到左子树，k-=1，如果k==0，则记录当前节点值到ans中，直接返回；否则继续递归右子树。最后调用dfs函数，返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(h)，其中 h 是树高，递归需要 O(h) 的栈空间。最坏情况下树是一条链，h=n，空间复杂度为 O(n)。
- Python 实现
199. 二叉树的右视图
灵神：初始化ans数组，定义 f 函数，参数是节点和当前深度depth：如果节点为空则返回空；然后判断深度是否等于答案长度，如果是则记录；然后先递归右子树，再递归左子树。然后调用f 函数，传入根节点和根节点深度0.
- 判断节点值是否需要被记入答案：如果递归深度等于答案长度，那么这个节点就需要记录到答案中。
- 时间复杂度 O(n)
- 空间复杂度 O(h)，其中 h 是二叉树的高度。递归需要 O(h) 的栈空间。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。
- Python 实现
114. 二叉树展开为链表
灵神：头插法，在函数外初始化一个全局变量head为空，然后实现该函数，如果根节点为空，则返回空；先递归右子树，再递归左子树，将左子树赋值为空，当前节点的右子树为head，然后将head赋值为当前节点。
- 时间复杂度 O(n)
- 空间复杂度 O(n)，最坏情况为一条链。
- Python 实现
105. 从前序与中序遍历序列构造二叉树
灵神：（优化后）使用哈希表保存中序遍历从值到下标的索引；然后定义dfs函数（传入参数为前序遍历和中序遍历的左右端点）：如果左端点等于右端点，那么返回空；计算左子树的大小为根节点值在中序遍历数组中的下标-中序遍历的左端点；递归返回左子树，递归返回右子树，返回根节点。
- 优化点：
- 使用哈希表储存中序遍历从值到下标的索引
- 递归传入参数改为数组的左右端点（左闭右开），避免复制数组
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
437. 路径总和3
灵神：做法类似于560题，使用前缀和+哈希表。初始化ans，带默认值的哈希表cnt，初始化cnt下标为0位置的值为1，定义dfs（传入参数为节点和到当前节点的和s）：如果当前节点为空，则返回空；然后s加上当前节点的值，ans加上cnt[s-target]，然后cnt[s]++, 递归到左子树，然后递归到右子树，然后恢复现场（（撤销 cnt[s] += 1））
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
236. 二叉树的最近公共祖先
灵神：先判断根节点是否为空，或者是否是p，或者是否是q，如果是则返回root；递归左子树，返回left，然后递归右子树，返回right；如果left和right都非空，则返回当前节点，如果只有left，则返回left，否则返回right。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
124. 二叉树中的最大路径和
灵神：方法和543二叉树的直径类似。初始化ans为负无穷，定义dfs函数，如果节点为空则返回0，然后递归左子树得到left，递归右子树得到right，函数内定义ans，然后更新答案ans为ans和左右子树之和+当前节点值取最大值，然后返回max(max(l_val,r_val)+node.val，0)，调用dfs函数，返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
图论（4/4）
200. 岛屿数量
灵神：初始化m,n为矩阵的长宽，然后定义dfs函数：如果出界，或者当前元素的值不为“1”，则直接返回，否则将当前位置赋值为“2”，递归上下左右。最后主要函数中，初始化ans，然后两层循环，如果当前值为“1”，则开始递归，ans+=1。
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
- Python 实现
994. 腐烂的橘子
灵神：多源BFS。初始化m,n为矩阵的长宽，fresh用于记录新鲜橘子的个数，数组q为记录腐烂橘子的位置；然后两层循环遍历统计新鲜橘子的个数和腐烂橘子的位置；初始化ans，循环边界为有腐烂橘子且有新鲜橘子，ans+=1表示过了一分钟，tmp赋值为q前一分钟所有腐烂橘子的位置，q为空数组，然后循环遍历tmp，内层循环遍历腐烂橘子的四个方向，如果在边界，且是新鲜橘子，则新鲜橘子减一，该位置赋值为腐烂橘子，记录腐烂橘子的位置在q中。最后如果fresh为零，则返回答案，否则返回-1.
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
- Python 实现
207. 课程表
灵神：初始化数组g(g = [[]for _ in range(numCourses)])，遍历prerequisites，给g中添加值。初始化colors为课程数*[0]。定义dfs函数（参数为x）：当前课程的颜色置为1，用y遍历当前课程的g（看当前课程x是哪些课程的前置课程），如果y的颜色为1（表示正在访问，冲突），或者y的颜色为0，且递归y后面的课程有正在访问，就说明有环，返回True。遍历完，将x的颜色置为2，返回False。在主函数中遍历colors，如果有元素为0，且递归有环，则返回False，遍历完，没有环就返回True。
- 时间复杂度 O(m+n)，，其中 n 是 numCourses，m 是 prerequisites 的长度。每个节点至多递归访问一次，每条边至多遍历一次。
- 空间复杂度 O(m+n)，存储 g 需要 O(n+m) 的空间。
- Python 实现
208. 实现Trie（前缀树）
灵神 ：定义一个Node类，写一行__slot__ = (’son’,’end’)来优化内存，定义init：self.son = {}和self.end默认值为False。
定义Trie类，在init中，初始化一个self.root = Node()；定义insert函数，cur为root，用c遍历word，如果c不在cur.son中就定义一个cur.son[c] = Node()，移动cur到对应的son，遍历结束将cur的end置为True；定义find，同样初始化cur为root，遍历word，如果c不在son中，就返回0，否则就移动cur到对应的son，遍历完，如果是end就返回1，否则返回2；定义search函数，直接调用find函数，返回值为1，就证明匹配成功。定义startWith函数，也是调用find函数，如果返回值不是0，就匹配成功。
- 时间复杂度：初始化为 O(1)，insert 为 O(n∣Σ∣)，其余为 O(n)，其中 n 是 word 的长度，∣Σ∣=26 是字符集合的大小。注意创建一个节点需要 O(∣Σ∣) 的时间（如果用的是数组）。
- 空间复杂度：O(qn∣Σ∣)。其中 q 是 insert 的调用次数。
- Python 实现
回溯（8/8）
46. 全排列
灵神：初始化数组nums的长度为n，数组ans，以及数组path。定义dfs函数，i和s两个参数：如果i等于n，则将path的copy加入到ans中，返回；否则遍历s，path[i]赋值为x，然后递归到下一个。最后调用dfs(注意要传入set(nums))，返回ans.
- 时间复杂度 $O(n\cdot n!)$
- 空间复杂度 O(n)
- Python 实现
78. 子集
灵神：初始化数组ans，path，变量n为nums大小；定义dfs函数（传入参数i）：如果 i 等于n，则将path加入到ans中，返回；然后就是不选的情况，直接递归到i+1，选的话就是先把下标为 i 的nums的值加入到path中，然后递归到i+1，最后恢复现场。在外层函数中调用dfs，返回ans。
- 时间复杂度 $O(n2^n)$
- 空间复杂度 O(n)
- Python 实现
17. 电话号码的字母组合
灵神：在类外初始化一个MAPPING = “”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “wxyz”.
初始化n为digits的长度，如果n为0，直接返回空数组；初始化数组ans和path，定义dfs函数（传入参数i）：如果i等于n，就path(用join函数组合起来）加入到ans中，然后返回，否则遍历i所对应的MAPPING中的字母，加入到path中，递归到i+1，然后path恢复现场。最后调用dfs，返回ans.
- 时间复杂度 $O(n4^n)$
- 空间复杂度 O(n)
- Python 实现
39. 组合总和
灵神：选或不选。初始化数组ans,path, n为candidate的长度，定义dfs函数（参数为i和left(剩余的target)）：如果left==0，直接将path加入ans，然后返回；如果left<0或者i==n，直接返回；然后不选，然后选，然后恢复现场。最后调用dfs，返回ans.
- 剪枝优化：把 candidates 从小到大排序，如果递归中发现 left<candidates[i]，由于后面的数字只会更大，所以无法把 left 减小到 0，可以直接返回。
- 时间复杂度 $\mathcal{O}\left(n\log n+\frac{e^{\pi\sqrt{(2/3)-\text {target}}}}{\text {target}}\right)$
- 空间复杂度 O(target)
- Python 实现
22. 括号生成
灵神：初始化m等于2*n，数组ans和path。定义dfs函数（两个参数i和open（左括号个数））：如果i==m，就将path加入到ans中，返回；如果open小于n，就可以选左括号，递归；如果右括号数（i-n）小于左括号数，就可以选右括号，递归。最后调用dfs函数，返回ans.
- 时间复杂度 $\mathcal{O}\left(\frac{4^{n}}{\sqrt{n}}\right)$
- 空间复杂度 O(n)
- Python 实现
79. 单词搜索
灵神：初始化m,n为board的长和宽。定义dfs函数（参数为i,j,k（i,j表示board的位置，k表示word的第几个））：如果当前board的值不等于work[k]的值，返回False；如果k为word长度减一，就匹配成功，返回True；否则就是当前值匹配到了，然后将board当前位置标记为匹配过（赋值为‘ ’），然后用x,y变量遍历i,j周围的位置，如果位置在界内，且递归为真，就返回True；遍历完，恢复现场，返回False。最后遍历board中的所有位置为起始位置，如果调用dfs函数为真，则返回True，遍历完，则返回False。
- 优化一：先使用Counter函数统计board中字母出现的次数，如果少于word中出现的次数，直接返回False。（附：
cnt = Counter(c for row in board for c in row)） 优化二：如果 word=abcd 但 board 中的 a 很多，d 很少（比如只有一个），那么从 d 开始搜索，能更快地找到答案。（即使我们肉眼去找，这种方法也是更快的）
时间复杂度：$O(mn3^k)$，其中 m 和 n 分别为 grid 的行数和列数，k 是 word 的长度。除了递归入口，其余递归至多有 3 个分支（因为至少有一个方向是之前走过的），所以每次递归（回溯）的时间复杂度为 $O(3^k)$，一共回溯 O(mn) 次，所以时间复杂度为 $O(mn3^k)$。
- 空间复杂度：O(∣Σ∣+k)。其中 ∣Σ∣=52 是字符集合的大小。递归需要 O(k) 的栈空间。部分语言用的数组代替哈希表，可以视作 ∣Σ∣=128
131. 分割回文串
灵神：子集型回溯。初始化数组ans,path和n，然后定义dfs函数，递归边界如果i==n，就把path加入到答案中（记得要copy），然后返回；否则遍历i之后的位置，t为截取j+1之前的子串，如果t为回文串（t==t[::-1]）则加入到path，在向后递归，然后恢复现场。最后返回ans。
- 时间复杂度 $O(n2^n)$
- 空间复杂度 O(n)
- Python 实现
51. N皇后
灵神：
- 这是排列型回溯，初始化ans和col，col中存放每行中的皇后放在哪一列，然后定义一个valid函数传入行和列，判断对角线是否冲突；定义dfs函数，传入为r和s(0~n的数组)，如果当前的行数等于n, 则将答案加入到ans中；遍历s数组，如果valid，那么放置皇后，递归下一步传入r+1和s-{c}。
- 时间复杂度 O($n^2$*n!)
- 空间复杂度 O(n)
- Python 实现
- 优化：因为 valid函数的复杂度有O(n*n!)，优化使得判断valid的复杂度变为O(1)
- 时空复杂度同上
- Python实现
二分查找（6）
35. 搜索插入位置
灵神：左闭右开。初始化left和right，while循环，条件为left<right，mid为left和right的和除以2取整，如果mid位置的元素小于目标值，则更新left为mid+1，否则更新right为mid。最后返回left（或者right）
- 时间复杂度 O(logn)
- 空间复杂度 O(1)
- Python 实现
可以直接使用库函数：bisect_left(数组，target)，返回为应该插入的位置下标。
- Python 实现
74. 搜索二维矩阵
灵神：二分查找，左闭右开。初始化m、n分别为matrix的长和宽，left和right分别为0和m*n。while循环，条件为left<right，mid为left+right整除2，x为matrxi横纵下标分别为mid//n和mid%n；如果x等于目标值，直接返回True；如果x小于目标值，更新left为mid+1，否则更新right为mid。循环结束，意味着没有找到target，直接返回False。
- 时间复杂度 O(logmn)
- 空间复杂度 O(1)
- Python 实现
34. 在排序数组中查找元素的第一个和最后一个位置
灵神：定义一个函数low_bound，类似于35题，可以找出查找元素的第一个位置。在题目函数中调用low_bound函数，返回值赋值给start，如果start等于数组长度，或者下标为start的元素不等于target，则没有找到目标元素；end就等于使用low_bound函数寻找target+1位置的小标-1，最后返回start和end组成的数组。
- 时间复杂度 O(logn)
- 空间复杂度 O(n)
- Python 实现
33. 搜索旋转排序数组
灵神：写一个153.寻找旋转排序数组中的最小值的函数，再写一个类似于35.搜寻插入位置的函数lower_bound（参数为数组，left,right,target），调用findMin函数，返回值赋值给min_index，如果target小于min_index位置元素，就返回-1；如果target大于最后一个元素，就返回 函数lower_bound的返回值（left=0,right=min_index），否则返回 函数lower_bound的返回值（left=min_index, right = len(nums））。
- 时间复杂度 O(logn)
- 空间复杂度 O(1)
- Python 实现
153. 寻找旋转排序数组中的最小值
灵神：和最后一个元素比大小，使用二分查找（左闭右开）。初始化n为数组长度，left和right分别为0和n。while循环，条件为left<right：mid为left+right整除2，如果mid位置元素大于最后一个元素，更新left为mid+1，否则更新right为mid。最后返回left位置的元素值。
- 时间复杂度 O(logn)
- 空间复杂度 O(1)
- Python 实现
4. 寻找两个正序数组的中位数
灵神：如果a数组的长度大于b数组，就交换两个数组（保证下面的 i 可以从 0 开始枚举）。初始化m,n为数组a，b的长度，给数组a，b的首尾分别加上负无穷和正无穷。初始化left = 1，right = m+1，while循环，条件为left<right(左闭右开二分），给 i 赋值为left和right平均取整，给 j 赋值为(m+n+1)//2-i （即为有第一组中的元素在数组b中），然后如果a[i]小于等于b[i+1]，左边界left就更新为i+1，否则更新右边界为 i。最后循环结束，初始化i为left-1（因为循环结束时，left 是第一个不满足 a[i] <= b[j+1] 的位置，所以合法的最大 i 是 left - 1），j使用和循环中相同的公式更新，然后求$ai$和$b_j$的最大值，求$a{i+1}$和$b_{j+1}$的最小值，如果两数组长度和为奇数，就直接返回最大值，否则返回最大值和最小值的均值。
- 时间复杂度 O(log min(m,n))
- 空间复杂度 O(1)
- Python 实现
栈（5/5）
20. 有效的括号
灵神：先判断字符串长度是否为偶数，然后再初始化哈希表mp（key为右括号，value为左括号），和栈st，然后遍历s，如果当前字符为左括号就加入st，否则st为空，或者为左括号且与栈顶不匹配就返回false，最后判断st是否为空，为空则true，否则false。
- 时间复杂度：O(n)，其中 n 是 s 的长度。
- 空间复杂度：O(n) 或 O(1)。如果能修改 s，那么直接把 s 当作栈，可以做到 O(1) 额外空间。
- Python 实现
155. 最小栈
灵神：栈中除了保存添加的元素，还保存前缀最小值。（栈中保存的是 pair）
- 时间复杂度：所有操作均为 O(1)。
- 空间复杂度：O(q)。其中 q 是 push 调用的次数。最坏情况下，只有 push 操作，需要 O(q) 的空间保存元素。
- Python 实现
394. 字符串解码
灵神：递归解决。分三种情况：第一种就是s为空，则返回空，第二种s为字母（isalpha函数），则可以分解为s0+解码剩下的，第三种s为数字，使用find函数找到第一个左括号的下标，使用变量balance保存左括号减去有括号的个数，一旦balance=0，就找到了与第一个左括号所对应的右括号，然后分成三部分（第一部分为第一个左括号之前转为数字，乘上第一个左括号与右括号的解码，再加上剩余的解码），然后返回。
- 时间复杂度：$O(U^m)$
- 空间复杂度：$O(U^m)$
- Python 实现
739. 每日温度
灵神：单调栈。首先初始化n为temperatures的长度，n位数组ans，还有单调栈st，然后从右到左遍历temperatures数组，t为第i个temperature的值，while循环条件为st不为空且t大于等于栈顶元素位置的值，则pop栈顶，然后如果st不为空，则当前的ans就是栈顶元素减去当前位置下标，然后将i放入堆栈。返回ans
- 时间复杂度 O(n)
- 空间复杂度：O(min(n,U))，其中 U=max(temperatures)−min(temperatures)+1。
- Python 实现
84. 柱状图中最大的矩形
灵神：初始化n为heights长度，left为长度为n，默认值为-1的数组，st为单调栈，先遍历求每个元素左边第一个比他小的元素的下标；清空st单调栈，然后初始化right为长度为n，默认值为n的数组，然后从后向前遍历，保存每个元素右边第一个比他小的元素。最后再遍历每个元素（高），然后求最大面积。
- 以上为三次遍历
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
堆 （3）
215. 数组中的第K个最大元素
灵神：
直接调用库函数
ranges::nth_element(nums, nums.end() - k);
return nums[nums.size() - k];
- C++ 实现
O(n) 快速选择算法
定义另一个函数partition：在子数组 left,right中，选一个基准元素 pivot；将基准元素和 left元素交换；赋值 i,j 为 left,right；循环True（套两个循环调整 i 和 j 的位置，如果 i ≥ j就break跳出，否则就交换位置 i, j 的元素，然后更新 i，j）；再把pivot交换为合适位置，将left元素和j位置元素交换；最后返回 pivot 位置 j；
主要的实现函数：初始化长度n,目标位置下标，以及left和right；无限循环：调用函数返回位置下标i,判断是否为目标下标，如果大调整right,如果小调整left。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
347. 前K个高频元素
灵神：第一步：统计每个元素的出现次数；第二步：把出现次数相同的元素，放到同一个桶中；第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
295. 数据流中的中位数
灵神：使用最大堆和最小堆实现（始终保持左一半left的大小大于右一半的大小right），left使用最大堆，使用最小堆来存放相反数来实现，right使用最小堆；
具体实现：使用heappushpop, headpushpop_max, heappush_max, heappush实现
- addNum：如果left大小等于right，就先加入right，pop出最小值加入left；如果不相等，就先加入left，pop出最小值取反，然后加入right。
- 找中位数时间复杂度为 O(1)，添加元素时间复杂度为 O(logq)，q为addNum的调用次数；
- 空间复杂度 O(q)
- Python 实现
贪心算法（4/4）
121. 买卖股票的最佳时机
灵神：初始化ans和minprice，遍历prices数组，更新ans为ans和当前元素减去minprice的较小值，更新minprice为minprice和当前元素的较小值。最后返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
55. 跳跃游戏
灵神：
- 算法如下：
- 从左到右遍历 nums，同时维护能跳到的最远位置 mx，初始值为 0。
- 如果 i>mx，说明无法跳到 i，返回 false。
- 否则，用 $i+nums_i$更新 mx 的最大值。
- 如果循环中没有返回 false，那么最后返回 true。
- 也可以在 mx≥n−1 时就返回 true，这可以让我们提前退出循环。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
45. 跳跃游戏2
灵神：造桥原理，初始化ans和已造的桥的右端点cur_right,下一座桥的右端点next_right,然后遍历数组-1，更新next_right为之前的next_right和当前点可造桥长度的较大值，如果当前下标等于当前桥的右端点，就必须要造桥了，将当前桥右端点更新，ans+=1. 最后返回ans.
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
763. 划分字母区间
灵神：统计每个字母最后出现的下标，然后初始化ans数组，start和end，再次遍历 s，由于当前区间必须包含所有 s[i]，所以更新end为end和last[s[i]]的较大值。如果发现 end=i，那么当前区间合并完毕，把区间长度 end−start+1 加入答案。然后更新 start=i+1 作为下一个区间的左端点。遍历完毕，返回答案。
- 时间复杂度 O(n)
- 空间复杂度 O(∣Σ∣)。其中 ∣Σ∣ 是字符集合的大小，本题字符均为小写字母，所以 ∣Σ∣=26。
- Python 实现
动态规划（10）
70. 爬楼梯
灵神：定义dfs函数，递归边界：$dfs(0)=1, dfs(1)=1$。从 0 爬到 0 有一种方法，即原地不动。从 0 爬到 1 有一种方法，即爬 1 个台阶。然后状态转移方程如下：
最后，调用dfs函数，递归入口：$dfs(n)$，也就是答案（爬 n 个台阶的方案数）。
- 动态规划+记忆化搜索
- 时间复杂度 O(n)
- 空间复杂度 O(n)
Python 实现
1:1翻译递推+空间优化
- 时间复杂度 O(n)
- 空间复杂度 O(1)
118. 杨辉三角
解法：初始化空列表c，然后循环numRows次：创建长度为 (i+1) 的子列表，所有元素初始化为 1；将子列表添加到主列表。然后两层循环，外层循环从第2行开始遍历到numRows-1，内层循环遍历从1到i-1, 然后当前元素就等于上一行元素的下标为 j-1 的元素加上下标为 j 的元素。
- 时间复杂度 $O(numRow^2)$
- 空间复杂度 O(1)
- Python 实现
198. 打家劫舍
灵神：初始化n为nums的长度，定义dfs函数，递归边界：如果 i 小于0，返回0，否则就状态转移方程：
最后，调用函数dfs，递归入口为dfs(n-1)
- 动态规划+记忆化搜索
- 时间复杂度 O(n)
- 空间复杂度 O(n)
Python 实现
1:1翻译递推+空间优化
- 时间复杂度 O(n)
- 空间复杂度 O(1)
279. 完全平方数
灵神：动态规划
记忆化搜索：在类外定义一个dfs函数：递归边界：如果等于dfs(0,0)=0，因为没有数可以选了，且要得到的数等于 0，那么答案为 0。如果 j>0，那么 dfs(0,j)=∞，这里用 ∞ 表示不合法的状态，从而保证上式中的 min 取到合法的状态。注意本题是一定有解的，因为 1 是完全平方数。在类中的函数调用dfs函数，递归入口：由于$i^2$≤n，所以i≤⌊n⌋，所以递归入口为dfs(⌊n⌋,n)，也就是答案。
动态转移方程：选或者不选，如果$j<i^2$就只能不选，如果$j \geq i^{2}$就可以选择选或者不选。
$dfs(i,j) = \left{
\begin{matrix}
dfs(i-1, j), & j < i^{2} \
\min \left( dfs(i-1, j), dfs(i, j-i^{2}) + 1 \right), & j \geq i^{2}
\end{matrix}
\right.$时间复杂度 $O(n\sqrt{n})$
空间复杂度 $O(n\sqrt{n})$
Python 实现
322. 零钱兑换
灵神：
- 记忆化搜索
- 递归边界：如果i小于0，那么如果amount==0，则返回0，不为0，则返回inf；如果当前的coins[i]>剩余总额，则一定不选；然后返回选或者不选的最小值；
- 时间复杂度：O(n⋅amount)，其中 n 为 coins 的长度。
- 空间复杂度：O(n⋅amount)。
- Python 实现
- 1:1 翻译递推+空间优化
- 时间复杂度：O(n.amount)
- 空间复杂度：O(amount)
139. 单词拆分
灵神：初始化max_len为wordDict中最长字符串的长度，words为wordDict的set类型的哈希表；定义dfs函数，递归边界：如果 i 等于0，则返回true，然后用 j 遍历在 i-1 到 max(i-max_len-1,-1) 的长度中有无在哈希表中的，如果有，且递归到dfs(j)为真，则返回True，遍历完没有的话，就返回false。
最后，调用dfs函数，递归入口：dfs(n)，也就是答案。
- 递归搜索+保存递归返回值 = 记忆化搜索
- 时间复杂度 $O(mL+nL^2)$，m为wordDict的长度，L为wordDict中最长字符串的长度，n为s的长度；
- 空间复杂度 $O(mL+n)$
- Python 实现
300. 最长递增子序列
灵神：使用子集型回溯来解决，dfs中遍历所有i之前的数，小于nums[i]，则递归此值的下标；遍历完返回res+1；没有写递归边界，因为i如果等于零，就不会进入遍历循环中。
- 注意：要遍历从所有的位置开始；如果翻译为递推形式时，初始化f = [0]*n；
- 时间复杂度 $O(n^2)$；
- 空间复杂度 O(n)，需要 O(n)个递归空间；
Python 实现
贪心+二分查找：初始化一个数组g，遍历数组nums元素为x，j 为二分查找x在g中的位置（bisect_left函数），如果变量j和数组g的长度相同，那么就把x加到数组g的后面，否则就把数组g下标为j的元素替换为x，最后返回g的长度。
- 时间复杂度 O(nlogn)
- 空间复杂度 O(n)
- Python 实现
152. 乘积最大子数组
灵神：初始化n，定义$f{max}$和$f{min}$数组，初始化为nums[0]，由于以nums[0] 为右端点的子数组乘积只能是nums[0]，所以初始值为fmax[0]=fmin[0]=nums[0]。遍历数组nums（从1到n-1），x=nums[i]，然后再更新fmax[i]和fmin[i]的值（更新规则如下），最后返回fmax数组的最大值。
- 以上为动态规划，更新状态转移方程求解方法，并没有空间优化
- 时间复杂度 O(n)
- 空间复杂度 O(n)
- Python 实现
- 空间优化：初始化ans为负无穷，两个变量f_max和f_min，初始化为1，然后用x遍历nums，同时更新f_max和f_min（必须同时更新，否则会产生依赖冲突），然后更新ans为ans和f_max的较大值。最后返回ans。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
416. 分割等和子集
灵神：定义一个cache进行记忆化搜索，定义dfs函数：递归边界为dfs(−1,0)=true, dfs(−1,>0)=false。注意 j 是从 s/2 开始倒着减的，如果 j 能减小成恰好等于 0，就表示找到了一个和恰好等于 s/2 的子序列。如果j小于当前值，就只能不选，否则就可以选或者不选。递归入口：dfs(n−1,s/2)，即答案。
- 以上为记忆化搜索
- 时间复杂度 O(ns)
- 空间复杂度 O(ns)
- Python 实现
- 空间优化
- 时间复杂度 O(ns)
- 空间复杂度 O(s)
32. 最长有效括号
灵神：初始化栈st（后进先出）（第一个元素为-1表示红线）,ans=0，然后遍历s,下标为i，元素为ch，如果当前元素为左括号（炸弹），则加入栈中，否则如果当前栈的长度大于1（隐藏条件是当前元素为右括号），则将栈顶pop（拆弹），然后更新ans为ans和当前下标减去栈顶的较大值，否则就是触碰到了红线，需要更新红线下标。最后返回答案ans。
- 时间复杂度：O(n)，其中 n 是 s 的长度。
- 空间复杂度：O(n)。栈保存 O(n) 个下标，需要 O(n) 的空间。
Python 实现
空间优化
- 时间复杂度 O(n)
- 空间复杂度 O(1)
多维动态规划（5/5）
62. 不同路径
灵神：定义状态为 dfs(i,j)，表示从起点 (0,0) 走到 (i,j) 的路径数。
讨论我们是如何到达 (i,j) 的：
- 如果是从 (i−1,j) 过来，那么问题变成从起点 (0,0) 走到 (i−1,j) 的路径数，即 dfs(i−1,j)。
- 如果是从 (i,j−1) 过来，那么问题变成从起点 (0,0) 走到 (i,j−1) 的路径数，即 dfs(i,j−1)。
这两种情况互斥，根据加法原理，有
dfs(i,j)=dfs(i−1,j)+dfs(i,j−1)
递归边界：
- dfs(−1,j)=dfs(i,−1)=0。无法从 (0,0) 到达这些位置。
- dfs(0,0)=1。起点到它自己有一条路径，即原地不动。
递归入口：dfs(m−1,n−1)，这是原问题，也是答案。
- 以上为动态规划+记忆化搜索
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
Python实现
1:1翻译为递推+空间优化
- 时间复杂度 O(mn)
空间复杂度 O(n)
组合数学
- 时间复杂度 O(min{m,n})
- 空间复杂度 O(1)
64. 最小路径和
灵神：初始化m和n，然后记忆化搜索，定义dfs函数，递归边界：如果 i 小于0，或者 j 小于0，就返回正无穷；如果 i 和 j 都等于0，就返回当前值（grid[0][0]）。然后状态转移方程就是
最后，调用dfs函数（递归入口就是dfs(m-1,n-1)）
- 动态规划+记忆化搜索
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
Python 实现
1:1翻译为递推+空间优化
- 时间复杂度 O(mn)
- 空间复杂度 O(n)
5. 最长回文子串
灵神：如果用暴力的做法，那么判断子串是否回文就需要O(n)的时间复杂度，遍历子串也需要$O(n^2)$的复杂度，那么整个算法就需要$O(n^3)$的复杂度；
- 中心扩展法
- 将判断子串是否回文的复杂度降到O(1)，分为字符串长度为奇数和字符串长度为偶数来判断子串是否回文；
- 时间复杂度 $O(n^2)$
- 空间复杂度 O(1)
- Python 实现
- Manacher 算法
1143. 最长公共子序列
灵神：初始化两个字符串长度m和n，然后记忆化搜索，定义dfs函数，如果i或者j小于0，就直接返回0，如果当前两个字符相同，就返回递归到都选的情况然后再+1，否则直接返回选i不选j，不选i选j的较大值。最后返回调用dfs函数。
- 动态规划+记忆化搜索
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
Python 实现
1:1翻译递推+空间优化
- 时间复杂度 O(mn)
- 空间复杂度 O(n)
72. 编辑距离
灵神：初始化m和n分别为s,t长度，定义dfs函数，递归边界：如果 i<0，则返回 j+1；如果 j<0，则返回 i+1，然后状态转移方程如下：
最后，调用dfs函数，递归入口为dfs(m-1,n-1)
- 动态规划+记忆化搜索
- 时间复杂度 O(mn)
- 空间复杂度 O(mn)
Python 实现
1:1翻译递推+空间优化
- 时间复杂度 O(mn)
- 空间复杂度 O(n)
技巧（5/5）
136. 只出现一次的数字
169. 多数元素
灵神：初始化ans和hp（血量），然后遍历数组，如果当前hp为零，则将ans赋值为x,hp赋值为1，否则判断当前元素是否为ans，如果是则hp++,否则hp—.
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
75. 颜色分类
可以直接使用排序函数，但是时间复杂度应该会是O(nlogn).
灵神：初始化p0和p1等于1，然后用 i,x 遍历数组中的元素，现将元素置为2；然后如果x小于等于1，则，下标为p1位置赋值为1，然后加一；如果x等于0，则置为0，p0+=1.
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
31. 下一个排列
灵神：
第一步：从右向左找到第一个小于右侧相邻数字的数 nums[i]；
如果找到了，进入第二步；否则跳过第二步，反转整个数组
第二步：从右向左找到 nums[i] 右边最小的大于 nums[i] 的数 nums[j]
第三步：反转 nums[i+1:]（如果上面跳过第二步，此时 i = -1）
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现
287. 寻找重复数
灵神：代码逻辑同环形链表2. 初始化快慢指针都指向nums的下标0；然后无限循环，slow = nums[slow]（等同于环形链表中的slow = slow.next），同理fast = nums[nums[fast]]，然后如果快慢指针相同则break跳出循环；初始化头结点head= 0, 然后让头结点和慢指针同时向前，相遇是即为入环口，返回head即可。
- 时间复杂度 O(n)
- 空间复杂度 O(1)
- Python 实现