LeetCode - 2021-08 - 《算法》

36. 有效的数独

请你判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。

遍历这个数独，对每一个数据判断它所在的行、列、3 * 3 范围内维护一个 Set，当数据出现在这个 Set 里面的时候，就可以认为不是一个数独了

37. 解数独
编写一个程序，通过填充空格来解决数独问题。数独的解法需遵循如下规则：
1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
使用回溯+状态压缩方法：
1. 使用已经填充数据的信息，构造行、列、3 * 3 范围内的 Set（可以节省内存使用 BitSet）
2. 对于每一个需要填充数据的空格，从已经填充的数据里面得到满足条件的数据（其实就是 1-9 先过滤一次），依次填入这个值
3. 每次填入这个值的时候，更新 Set 信息，开始回溯，如果回溯成功，返回，否则清理 Set 信息，重新填入下一个值
  38. 外观数列
  给定一个正整数 n ，输出外观数列的第 n 项。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列：
  - countAndSay(1) = "1"
  - countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
  前五项如下：
  1. 1
  2. 11 （一个一）
  3. 21 （二个一）
  4. 1211 （一个二、一个一）
  5. 111221 （一个一、一个二、二个一）
遍历这个字符串整数，收集每一个字符，如果该字符是第一个或等于上一个，那么更新计数，否则输出计数+字符并且重置计数

39. 组合总和

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。 candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是唯一的。对于给定的输入，保证和为 target 的唯一组合数少于 150 个。
使用排序+回溯+状态压缩
1. 先将整数数组 candidates 从小到达排序，这样回溯的时候找到一个大于目标值的整数的时候就可以认为后续都会大于目标值了，进行状态压缩
2. 回溯每一个整数，判断其存在或不存在的进行递归下去，直到 target 为 0（每次回溯存在的时候，将 target - 目标值）
  40. 组合总和 II
  
  给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。
和 39 解法一样，只是回溯整数的时候，如果一个整数被遍历到的时候，跳过后续所有重复的整数

41. 缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
哈希表：对于数组 nums 来说，它的最小的正整数只可能是（因为最坏情况下，nums 里面都是不重复的且小于 n 的整数，此时最小的正整数为 n + 1
1. 因此对于长度为 N 的数组里面，所有不属于 1...n 的整数都属于无效整数，此时可以直接将其标记为无效数字，例如 n + 1
2. 对于有效的整数，x = nums[i]，此时可以将 x 作为数组的位置，将具体位置标记为负值
  1. nums[num[i] - 1] = -abs(nums[num - 1])，此时 num = abs(nums[i])
  2. 设置为负数的好处就是，未遍历的整数也能通过 abs(nums[i]) 的原始的数据
3. 这样遍历一圈之后，所有有效的数字都会将其数字所在的位置变成负数，此时重新遍历第一个不为负数的位置就是缺失的第一个正数
置换：直接遍历数组，对所有有效的数字 x = nums[i] 和 nums[x - 1] 交换位置，这样重新判断，遍历完成之后，每一个位置上面的值都会等于自己的位置 nums[i] = i + 1
1. 存在 nums[x - 1] == nums[i] 的情况，此时交换位置的时候将会无限循环，因此需要额外剔除这种情况，此时不做处理即可
  42. 接雨水
  
  给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
  
  示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
