61. 旋转链表
所谓旋转就是把需要断开的地方断开，断开处右边为新的头结点，以及把链表尾部与head连起来。
找到断点可以 用双指针，while count < k：指针 p1 到达第 k 个结点时（之前如果 p1.next=None，就从head从头开始），p2 从头结点开始，两个指针一起遍历。直到 p1.next == None，此时p2就是断点，使 p1.next = head，然后p2.next为新的头结点。
找结点时可以优化，比如对于 [1,2,3]，k = 50，当 p1 第一次到达链表末尾时，使 k = k % count，count = 0，减少循环次数。
62. 不同路径
① 刚好组合数学学过，这个问题可以看作是 m-1 个 → 与 n-1 个 ↓ 有多少种排列。假设每个相同方向的箭头是不同的个体，那么排序数是 [(m-1)+(n-1)] !，由于相同方向的箭头在排序上是等价的，所以要再除以两个方向箭头的内部排序数：(m-1) ! 和 (n-1) !。即结果为 [(m-1)+(n-1)]! / (m-1)! (n-1)!。
② 动态规划。到达每格的路径数等于左边一格路径数加上上面一格路径数，第一行和第一列 dp 都为 1。初始化二维数组 dp：dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]。二层循环访问所有网格（除了第一行第一列）：dp[i][j] = dp[i-1][j] + dp[i][j-1]。最后返回 dp[-1][-1]。
优化内存，不需要保存整个 dp，只用保存前一行和本行即可。再优化，前一行也不需要保存，cur = [1] * n，两层遍历都从 1 开始，每次加了以后覆盖前一行：cur[j] += cur[j-1]。
63. 不同路径 II
如果 obstacleGrid[i][j] = 1，则这格 dp = 0，如果这格是第一行或第一列的，则这行或列后面的 dp 都是 0。其他和 62 题一样。
64. 最小路径和
动态规划。到每格的最小和 = 上格与左格中较小值 + 本格的值。直接在数组 grid 中本格存储路径的和不需要额外空间。grid[i][j] += min(grid[i-1][j], grid[i][j-1]) 。
65. 有效数字
呃。。。
66. 加一
从后往前每位加1，如果大于等于10就-10，小于10就 return，到了最高位要进位就 digits.insert(0,1)。循环正常结束则 digits.insert(0,1)
67. 二进制求和
① 逐位加，短的数0补齐，carry 表示进位，a 和 b 都加到 carry，carry 低位加入结果，高位作为进位，将结果保存在新列表。
② 位操作。^ 操作得到两个数字无进位相加的结果 a，& 操作得到进位 b。将 a 和 b 相加，依然是二进制求和得到无进位结果与进位，循环直到进位为 0。
把 a 和 b 转换成整型数字 x 和 y，x 保存结果，y 保存进位。当进位 y != 0：
计算当前 x 和 y 的无进位相加结果：answer = x^y。
计算当前 x 和 y 的进位：carry = (x & y) << 1。
更新 x = answer，y = carry。
返回 x。
68. 文本左右对齐
呃。。。
69. x 的平方根
① 二分法。由于 a 一定是整数，此问题可以转换成在有序整数集中寻找一个特定值，可以使用二分查找。
如果 x < 2，返回 x。令左边界 left 为 2，右边界 right 为 x // 2。其他和标准二分差不多。
② 牛顿法。迭代公式：xk+1 = (xk + x/xk) / 2。xk 为逼近 x 的数。
x1初值任意（大于0），当结果变化小于指定数时停止迭代 while abs(x0 - x1) >= 1：记录上个数 x0 = x1，然后计算 x1 = (x0 + x / x0) / 2。
③ 递归+位操作。√x = 2 * √(x/4)。<< 左移用来乘 2， >> 右移用来除 2，因此 mySqrt(x) = mySqrt(x>>2) << 1。
如果 x 小于 2，有√x返回 x。left = self.mySqrt(x >> 2) << 1。right = left + 1。return left if right * right > x else right。
* 这类题可以思考 f(x) 与 f(x//2) 之类的关系，然后用递归。
比如第50题 Pow(x, n)，n 是偶数则 xn = xn/2 * xn/2 ，如果是奇数则 xn = xn/2 * xn/2 * x。
70. 爬楼梯
① 动态规划。到达第 i 阶的方法总数就是到第 i-1 阶和第 i−2 阶的方法数之和。初始化第 1 和 2 阶，从 3 开始：dp[i] = dp[i-1] + dp[i-2]。
② 斐波那契数。dp[i] 是第 i 个斐波那契数。每次循环：third = first + second，first = second，second = third。和动态规划差不多，省点空间。
71. 简化路径
① 直接。把 '/' 之间的字符串提取出来，检查后放到列表 words：空字符跳过，'.' 跳过，‘..’ 去掉列表前一个元素，其他字符加入列表。最后返回 '/' + '/'.join(words)。
可以用字典代替 if：for s in path.split('/'): words = {'': words, '.': words, '..': words[:-1]}.get(s, words + [s])。
② 栈。每个词压栈，遇到 '..' 出栈，'.' 不做操作，最后出栈即可。
72. 编辑距离
动态规划。和第44题差不多思路。dp[i][j] 等于 word1 前 i 个字母与 word2 前 j 个字母的编辑距离（word1[:i-1] 与 word[:j-1]）。三种操作对应了三种根据前面的 dp 求得 dp[i][j]的方法：
(1) 插入: dp[i][j] = dp[i-1][j] + 1 (2) 删除: dp[i][j] = dp[i][j-1] + 1 (3) 替换: 如果 word1[i-1] == word[j-1] 则 dp[i][j] = dp[i-1][j-1] + 1，否则 dp[i][j] = dp[i-1][j-1]
初始化第一行与第一列：dp[i][0] = i 和 dp[0][i] = i。两层循环遍历 dp，每次选择以上三种操作中最小的一个数写入 dp[i][j]。
73. 矩阵置零
如果格子为 0 就保存它的行号和列号，最后进行修改。定义两个数组 row 和 col，分别保存为 0 的元素的行号和列号。遍历整个矩阵，如果元素为 0 就 row.append(i)，col.append(j)。最后再把 row 和 col 在 matrix 中对应的行和列的所有元素改为 0。
74. 搜索二维矩阵
两次二分查找，先二分对比 matrix[mid][0] 和 target，定位到所在行，常规二分出来时，所在行 row = left - 1（二分结束左边界是大于target的）。再在行里二分查找 target。
75. 颜色分类
三路快排，三个指针 left、right、cur，遍历一遍数组，将当前指针cur访问到的元素放到正确的位置去即可。
初始化 left = 0，cur = 0，right = len(nums) - 1。while cur <= right：
(1) if nums[cur] == 0，交换 nums[cur] 和 nums[left]，left 和 cur 都加一（左边已经排好，left相当于0和1的边界。如果左边有1，left一定会把1换过来；如果左边没有1而都是0，换过来的0也不影响排序）。
(2) if nums[cur] == 2，交换 nums[cur] 和 nums[right]，cur不变。
(3) if nums[cur] == 1，cur加一。
76. 最小覆盖子串 *
滑动窗口。
left 指针和 right 指针都指向 s 的第一个元素。将 right 右移，扩张窗口，直到得到一个包含 t 的全部字母的窗口。得到可行的窗口后，将 left 逐个右移，得到最小可行窗口大小。left 右移到某处若窗口不再可行，则继续 right 右移，循环。
判断是否是可行窗口：
把 t 的字母存在字典，dict_t = Counter(t)，t 的不重复字母个数 required = len(dict_t)，窗口字母存在字典 windows_counts = {}，窗口不重复字母个数 formed = 0。
每次 right 左移时，把当前字母 character 放在 windows_counts 中：window_counts[character] = window_counts.get(character, 0) + 1，如果 character 在 dict_t 中，且加入 windows_counts 后 window_counts[character] == dict_t[character]，则 formed += 1。当 formed == required 时，是一个可行窗口。
left右移时，window_counts[character] -= 1，如果 character in dict_t 且 window_counts[character] < dict_t[character]，说明匹配的字母少了，formed -= 1。之后 left += 1，窗口移出这个字母。
优化：
建立一个 s_t 列表，一边遍历，保存 t 中字母在 s 中的字符及下标。例 s_t = [(0, 'A'), (1, 'B'), (14, 'B')]，然后在 s_t 中使用滑动窗口，减少遍历的字符数。
77. 组合
回溯。backtrack(curr, start)，传递当前组合以及起点数字，如果 len(curr) == k 则 ans.append(cur) 然后return，否则 for i in range(start, n+1): com(curr+[i], i+1)。最初 com([], 1)。start 的用处是防止重复。
78. 子集
① 回溯。相当于没设置组合长度 k 的第 77 题。backtrack(curr, start)，传递当前组合以及下标起点数字，每次先 ans.append(curr)，然后如果 len(curr) == k 就 return。否则 for i in range(start, len(nums))：com(path+[nums[i]], i+1)。最初 com([], 0)。
② 递归。初始化 output = [[]]。遍历 for num in nums，把前面得到的 output 中的已有结果加上当前的 num 然后放入output中：output += [curr + [num] for curr in output]。
79. 单词搜索
回溯。dfs。定义二维数组 mark 保存是否使用过，每次四个方向使用调用函数。
directs = [(0, 1), (0, -1), (1, 0), (-1, 0)] 定义四个行走方向，每个点 for direct in self.directs 检查四个方向，cur_i = i + direct[0]，cur_j = j + direct[1]。
80. 删除排序数组中的重复项 II
① 直接删除。使用 pop 之类的方法删除，这个操作时间复杂度 O(N)。最后总复杂度 O(N2)。
② 覆盖，使用快慢指针，快指针 right 遍历整个数组，如果元素出现次数大于 2 就 nums[left] = nums[right]，left += 1。时间复杂度 O(N) 比直接删除优秀。
81. 搜索旋转排序数组 II
二分思路和第 33 题一样，然后就是关于重复数字的影响。比如 10111，不能通过对比 left 和 right 判断旋转点在哪半边。 此时 left += 1 去掉干扰即可。
82. 删除排序链表中的重复元素 II
比较容易写乱。循环 while cur.next and cur.next.next。
如果遇到重复数字即 cur.next.val == cur.next.next.val，使 temp = cur.next，然后一直到这个数字没有重复。 while (temp and temp.next and temp.val == temp.next.val ) : temp = temp.next。出了循环 cur.next = temp.next。
如果没有重复，就当前元素就 cur = cur.next。
83. 删除排序链表中的重复元素
呃。。。
84. 柱状图中最大的矩形 *
① 暴力。外层遍历 left 表示左边柱子，内层遍历 right 表示右边柱子，保存当前 left 开始的柱子最小值，对每个 right 计算面积。时间复杂度 O(n2)。
② 分治。令当前区域的最小值点为 min_loc，总的最大面积等于 min(包含 min_loc 的最大面积，min_loc 左区域的最大面积、min_loc 右区的域最大面积)。而当前区域 [i, j] 的最大面积等于 min_loc * [i-j+1]。同理，左右区域里所求面积也等于区域内最小值×区域长度。递归求解。平均时间复杂度 O(nlogn)，最坏 O(n2)。
③ 中心扩散。第一遍从左到右，记录每个元素左边区域的最小值；第二遍从右往左，记录每个元素的右最小值。第三遍，对每个元素 i 计算 heights[i] * (r_low[i] - l_low[i] - 1) 即对 i 来说的最大面积。
因为如果两边出现比 i 小的值，总的面积一定会减少，所以每次以左边第一个高度小于 i 的位置和右边第一个高度小于 i 的位置为边界。时间复杂度 O(n)。
④ 栈。注意到问题的核心是求左边第一个比 i 小的和右边第一个比 i 小的位置，适合用单调栈处理，维护一个单调增栈。在 heights 左右添加哨兵 0，这样遍历结束栈会清空。
遍历数组，如果每次比栈顶大就下标入栈。如果比栈顶小，则出栈直到当前高度大于栈顶 while stack and heights[st[-1]] > heights[i]，每次出栈计算面积 heights[stack.pop()] * (i - stack[-1] - 1)，这个面积是 i 与 stack[-1] 之间的柱子的最大面积（不包括i 和 stack[-1]），因为这些柱子中的最小值是刚刚出栈的那个数。
85. 最大矩形 *
① 柱状图。记录每一行中每一个方块连续的“1”的数量 row[i] = row[i-1] + 1 if row[i] == '1'，对于每一列，可以看做一组方向向左、高度为 row[i] 的柱状图，问题变成求这些柱状图的最大矩形，也就是第 84 题的问题。
② 动态规划。定义三个长度为 n 的数组：left，right，height。遍历每行，每行内层有四次遍历，分别用来更新 left、更新 right、更新 height、计算面积。left[j] 表示该矩形的左边界下标，right[j] 表示该矩形的右边界下标，height[j] 表示高度，根据这三个值可以计算矩形面积。
对于 left[j]，由于前几行的 0 已经考虑到了数组中，唯一的影响就是当前行的0，所以 left[j] 为前一行 left[j] 与当前行的左边界 cur_left 中的的最右值。如果当前点是 1 则 left[j] = max(left[j], cur_left)，如果是 0 则 left[j] = 0 并更新 cur_left = j + 1。right[j] 同理，从右往左遍历。对于height[j]，如果该点是 1 则 height[j] += 1，如果是 0 则 height[j] = 0。
86. 分隔链表
如果遍历时元素小于 x，p = p.next；如果大于等于 x，把它放到 large 开头的链表中（large 用另外一个指针标记当前末尾，每次添加到末尾）。最后把两个相连 p.next = large.next。注意初始化在开头添加 dummy，减少条件判断。
87. 扰乱字符串 *
① 递归。如果一段区域发生扰乱，一定有交换点 i，使得 i 的左边与右边发生扰乱。遍历每个点逐个检查 i 两边交换或不交换是否相同。每个点 i 有两种情况：(1) s1 在点 i 分成两部分，每部分内部经过若干分割交换；(2) s1 在点 i 分成两部分并两部分交换，每部分内部经过若干分割交换。
每次递归先判断两个字符串是否相同，相同返回 True。两串出现的字母和对应数量是否一致，不一致返回 False。然后是遍历所有字符 i 并递归。
(1) 对应情况 1： if (isScramble(s1.substring[ : i+1], s2.substring[ : i+1]) && isScramble(s1.substring[i: ], s2.substring[i: ])): return true
(2) 对应情况 2，两个子树进行了交换：if (isScramble(s1[i: ], s2.substring[ : n-i+1]) and isScramble(s1[i: ], s2.substring[ :n-i+1]): return true
有大量重复计算，可以用记忆优化。
② 动态规划。dp[i][j][len] 表示 s1 从 i 开始的 len 个字符是否能转换为 S2 从 j 开始的 len 个字符。初始化 dp[i][j][1]。
循环四层。 for len in range(1, n) 检查不同长度。for i in range(n-len+1) 和内层 for j in range(n-len+1) 分别遍历两个字符串。for q in range(1, len+1) 遍历切割点。
假设左半部分长度是 q，第一种情况可以写做 dp[i][j][len] = dp[i][j][q] and dp[i+q][j+q][len-q]，则 dp[i][j][len] = True，break。也就是 S1 的左半部分和 S2 的左半部分 and S1 的右半部分和 S2 的右半部分。
第二种情况，dp[i][j+len-q][q] and dp[i+q][j][len-q]，则 dp[i][j][len] = True，break。
最后返回 dp[0][0][len]，即两个字符串从 0 开始的 len 个字符能否转换。
88. 合并两个有序数组
双指针从后往前。loc=m+n-1 指向 nums1 存储 m+n个 数后的末尾 ，l1=m-1 和 l2=n-1 分别指向 nums1 元素末尾和 nums2 元素末尾。从后往前，把 num1[l1] 和 nums2[l2] 中较大的值赋给 nums1[loc]，然后 loc 和较大的那个数组下标左移。当 l1 小于 0，nums1[: l2+1] = nums2[: l2+1] 并 break；当 l2 小于 0，break。
89. 格雷编码
假设已知 n 阶格雷码 则 n+1 阶可以这样得到：将 n 阶二进制格雷码每个元素前添加 0，再将 n 阶格雷码序列倒序并且每个元素前添加 1，合并以上两个集合就得到了 n+1 阶格雷码。因为添加 1 的那些元素顺序是原来的倒序，所以添加 0 的最后一个元素和添加 1 的第一个元素是一样的，唯一不同就是开头添加的一位，符合格雷码性质。
代码实现时，外层循环 0 到 n 阶，内层倒序遍历之前保存的结果 res：res.append(head + res[j])，因为最高位默认为 0，所以添加 0 的操作可以省去。
90. 子集 II
回溯。还是同样的去重方法。
对于每个元素只能用一次，这里使用设置元素起点的方法解决，backtrack(start, path) 函数中传递当前组合以及下标起点数字，每轮选取数字的范围为 nums[start: ]。
对于子集不重复的问题，这里使用当前层元素不重复的方法，if i > start and nums[i] == nums[i-1]: continue，这样避免在同一层递归出现重复的数字。