leetcode-python

记录一下自己做过的leetcode题，代码在code中。（持续更新）

每题都包含：

1. 题目的难易度
2. 原题链接，题目内容
3. 解题思路
4. python代码

做题总结

排序算法

十大经典排序算法

---

位运算

136. 只出现一次的数字， 137. 只出现一次的数字 II， 260. 只出现一次的数字 III

---

股票问题

一种简单的动态规划解决股票6问

---

二叉树的非递归遍历

• 中序遍历
• 前序遍历
• 后续遍历

前序遍历和后续遍历可以看成是一种（后续遍历中有介绍）

---

回溯问题

例：46-全排列， 22-括号生成
解决一个回溯问题，实际上就是一个决策树的遍历过程。考虑三个问题

1. 路径：即已经做出的选择
2. 选择列表：即当前还可以做的选择
3. 结束条件：到达决策树底层时，已无法再选择了

代码框架：核心就是for循环中的,即递归前做选择，递归后撤销选择, 撤销选择是为了不让当前选择影响到其他平行的选择

ans = []
def backtrack(路径，选择列表):
  if 满足条件(一般是没有选择了):
    ans.append(路径)
    return
  
  for 选择 in 选择列表:
    # 1. 做选择
    从选择列表中删除选择
    添加选择到路径
    # 2. 递归
    backtrack(路径，选择列表)
    # 3. 撤销选择
    从选择列表中添加选择
    删除路径中的选择

如果我们使用的路径、选择是相互独立的，就不用撤销选择，可见22-括号生成

子集/组合/排列问题

• 该类问题都可以抽象为树的遍历问题。
• 子集&组合问题是没有顺序的；排列问题是有顺序的。
• 无重复元素问题
  • 因此子集&组合的遍历是不完全树，可以通过start（索引）来对树进行减枝，即我们通过保证元素之间的相对顺序不变来防止出现重复的子集&组合。如78. 子集，77. 组合。
  • 排列问题通常通过一个集合(set)记录下访问过的元素，避免重复访问。如46. 全排列。子集&组合通过上述方法已经避免了重复访问。
• 有重复元素问题：
  • 避免出现重复解：避免同一层中，选择相同的值
  • 子集&组合: 通过对原始数组进行排序；若当前值与上一个值相同，则跳过（因为上一个值是必选的）。从而避免了同一层选择相同的值。90. 子集 II，40. 组合总和 II。
  • 排列: 通过使用当前层一个集合(cur_set)来判断是否选择了重复值。47. 全排列 II。

---

二分查找

二分查找思路虽然简单。。。但是细节真是要命。
这里用统一的思维解决所有二分查找问题。

• 二分查找流程（三步骤）：
  1. 先筛选特例： 例如：数组为空，或待查元素大于最大元素，导致下标溢出
  2. 框架：
     • 使用while l<r, l=0, r=size-1, 这样while出来后一定是l=r。 是左闭右闭区间。
     • mid = (l+r)//2 向下取整 或 mid = (l+r+1)//2 向上取整；具体根据情况，下面会介绍
     • 利用排除法：排除肯定不是解的部分，那么剩下就是解了。把肯定不是解的放在if中。
  3. 根据题目看是否需要对最终选出的元素进行判断。
• 如果 else 下是l=mid，则要向上取整；否则可能会跳不出while
• 可以看看34-在排序数组中查找元素的第一个和最后一个位置和 35-搜索插入的位置加深理解
• 此外，旋转排序数组的题目也可以练练，进一步熟悉下： 33-搜索旋转排序数组, 81-搜索旋转排序数组 II, 153-寻找旋转排序数组中的最小值, 154-寻找旋转排序数组中的最小值 II

---

并查集

并查集经常用于：变量之间的关系具有传递性时
并查集基本模板

无权重并查集 547. 省份数量, 990. 等式方程的可满足性, 785. 判断二分图, 130. 被围绕的区域
带权重并查集 399. 除法求值