递归：对每一个左边框找到第一个大于等于它的有边框作为一个处理单元，对其中的每一个元素进行计算 min(left, right) - height[i]，此时递归处理下一个处理单元
1. ans = current[i] + recursive(i + 1)
2. 此时需要考虑一种情况，左边框不存在大于它的有边框的情况，此时需要从右向左处理，因此
3. ans = current[i] + max(recursive(i + 1), recursiveReversed(i, length - 1)
动态规划：对于每一个下标 i，它的节水量等于 min(最大左边框，最大有边框) - height[i]，因此只要通过动态规划计算得到每个下标的左右最大边框即可
1. 计算最大边框的时候可以包含下标所在的边框值（因为两边边框小于自己的话，最终结果其实为 0）
4. 通过两次遍历得到 leftMax、rightMax 数组后，再次遍历即可得到最终结果值
双指针：动态规划里面计算了每一个下标的左右最大值，空间复杂度是 O(n)，其实可以使用双指针的方式来动态的更新 leftMax、rightMax 值
1. 维护两个指针 left 和 right，以及两个变量 leftMax 和 rightMax，初始时默认 left=0，right=n - 1，leftMax = 0, rightMax = 0，指针 left 只会向右移动，指针 right 只会向左移动，在移动过程中动态的维护 leftMax、rightMax 这两个变量的值
2. 当两个指针没有相遇时，进行如下操作
  1. 使用 height[left]、height[right] 的值动态更新 leftMax、rightMax 的值
  2. 如果 height[left] < height[right]，则必有 leftMax < rightMax，下标 left 处能接的雨水量等于 leftMax - height[left]，将下标 left 处能接的雨水量加到能接的雨水总量，然后将 left 加 1（即向右移动一位）
  3. 如果 height[left] >= height[right]，则必有 leftMax >= rightMax，下标 left 处能接的雨水量等于 rightMax - height[right]，将下标 right处能接的雨水量加到能接的雨水总量，然后将 right减 1（即向左移动一位）
```
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
   leftMax = Math.max(leftMax, height[left]);
   rightMax = Math.max(rightMax, height[right]);
   if (height[left] < height[right]) {
       ans += leftMax - height[left];
       ++left;
   } else {
       ans += rightMax - height[right];
       --right;
   }
}
return ans;
}
}
```
单调栈：维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减
1. 从左到右遍历数组，遍历到下标 i 时，如果栈内至少有两个元素，记栈顶元素为 top，top 的下面一个元素是 left，则一定有 height[left] >= height[top]。如果 height[i] > height[top]，则得到一个可以接雨水的区域，该区域的宽度是 i - left - 1，高度是 min(height[left], height[i]) - height[top]，根据宽度和高度即可计算得到该区域能接的雨水量。
2. 为了得到 top，需要将 top 出栈。在对 top 计算能接的雨水量之后，left 变成新的top，重复上述操作，直到栈变为空，或者栈顶下标对应的 height 中的元素大于或等于 height[i]。12q
3. 在对下标 i 处计算能接的雨水量之后，将 i 入栈，继续遍历后面的下标，计算能接的雨水量。遍历结束之后即可得到能接的雨水总量。
```
class Solution {
public int trap(int[] height) {
  int ans = 0;
  Deque<Integer> stack = new LinkedList<Integer>();
  int n = height.length;
  for (int i = 0; i < n; ++i) {
      while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
          int top = stack.pop();
          if (stack.isEmpty()) {
              break;
          }
          int left = stack.peek();
          int currWidth = i - left - 1;
          int currHeight = Math.min(height[left], height[i]) - height[top];
          ans += currWidth * currHeight;
      }
      stack.push(i);
  }
  return ans;
}
}
```
  43. 字符串相乘
  
  给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
直接模拟竖式乘法的方法来计算成绩，从右往左遍历乘数，将乘数的每一位与被乘数相乘得到对应的结果，再将每次结果累加（每一个相乘的结果需要注意累加补 0）
直接使用一个最终的结果数组（可以证明这个长度为 m + n 或 m + n - 1），根据乘数和被乘数的每一位计算得到的值直接累加到这个数组的每一位上去（注意进位，默认值为 0）

44. 通配符匹配
给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘‘ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。 ‘‘ 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。说明:
- s 可能为空，且只包含从 a-z 的小写字母。
- p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
回溯算法：对于模式串匹配的时候，除了 * 需要特殊处理，会产生回溯分支之外，其余字符匹配的时候正常处理即可（可以添加备份机制来节省时间）
动态规划：转移方程如下：
2. 需要处理一种特殊的边界情况，如果模式串 p[0...j] == '*...***' 那么 dp[0][j] = *
  45. 跳跃游戏 II
  
  给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。
贪心算法：每次找到当前位置和最大长度位置里面可以使得跳跃最长的一个位置，跳到该位置上去（该位置上的所有选择覆盖其他位置的选择）

46. 全排列

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。
直接回溯每个位置，判断每个位子上能够使用的所有数字（需要一个判重的操作）

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。
和 46 解法一样，但是提前排好序，只要保证每个位置选数字的时候不要选重复的数字即可，因此排序只会选择重复数字的第一个，下次选择的时候跳过这个重复数字

48. 旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
循环遍历每一层，通过算法计算出每一个数字应该出现在上面位置上面，直接覆盖这个值（需要一个临时值来存储第一个数字）

49. 字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词指字母相同，但排列不同的字符串。
示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
排序：对每一个字符串进行排序，这样排序之后的字符串就可以作为哈希表的键
计数：由于字符串只包含小写字母，因此每个字符串都可以使用一个 new int[26] 的数组记录每个字母出现的次数，此时可以使用哈希表来记录所有相同的键

50. Pow(x, n)

实现 pow(x,n) ，即计算 x 的 n 次幂函数（即，xn）。

直接使用递归方法即可

class Solution {
public:
 double quickMul(double x, long long N) {
     if (N == 0) {
         return 1.0;
     }
     double y = quickMul(x, N / 2);
     return N % 2 == 0 ? y * y : y * y * x;
 }
 double myPow(double x, int n) {
     long long N = n;
     return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
 }
}

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数n，返回所有不同的 n皇后问题的解决方案。每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

直接回溯即可，判断每个位置上存放一个皇后得到的结果就可以了
1. 需要使用一些集合来判断是否相互攻击（也可以直接使用 bitmap 来节省一点点内存）
  52. N皇后 II
  
  n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题不同的解决方案的数量。

和 51 解法一样，直接回溯即可，递归方法的返回值可以设置为解决方案的数量

private int totalNQueensRecursive(int row) {
 if (row >= this.count) {
     return 1;
 }
 int res = 0;
 for (int col = 0; col < this.count; col++) {
     if (testCell(row, col)) {
         addCell(row, col);
         res += totalNQueensRecursive(row + 1);
         removeCell(row, col);
     }
 }
 return res;
}

53. 最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

初始化 maxVals 和 leftVal 为 nums[0]，从下标 1 开始，依次遍历数组，对每一个下标判断当前数字 nums[i] 和 nums[i] + leftVal 的大小，将大值赋值给 leftVal，最后最大的 leftVal 即为最大和

54. 螺旋矩阵

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]

维护一个需要填充的元素数量 nums，在维护一个 step，默认为 0，每经过一次循环 +1，用来作为每次循环的开始和终止条件

维护四个方向，将 row=0，column=0 开始，先保持 row 不变，column增长，再column不变，row增长，这样四个方向之后，再重新循环这个逻辑，直到 nums 等于 0 为止（每填充一个元素，就减一）

int step = 0, row = 0, col = 0;
while (numSize >= 1) {
for (row=step; col < matrix[0].length - step && numSize >= 1; col++) {
  res.add(matrix[row][col]);
  numSize--;
}

row++;

for (col=matrix[0].length - step - 1; row < matrix.length - step && numSize >= 1 ; row++) {
  res.add(matrix[row][col]);
  numSize--;
}

col--;

for (row=matrix.length - step - 1; col >= step && numSize >= 1; col--) {
  res.add(matrix[row][col]);
  numSize--;
}

row--;

step += 1;
for (col=step - 1; row >= step && numSize >= 1; row--) {
  res.add(matrix[row][col]);
  numSize--;
}

col++;
}

也可以额外维护一个 visists 的二维数组，维护每个元素是否被访问到，在维护一个[[0, 1], [1, 0], [0, -1], [-1, 0]]的 row、column 的方向，再每个方向中，不断地变化 row、column 值，直到超出边界，或者到达一个已经访问的节点，那么认为达到边界了，更换一个方向（第四个方向之后是第一个方向）
```
for i in range(total):
 order[i] = matrix[row][column]
 visited[row][column] = True
 nextRow, nextColumn = row + directions[directionIndex][0], column + directions[directionIndex][1]
 if not (0 <= nextRow < rows and 0 <= nextColumn < columns and not visited[nextRow][nextColumn]):
     directionIndex = (directionIndex + 1) % 4
 row += directions[directionIndex][0]
 column += directions[directionIndex][1]
```
55. 跳跃游戏

给定一个非负整数数组 nums ，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
从第一个下标开始，找到他能跳跃到的最大位置和最小位置之间所有能够跳跃最远的哪个下标，即使跳跃的目标，依次类推，直到找到最后一个下标
1. 每次都选能够跳跃最远的是因为它包含了其他能够跳跃的下标的可能，如果其他下标能够达到最后一个下标，那么最大的一定也可以
所谓的可达，也就是值存在一个可达的下标 i + nums[i] >= n，因此遍历这个数组 nums，维护一个最大位置 x + nums[x]，只要这个最大位置大于最后一个下标，即认为可达
1. 遍历的时候，需要判断当前下标值是不是小于这个最大位置，如果大于的话，说明这个下标是不可达的，那么就认为最后一个下标也是不可达的
  56. 合并区间
  
  以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
将区间按照区间开始值进行排序，然后顺序遍历这个区间，维护一个 leftInterval 如果当前区间和上个区间重合，那么合并区间，如果不重合，那么将上一个合并后的区间假如结果值，遍历完成后，如果 leftInterval 存在，将其放入结果值

57. 插入区间

给你一个无重叠的，按照区间起始端点排序的区间列表。在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）
应为原先的区间列表是无重叠的，因此只要找到所有与新的区间重叠的部分即可，其他部分的区间值直接添加到结果值里面就行（区间重叠的一定是连续的区间）
1. 遍历区间，如果非重叠的直接加入到结果值中，重叠的部分，维护最小和最大的值，直到下一个非重叠的区间存在，加入进去这个合并区间
  58. 最后一个单词的长度
  
  给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。
从右向左遍历，找到第一个字符开始计数，直到第一个非字符的结束，返回这个计数

59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
和 54 解题方法一致，只是改成给指定位置赋值元素

60. 排列序列
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
1. “123”
2. “132”
3. “213”
4. “231”
5. “312”
6. “321”
给定 n 和 k，返回第 k 个排列。
维护一个初始数组 [1...n]，因为前 x 个数字能够生成的最大排列数为 2^x，因此找到最大的一个 x，使得 2^x 小于等于 k
1. 此时数组变为 [1...y, n, n-1, ..., n - x]，这个时候如果 2^x 等于 k 的话就直接返回这个数组
2. 否则，将数组右边的第一个大于 y 的数字和 y，进行交换，然后将最右边的 x 个数组逆序
3. 之后对数组 [1...n - x(y), n - x + 1, ..., n] 计算第 k - 2^x - 1 的排列
康托展开

捕获.PNG

61. 旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

先使用一个链表节点，开始遍历链表，遍历 k 次，如果遍历到链表结尾，可以从头开始（可以优化一下，如果遍历到链表节点，此时可以得到链表的长度，将 k = k % length，之后从头开始遍历
1. 找到一个第 k 个位置的链表后，在初始化一个新的节点遍历重头开始遍历，每次遍历的时候将新旧两个节点依次向右遍历，直到第一个节点直到链表结尾，此时新的节点就是结果值的开头，此时将尾节点执行 head 节点，新的遍历节点的上一个节点指向 null（遍历指针找到开始节点的上一个节点即可）
  62. 不同路径
  
  一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
动态规划，维护一个二维矩阵，表示到达 <m, n> 位置的最大路径数位 res[m][n]，此时
1. res[m][n] = 0 如果 m = 0, n = 0
2. res[m][n] = res[m - 1][n] + res[m][n - 1];
  63. 不同路径 II
  
  一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
和 62 一样，动态规划即可，多了一个位置上有障碍物的时候直接置为 0

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
和 62 类似，动态规划即可，但是 res[i][j] = grid[i][j] + Math.min(res[i - 1][j], res[i][j - 1]);

65. 有效数字
有效数字（按顺序）可以分成以下几个部分：
1. 一个小数或者整数
2. （可选）一个 ‘e’ 或 ‘E’ ，后面跟着一个整数
小数（按顺序）可以分成以下几个部分：
1. （可选）一个符号字符（’+’ 或 ‘-‘）
2. 下述格式之一：
  1. 至少一位数字，后面跟着一个点 ‘.’
  2. 至少一位数字，后面跟着一个点 ‘.’ ，后面再跟着至少一位数字
  3. 一个点 ‘.’ ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
1. （可选）一个符号字符（’+’ 或 ‘-‘）
2. 至少一位数字
部分有效数字列举如下：
- [“2”, “0089”, “-0.1”, “+3.14”, “4.”, “-.9”, “2e10”, “-90E3”, “3e+7”, “+6e-1”, “53.5e93”, “-123.456e789”]
部分无效数字列举如下：
- [“abc”, “1a”, “1e”, “e3”, “99e2.5”, “—6”, “-+3”, “95a54e53”]
给你一个字符串 s ，如果 s 是一个有效数字，请返回 true 。
确定有限状态自动机:

确定有限状态自动机（以下简称「自动机」）是一类计算模型。它包含一系列状态，这些状态中：有一个特殊的状态，被称作「初始状态」。还有一系列状态被称为「接受状态」，它们组成了一个特殊的集合。其中，一个状态可能既是「初始状态」，也是「接受状态」。起初，这个自动机处于「初始状态」。随后，它顺序地读取字符串中的每一个字符，并根据当前状态和读入的字符，按照某个事先约定好的「转移规则」，从当前状态转移到下一个状态；当状态转移完成后，它就读取下一个字符。当字符串全部读取完毕后，如果自动机处于某个「接受状态」，则判定该字符串「被接受」；否则，判定该字符串「被拒绝」。

注意：如果输入的过程中某一步转移失败了，即不存在对应的「转移规则」，此时计算将提前中止。在这种情况下我们也判定该字符串「被拒绝」。一个自动机，总能够回答某种形式的「对于给定的输入字符串 S，判断其是否满足条件 P」的问题。在本题中，条件 P 即为「构成合法的表示数值的字符串」。自动机驱动的编程，可以被看做一种暴力枚举方法的延伸：它穷尽了在任何一种情况下，对应任何的输入，需要做的事情。
1. 此时可以定义所有的状态：
  1. 初始状态
  2. 符号位
  3. 整数部分
  4. 左侧有整数的小数点
  5. 左侧无整数的小数点（根据前面的第二条额外规则，需要对左侧有无整数的两种小数点做区分）
  6. 小数部分
  7. 字符 e
  8. 指数部分的符号位
  9. 指数部分的整数部分
2. 根据题意，「初始状态」应当为状态 1，而「接受状态」的集合则为状态 3、状态 4、状态 6 以及状态 9。换言之，字符串的末尾要么是空格，要么是数字，要么是小数点，但前提是小数点的前面有数字。
3. ```python from enum import Enum

class Solution: def isNumber(self, s: str) -> bool: State = Enum(“State”, [ “STATE_INITIAL”, “STATE_INT_SIGN”, “STATE_INTEGER”, “STATE_POINT”, “STATE_POINT_WITHOUT_INT”, “STATE_FRACTION”, “STATE_EXP”, “STATE_EXP_SIGN”, “STATE_EXP_NUMBER”, “STATE_END” ]) Chartype = Enum(“Chartype”, [ “CHAR_NUMBER”, “CHAR_EXP”, “CHAR_POINT”, “CHAR_SIGN”, “CHAR_ILLEGAL” ])

    def toChartype(ch: str) -> Chartype:
        if ch.isdigit():
            return Chartype.CHAR_NUMBER
        elif ch.lower() == "e":
            return Chartype.CHAR_EXP
        elif ch == ".":
            return Chartype.CHAR_POINT
        elif ch == "+" or ch == "-":
            return Chartype.CHAR_SIGN
        else:
            return Chartype.CHAR_ILLEGAL

    transfer = {
        State.STATE_INITIAL: {
            Chartype.CHAR_NUMBER: State.STATE_INTEGER,
            Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT,
            Chartype.CHAR_SIGN: State.STATE_INT_SIGN
        },
        State.STATE_INT_SIGN: {
            Chartype.CHAR_NUMBER: State.STATE_INTEGER,
            Chartype.CHAR_POINT: State.STATE_POINT_WITHOUT_INT
        },
        State.STATE_INTEGER: {
            Chartype.CHAR_NUMBER: State.STATE_INTEGER,
            Chartype.CHAR_EXP: State.STATE_EXP,
            Chartype.CHAR_POINT: State.STATE_POINT
        },
        State.STATE_POINT: {
            Chartype.CHAR_NUMBER: State.STATE_FRACTION,
            Chartype.CHAR_EXP: State.STATE_EXP
        },
        State.STATE_POINT_WITHOUT_INT: {
            Chartype.CHAR_NUMBER: State.STATE_FRACTION
        },
        State.STATE_FRACTION: {
            Chartype.CHAR_NUMBER: State.STATE_FRACTION,
            Chartype.CHAR_EXP: State.STATE_EXP
        },
        State.STATE_EXP: {
            Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER,
            Chartype.CHAR_SIGN: State.STATE_EXP_SIGN
        },
        State.STATE_EXP_SIGN: {
            Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
        },
        State.STATE_EXP_NUMBER: {
            Chartype.CHAR_NUMBER: State.STATE_EXP_NUMBER
       你 },
    }

    st = State.STATE_INITIAL
    for ch in s:
        typ = toChartype(ch)
        if typ not in transfer[st]:
            return False
        st = transfer[st][typ]

    return st in [State.STATE_INTEGER, State.STATE_POINT, State.STATE_FRACTION, State.STATE_EXP_NUMBER, State.STATE_END]

<a name="LbXJ8"></a>
#### 66. [加一](https://leetcode-cn.com/problems/plus-one/description/)
> 给定一个由 **整数 **组成的** 非空** 数组所表示的非负整数，在该数的基础上加一。
> 最高位数字存放在数组的首位， 数组中每个元素只存储**单个**数字。
> 你可以假设除了整数 0 之外，这个整数不会以零开头。

1. 从右向左遍历，维护一个进位值（默认为1），当遍历的数字为 9 的时候，变成0，将进位值变成 1，否则数字加一，进位值变成0，然后直接结束这个遍历
   1. 当遍历完成之后，进位值依然为 1 的时候，此时新建一个长度为原数组长度 + 1的数组，最高位为 1，其余位为 0 即可
<a name="l04y3"></a>
#### 67. [二进制求和](https://leetcode-cn.com/problems/add-binary/description/)
> 给你两个二进制字符串，返回它们的和（用二进制表示）。
> 输入为 **非空 **字符串且只包含数字 1 和 0。

1. 找到两个字符串的最大长度，开始遍历，从右向左获取两个字符串所在位置的字符值，超过长度的时候默认取 0，将加起来的值对 2 取模，余数为下一次相加的进位值。
1. 位运算：我们可以设计这样的算法来计算：
   1. 把 a 和 b 转换成整型数字 x 和 y，在接下来的过程中，x 保存结果，y 保存进位。
   1. 当进位不为 0 时
      1. 计算当前 x 和 y 的无进位相加结果：answer = x ^ y
      1. 计算当前 x 和 y 的进位：carry = (x & y) << 1
      1. 完成本次循环，更新 x = answer，y = carry
   3. 返回 x 的二进制形式
```python
def addBinary(a, b) -> str:
    x, y = int(a, 2), int(b, 2)
    while y:
        answer = x ^ y
        carry = (x & y) << 1
        x, y = answer, carry
    return bin(x)[2:]

68. 文本左右对齐
给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ‘ ‘ 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。 说明:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

维护一个当前长度，遍历每个单词，判断当前长度 + 遍历单词的长度大于宽度的时候，就认为找到一行字符了，单独处理这行字符的宽度，将当前长度变为 0，继续遍历这个单词
1. 计算单行字符的时候，先判断里面的单词数目，如果只存在一个的话，直接填充在开始，用空格覆盖后续位置
2. 如果多个单词的数目的话，先去掉首尾的单词，然后判断接下来的单词数目，并计算之间的间隔空格数
  1. 去除首尾单词的宽度再减去所有单词的长度余下的宽度除去（单词数目 + 1）就得到间隔空格数，余数就是前几个空格应该加一的数目
3. 根据空格数目，依次填充单词就行
4. 对于最后一行的文本，只要按照顺序填充一个单词，加一个空格，最后使用空格填充余下的位置
  69. x 的平方根
  
  实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
二分查找：先设定 left = 0, right = x，取 mid = ((right - left) >> 1) 判断 mid * mid 与 x 的比较，来设定 left、right 的值
1. 当 mid > sqrt(Integer.MAX_VALUE) 的时候，将 right = mid - 1
  70. 爬楼梯
  
  假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
动态规划：f(x) = f(x - 1) + f(x - 2)，默认 f(0) = 1, f(1) = 1

71. 简化路径
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点（..）表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠 ‘/‘ 开头。
- 两个目录名之间必须只有一个斜杠 ‘/‘ 。
- 最后一个目录名（如果存在）不能以 ‘/‘ 结尾。
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。
直接将字符串使用 ‘/‘ 分割，在维护一个堆栈，遇到一个字符就放入堆栈里面，遇到 .. 就移除一个字符，遇到 . 或者空白的时候就跳过这个字符，最后将这个堆栈拼接成一个字符串

72. 编辑距离
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
动态规划：维护一个二维数组 distances，假定 distances[i][j] 的值就是单词 word1 的前 i 个字符和单词 word2 的前 j 个字符相互转换所用的最少操作数，因此，只要求得 distances[word1.length() - 1][word2.length() - 2] 即可
1. distances[i][j] = min(distances[i - 1][j] + 1, distances[i][j - 1] + 1, last)
  1. 其中 last = distances[i - 1][j - 1] if word1[i] == word2[j]，否则 last = distance[i - 1][j - 1] + 1
```
for (int i = 0; i < word1.length(); i++) {
for (int j = 0; j < word2.length(); j++) {
top = i > 0? distances[i - 1][j] + 1 : Integer.MAX_VALUE;
bottom = j > 0? distances[i][j - 1] + 1 : Integer.MAX_VALUE;

if (i > 0 && j > 0) {
   last = distances[i - 1][j - 1];
} else {
   // 假如 word1 的前 i 个字符和 空字符进行转换，那么最少需要 i 次转换才行（删除或新增）
   last = Math.max(i, j);
}
if (word1.charAt(i) != word2.charAt(j)) {
   last++;
}

distances[i][j] = Math.min(Math.min(top, bottom), last);
}
}
```
    73. 矩阵置零
    给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。 进阶：
    - 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
    - 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
    - 你能想出一个仅使用常量空间的解决方案吗？
可以使用两个数组存储每列和每行出现 0 的位置，这样再用这两个数组来反向更新矩阵
可以使用矩阵的第一行和第一列来作为这两个数组，此时就需要提前存储好第一列和第一行是否出现 0 了，此时用两个变量存储就行
可以再次优化这个算法，使用一个变量来表示第一列出现了 0，再用 matrix[0][0] 位置来存储第一行是否出现了 0，这样的话就需要从上到下来更新这个矩阵了，防止第一行直接被全部变为 0 的时候，第一行的记录失效了

74. 搜索二维矩阵
编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。
两次二分查找：在第一列上找到第一个大于给定元素的值，在这列的上一行中再用二分查找找到具体的位置
一次二分查找：直接使用二维数组的二分查找，每次找到左右两个节点的中间节点，根据与给定元素的值进行判断重新定位左右两个值
1. 定位 right 和 left 的时候，直接将 mid 节点加一或减一，此时存在超过列数的问题，如果超过列数，将列变为0，行加一
  75. 颜色分类
  
  给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
单指针：进行两次遍历，第一次遍历，将数组中所有 0 交换到数组的头部，第二次遍历，将所有 1 交换到头部的 0 之后
双指针：使用一次遍历来完成整个交换，使用两个指针 p0 来交换 0，p1 来交换 1，初始值都为 0，开始从做向右遍历整个数组
1. 如果找到了1，将其与 nums[p1++] 进行交换
2. 如果找到了0，将其与 nums[p0++] 进行交换，此时交换出去的很大可能一个 1，因此如果 p0 < p1，那么将交换后的值与 p1 交换
  1. 每次找到了 0，都会给 p1 也右移一位
双指针：使用两个指针 p0 来交换0，初始值为 0，p2 来交换 2，初始值为 n - 1，此时从左向右遍历整个数组，直到遍历位置 i 超过了 p2
1. 如果找到了 0，将其与 nums[p0++] 交换
2. 如果找到了 2，将其与 nums[p2--] 交换，和 0 不一样，由于 i >= p0，因此可以保证 p0 位置上的数值一定不是 0，但是相比于 nums[p2]，这个值可能为0，也可能为 2，这是没法保证的，因此还需要对交换后的 i 进行重新比较才向
先遍历一次，统计 0、1、2 各自的数量，并且计算出每个 0、1、2各自的上下边界，遍历这个数组，如果为 0，将其和 0 所在的指针交换（如果这个值已经处理过了，就不再处理） ```java int zeroStart = 0, oneStart = zeroNums, twoStart = zeroNums + oneNums; int zeroEnd = 0, oneEnd = oneStart, twoEnd = twoStart;

int index = 0; while (index < nums.length) { if (nums[index] == 0) { if (index >= zeroStart && index < zeroEnd) { index++; } else { swap(nums, index, zeroEnd++); } } else if (nums[index] == 1) { if (index >= oneStart && index < oneEnd) { index++; } else { swap(nums, index, oneEnd++); } } else { if (index >= twoStart && index < twoEnd) { index++; } else { swap(nums, index, twoEnd++); } } } ```

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

滑动窗口：先维护一个字符串 t 的每个字符对应的个数的 map，再维护一个滑动窗口的当前 map
1. 再维护两个指针，l、r，首先开始增长 r，每次增长的时候判断字符是否在 t 的 map里面，如果在更新滑动窗口的 map
2. 每增长一次就就检查一次两个 map 是否一致，如果一致的话，就开始增加 l，直到两个 map 不一致的时候，跳出循环，再次增长 r，直到字符串 s 遍历结束
  77. 组合
  
  给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。你可以按 任何顺序 返回答案。
回溯：新建一个新的 k 长度的数组，回溯遍历整数列表[1...n]，每次挑选一个数字或者不挑选这个数字，直到数组长度到达指定位数的时候假如结果集中
非递归组合型枚举：使用一个n 位的二进制，其中存在 k个1 和 n - k 个0，只要遍历出所有满足的二进制即可

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按 任意顺序 返回解集。
简单回溯 + 哈希集合

79. 单词搜索

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
回溯：遍历这个二维字符网格，从每一个节点开始回溯，认为是匹配的第一个节点，如果可以匹配，向四个方向回溯匹配第二个字符，依次类推，直到找到一个可以匹配的字符
1. 回溯的时候需要记录一个已经匹配节点来剪枝
  80. 删除有序数组中的重复项 II
  
  给你一个有序数组 nums ，请你原地删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
双指针：维护两个指针 l 表示已经匹配过的位置，r 表示待匹配的位置，再维护一个 count 表示当前位置已经出现过的次数（其实可以直接匹配 nums[r] == nums[r - 2]，这样来判断是否出现过超过两次了）
1. 当 nums[r] == nums[r-1] 的时候 count++，如果 count > 2，那么跳过赋值，否则 nums[l++] = nums[r]，之后 r++
  81. 搜索旋转排序数组 II
  
  已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。
二分查找，因为数据可能重复，初始 left = 0, right = nums.length - 1，当 nums[left] == nums[right] 的时候，需要将 right--，直到两者不相等，这样当二分查找找到的 nums[right] >= mid 的时候，就不需要考虑 mid 出现在左边旋转后的位置上了
1. 对于找到的 target进行判断是否等于 nums[right]、nums[left]、nums[mid]，如果是直接返回
2. 否则需要根据 nums[left]、nums[right]、target 和 nums[mid] 来判断 mid 到底处于旋转左边和旋转右边的位置，以及 target 处于的位置，当明确这个位置后就可以修改 left、right 的值了
  82. 删除排序链表中的重复元素 II
  
  存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。返回同样按升序排列的结果链表。
使用一个额外的哑节点（dummy node）来指向链表的头节点，使用指针 cur 开始遍历，维护一个 count 计数，表示重复数据，如果 cur.next.val != cur.val，此时 count = 1 的话，就认为 cur 的值只出现过一次，那么将其加入到新的 dummy 链表里面去。
1. 遍历完成之后，需要处理下最后一个 cur 指针，然后将尾节点指向 null，最终返回 dummy.next
  83. 删除排序链表中的重复元素
  
  存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。返回同样按升序排列的结果链表。
和 82 解决方法一样，只是加入 dummy 的条件不一样

2021-08

36. 有效的数独

37. 解数独

38. 外观数列

39. 组合总和

40. 组合总和 II

41. 缺失的第一个正数

42. 接雨水

43. 字符串相乘

44. 通配符匹配

45. 跳跃游戏 II

46. 全排列

47. 全排列 II

48. 旋转图像

49. 字母异位词分组

50. Pow(x, n)

51. N 皇后

52. N皇后 II

53. 最大子序和

54. 螺旋矩阵

55. 跳跃游戏

56. 合并区间

57. 插入区间

58. 最后一个单词的长度

59. 螺旋矩阵 II

60. 排列序列

61. 旋转链表

62. 不同路径

63. 不同路径 II

64. 最小路径和

65. 有效数字

68. 文本左右对齐

69. x 的平方根

70. 爬楼梯

71. 简化路径

72. 编辑距离

73. 矩阵置零

74. 搜索二维矩阵

75. 颜色分类

76. 最小覆盖子串

77. 组合

78. 子集

79. 单词搜索

80. 删除有序数组中的重复项 II

81. 搜索旋转排序数组 II

82. 删除排序链表中的重复元素 II

83. 删除排序链表中的重复元素