前置说明，刷题采用语言为 Java，JDK 版本为 11。
1. 数组
1.1 双指针
双指针适用于具有单调性的数组中。
1.1.1 最多水
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
这道题的难点在于证明双指针的正确性。直观想法，如果移动指针，宽度一定会减少。如果移动高的柱子面积一定会减少，移动矮的柱子面积则不一定变化（可能出现更高的柱子）。
如果是左边的柱子较短，按照推论，就算移动右边的柱子高度也不会变化。所以我们移动左边的柱子，i++。而对于这个搜索空间也就是消除一行。同理如果是移动右边的柱子，j++。也就是消除一列。
// 双指针
public class ContainerWithMostWater {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int res = 0;
while (left < right) {
res = height[left] < height[right] ?
Math.max(res, (right - left) * height[left++]) :
Math.max(res, (right - left) * height[right--]);
}
return res;
}
}1.1.2 n 数之和
n 数之和本质都是固定其中的 n - m 数，让最后的解题变成两数之和问题（力扣的四数之和存在溢出问题，需要注意转 long）。
// 这是一个三数之和问题。双指针，将三数之和转化为两数之和问题
public class ThreeSum {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
for (int first = 0; first < nums.length; first++) {
// 去除重复值
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// 算是取巧，简化写法，之后判断写成 nums[i] + nums[j] + nums[first] == 0 也可以
int target = -nums[first];
for (int i = first + 1, j = nums.length - 1; i < j; i++) {
if (i > first + 1 && nums[i] == nums[i - 1]) {
continue;
}
// 注意要先剔除右边的范围，因为 i 本身在移动
while (i < j && nums[i] + nums[j] > target) {
j--;
}
if (i < j && nums[i] + nums[j] == target) {
res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[first])));
}
}
}
return res;
}
}下面是求三数之和最接近 target，本质原理和上题差不多（但是因为是最接近的数，所以只能去重，双指针不能随意移动）。
public class ThreeSumClosest {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int res = Integer.MAX_VALUE;
for (int first = 0; first < nums.length - 2; first++) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int i = first + 1, j = nums.length - 1;
while (i < j) {
int sum = nums[i] + nums[j] + nums[first];
if (sum == target) {
return target;
}
if (Math.abs(sum - target) < Math.abs(res - target)) {
res = sum;
}
// 分别对左右进行去重（本身可以不做，但是去重可以减少外层循环）
if (sum > target) {
int tmp = j - 1;
while (i < tmp && nums[j] == nums[tmp]) {
tmp--;
}
j = tmp;
} else {
int tmp = i + 1;
while (tmp < j && nums[i] == nums[tmp]) {
tmp++;
}
i = tmp;
}
}
}
return res;
}
}1.1.3 两数之和Ⅱ
给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
你可以假设每个输入只对应唯一的答案 ，而且你不可 重复使用相同的元素。你所设计的解决方案必须只使用常量级的额外空间。
这次题目限制不能使用额外空间，就不能使用 hash 表，最简单的就是双指针。left 为 0，right 为 length - 1。在双指针的基础上还能通过二分进一步优化时间。
public class TwoSum2 {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int l = 0, r = n - 1;
while (l < r) {
int mid = (r - l) / 2 + l;
if (numbers[l] + numbers[mid] > target) {
r = mid - 1;
} else if (numbers[mid] + numbers[r] < target) {
l = mid + 1;
} else if (numbers[l] + numbers[r] < target) {
l++;
} else if (numbers[l] + numbers[r] > target) {
r--;
} else {
return new int[]{l + 1, r + 1};
}
}
return new int[]{0, 0};
}
}1.2 模拟
1.2.1 螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
题目本身就是一个模拟，主要思路是固定四条边界，以一次螺旋作为一个周期进行循环（之后的螺旋矩阵Ⅱ同理）。
public class SpiralMatrix {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
int n = matrix.length, m = matrix[0].length;
int top = 0, left = 0, right = m - 1, bottom = n - 1;
int numLeft = m * n;
while (numLeft >= 1) {
for (int i = left; i <= right && numLeft >= 1; i++) {
res.add(matrix[top][i]);
numLeft--;
}
top++;
for (int i = top; i <= bottom && numLeft >= 1; i++) {
res.add(matrix[i][right]);
numLeft--;
}
right--;
for (int i = right; i >= left && numLeft >= 1; i--) {
res.add(matrix[bottom][i]);
numLeft--;
}
bottom--;
for (int i = bottom; i >= top && numLeft >= 1; i--) {
res.add(matrix[i][left]);
numLeft--;
}
left++;
}
return res;
}
}1.3 基本操作
1.3.1 排序
排序操作
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
public class MergeIntervals {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
List<int[]> res = new ArrayList<>();
for (int[] interval : intervals) {
int l = interval[0], r = interval[1];
if (res.size() == 0 || res.get(res.size() - 1)[1] < l) {
res.add(new int[]{l, r});
} else {
res.get(res.size() - 1)[1] = Math.max(res.get(res.size() - 1)[1], r);
}
}
return res.toArray(new int[res.size()][]);
}
}优势洗牌
给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]一个很明显的“田忌赛马”问题，然而我们并不需要考虑太多，本质是个贪心思想。如果 nums1 > nums2，那么就直接填入，反之，就选取一个最小值“填充”。需要根据 nums2 进行索引填充，排序时不能改变索引顺序。
public class AdvantageShuffle {
public int[] advantageCount1(int[] nums1, int[] nums2) {
int n = nums1.length;
// 降序排列
PriorityQueue<int[]> maxQ = new PriorityQueue<>(
(int[] i, int[] j) -> j[1] - i[1]
);
for (int i = 0; i < n; i++) {
maxQ.offer(new int[]{i, nums2[i]});
}
Arrays.sort(nums1);
int left = 0, right = n - 1;
int[] res = new int[n];
while (!maxQ.isEmpty()) {
int[] pair = maxQ.poll();
int i = pair[0], val = pair[1];
if (val < nums1[right]) {
res[i] = nums1[right--];
} else {
res[i] = nums1[left++];
}
}
return res;
}
}解法二：（这个问题的主要难点在于如何对 nums2 进行排序）
public class AdvantageShuffle {
public int[] advantageCount(int[] nums1, int[] nums2) {
int n = nums1.length;
Integer[] idx = new Integer[n];
// nums2 索引，idx 左边表示最小数据
for (int i = 0; i < n; i++) {
idx[i] = i;
}
Arrays.sort(nums1);
Arrays.sort(idx, Comparator.comparingInt(i -> nums2[i]));
// 根据 nums2 数据升序，排序 nums2(索引)
int L = 0, R = n - 1;
for (int i : nums1) {
// 如果能够 > num2 比较小的数，就放在这边
if (i > nums2[idx[L]]) {
nums2[idx[L++]] = i;
} else {
nums2[idx[R--]] = i;
}
}
return nums2;
}
}快速排序
快排本质即先对一个数（基准值，基准值有多种选择）排好序，保证基准值的左边都比其小，右边都比基准值大（可以看作二叉搜索树的构建）。
public class SortAArray {
private final Random random = new Random();
public int[] sortArray(int[] nums) {
sort(nums, 0, nums.length - 1);
return nums;
}
public void sort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int p = partition(nums, l, r);
sort(nums, l, p - 1);
sort(nums, p + 1, r);
}
public int partition(int[] nums, int l, int r) {
// 选取基准值
int index = random.nextInt(r - l + 1) + l;
swap(nums, l, index);
int pivot = nums[l];
int lt = l;
for (int i = l + 1; i <= r; i++) {
if (nums[i] < pivot) {
lt++;
swap(nums, i, lt);
}
}
swap(nums, l, lt);
return lt;
}
}数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
题目可以转化为求排序之后，n - k 对应索引的数。题目可以用快排的基准值来解决问题。
public class KthLargestElementInAnArray {
private final Random random = new Random();
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
int l = 0, r = n - 1;
k = n - k;
while (l <= r) {
int p = partition(nums, l, r);
if (p < k) {
l = p + 1;
} else if (p > k) {
r = p - 1;
} else {
return nums[p];
}
}
return -1;
}
public int partition(int[] nums, int l, int r) {
int index = random.nextInt(r - l + 1) + l;
swap(nums, l, index);
int pivot = nums[l], lt = l;
for (int i = l + 1; i <= r; i++) {
if (nums[i] < pivot) {
lt++;
swap(nums, i, lt);
}
}
swap(nums, l, lt);
return lt;
}
public void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}归并排序
所有递归的算法，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码。
归并排序框架代码：
public class SortAArray {
private int[] temp;
public int[] sortArray(int[] nums) {
temp = new int[nums.length];
mergeSort(nums, 0, nums.length - 1);
return nums;
}
public void mergeSort(int[] nums, int left, int right) {
if (left >= right) {
return;
}
int mid = (right - left) / 2 + left;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
public void merge(int[] nums, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left, j = mid + 1;
for (int p = left; p <= right; p++) {
if (i == mid + 1) {
nums[p] = temp[j++];
} else if (j == right + 1) {
nums[p] = temp[i++];
} else if (temp[i] > temp[j]) {
nums[p] = temp[j++];
} else {
// <= 保证稳定性，因为 i 本身就在 j 之前
nums[p] = temp[i++];
}
}
}
}剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
首先可以明确的是，正序排列的数组不存在逆序对（前面的数字 <= 后面的数字）。这类问题都是在归并的同时进行操作来简化时间复杂度。
如果 num[i] = 5 归并上去，可以得出比 5 小的数的范围为 [mid + 1, j)（右半边已经归并上去的部分）。这种思路是求 j 之前有多少比 i 小的数字，也可以求 i 之后比 j 大的数字。
public class ReversePairsInAnArray {
private int[] temp;
public int reversePairs(int[] nums) {
int n = nums.length;
if (n == 0 || n == 1) {
return 0;
}
temp = new int[n];
return sort(nums, 0, n - 1);
}
public int sort(int[] nums, int left, int right) {
if (left == right) {
return 0;
}
int mid = (right - left) / 2 + left;
int leftPairs = sort(nums, left, mid);
int rightPairs = sort(nums, mid + 1, right);
// 表示当前数组已经排序结束
if (nums[mid] <= nums[mid + 1]) {
return leftPairs + rightPairs;
}
return leftPairs + rightPairs + merge(nums, left, mid, right);
}
public int merge(int[] nums, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int i = left, j = mid + 1;
int count = 0;
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = temp[j++];
} else if (j > right) {
nums[k] = temp[i++];
count += right - mid;
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i++];
// count += (j - 1) - (mid + 1) + 1
count += j - mid - 1;
} else {
nums[k] = temp[j++];
// count += mid - i + 1; 反过来求
}
}
return count;
}
}计算右侧小于当前元素的个数
给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素问题的本质还是求逆序对，但题目对索引的安排有要求。可以使用 index[] 保持索引位置不变。
public class CountOfSmallerNumbersAfterSelf {
private int[] temp;
private int[] count;
// 使用 index 数组存储对应原本的下表
private int[] index;
public List<Integer> countSmaller(int[] nums) {
List<Integer> res = new ArrayList<>();
int n = nums.length;
count = new int[n];
temp = new int[n];
index = new int[n];
for (int i = 0; i < n; i++) {
index[i] = i;
}
sort(nums, 0, n - 1);
for (int c : count) {
res.add(c);
}
return res;
}
public void sort(int[] nums, int left, int right) {
if (left == right) {
return;
}
int mid = (right - left) / 2 + left;
sort(nums, left, mid);
sort(nums, mid + 1, right);
// 归并排序的优化，如果索引数组有序，则不存在逆序关系，没有必要合并
if (nums[index[mid]] <= nums[index[mid + 1]]) {
return;
}
merge(nums, left, mid, right);
}
public void merge(int[] nums, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = index[i];
}
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
index[k] = temp[j++];
} else if (j > right) {
index[k] = temp[i++];
count[index[k]] += (right - mid);
} else if (nums[temp[i]] <= nums[temp[j]]) {
// 使用 <= 保证稳定性
index[k] = temp[i++];
// 计算已经归并上去的代码，因为已经归并上去的代码一定比当前 nums[i] 小
// (j - 1) - (mid + 1) + 1 = j - mid - 1
count[index[k]] += j - mid - 1;
} else {
index[k] = temp[j++];
}
}
}
}翻转对
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。你需要返回给定数组中的重要翻转对的数量。
题目要求导致我们不能像逆序对一样一边合并一边进行计数，需要单独进行运算。同理，遍历左边的区间，如果存在满足情况的 i，那 i 之后的索引也满足（num[i] <= nums[i + 1]）。只需要找到不满足的情况，计算前面的值即可。
public class ReversePairs {
private int[] temp;
public int reversePairs(int[] nums) {
int n = nums.length;
temp = new int[n];
return sort(nums, 0, n - 1);
}
public int sort(int[] nums, int left, int right) {
if (left == right) {
return 0;
}
int mid = (right - left) / 2 + left;
return sort(nums, left, mid)
+ sort(nums, mid + 1, right)
+ merge(nums, left, mid, right);
}
// 需要先判断翻转对，之后再进行归并
public int merge(int[] nums, int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = nums[i];
}
int end = mid + 1;
int count = 0;
for (int i = left; i <= mid; i++) {
// 满足 num[i - 1] 的部分，肯定也满足 num[i] (num[i] >= num[i - 1])
// 每次都只需要扩张区间即可，不需要回头
while (end <= right && (long) nums[i] > (long) nums[end] * 2) {
end++;
}
// count += (end - 1) - (mid + 1) + 1;
count += end - mid - 1;
}
int i = left, j = mid + 1;
for (int k = left; k <= right; k++) {
if (i > mid) {
nums[k] = temp[j++];
} else if (j > right) {
nums[k] = temp[i++];
} else if (temp[i] <= temp[j]) {
nums[k] = temp[i++];
} else {
nums[k] = temp[j++];
}
}
return count;
}
}区间和的个数
给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。区间和本质就是求前缀和之差，对应 i，j 和在区间内即可。把归并稍微修改即可。可以使用类似滑动窗口进行优化，找出窗口的长度，即为当前区间和满足的个数。
public class CountOfRangeSum {
private long[] temp;
private int lower;
private int upper;
public int countRangeSum(int[] nums, int lower, int upper) {
int n = nums.length;
temp = new long[n + 1];
this.lower = lower;
this.upper = upper;
long[] preSum = new long[n + 1];
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
return sort(preSum, 0, n);
}
public int sort(long[] nums, int l, int r) {
if (l == r) {
return 0;
}
int mid = (r - l) / 2 + l;
int left = sort(nums, l, mid);
int right = sort(nums, mid + 1, r);
return left + right + merge(nums, l, mid, r);
}
public int merge(long[] nums, int l, int m, int r) {
for (int i = l; i <= r; i++) {
temp[i] = nums[i];
}
int count = 0;
int start = m + 1, end = m + 1;
for (int i = l; i <= m; i++) {
// 同逆序对，找出区间进行扩张即可
while (start <= r && nums[start] - nums[i] < lower) {
start++;
}
while (end <= r && nums[end] - nums[i] <= upper) {
end++;
}
count += end - start;
}
int i = l, j = m + 1;
for (int p = l; p <= r; p++) {
if (i == m + 1) {
nums[p] = temp[j++];
} else if (j == r + 1) {
nums[p] = temp[i++];
} else if (temp[i] > temp[j]) {
nums[p] = temp[j++];
} else {
nums[p] = temp[i++];
}
}
return count;
}
}1.3.2 随机数
O(1) 时间插入、删除和获取随机元素
实现RandomizedSet 类：
RandomizedSet() 初始化 RandomizedSet 对象；
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
- bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
- int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。
想要插入和删除是 O(1)，库中的 HashSet 可以帮我们完成，但是需要使用随机数，我们必须就要使用数组。而如果想要对数组的时间操作压缩到 O(1)，就需要在最后删除和插入。使用哈希表进行辅助，如果删除数字就将其移到最后。
class RandomizedSet {
private final HashMap<Integer, Integer> valToIndex;
private final List<Integer> list;
private final Random random;
public RandomizedSet() {
valToIndex = new HashMap<>();
list = new ArrayList<>();
random = new Random();
}
public boolean insert(int val) {
if (valToIndex.containsKey(val)) {
return false;
}
list.add(val);
valToIndex.put(val, list.size() - 1);
return true;
}
public boolean remove(int val) {
if (!valToIndex.containsKey(val)) {
return false;
}
// 交换删除的数字和最后的数字，不要忘记更新哈希表
int index = valToIndex.get(val), last = list.get(list.size() - 1);
list.set(index, last);
list.remove(list.size() - 1);
valToIndex.put(last, index);
valToIndex.remove(val);
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}黑名单中的随机数
给定一个整数 n 和一个 无重复 黑名单整数数组 blacklist 。设计一种算法，从 [0, n - 1] 范围内的任意整数中选取一个 未加入 黑名单 blacklist 的整数。任何在上述范围内且不在黑名单 blacklist 中的整数都应该有 同等的可能性 被返回。
优化你的算法，使它最小化调用语言 内置 随机函数的次数。
实现 Solution 类:
- Solution(int n, int[] blacklist) 初始化整数 n 和被加入黑名单 blacklist 的整数；
- int pick() 返回一个范围为 [0, n - 1] 且不在黑名单 blacklist 中的随机整数。
输入
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
输出
[null, 0, 4, 1, 6, 1, 0, 4]
解释
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // 返回0，任何[0,1,4,6]的整数都可以。注意，对于每一个pick的调用，
// 0、1、4和6的返回概率必须相等(即概率为1/4)。
solution.pick(); // 返回 4
solution.pick(); // 返回 1
solution.pick(); // 返回 6
solution.pick(); // 返回 1
solution.pick(); // 返回 0
solution.pick(); // 返回 4这里题目如果直接使用数组或者 HashSet 会导致内存超出。因为文中要求我们最少化使用 rand 函数，所以同理的思路，把所有的黑名单数字放在后面。因为不直接使用数组，所以通过 HashMap，将超出位置的黑名单数字映射到正确的位置。
public class Solution {
private final HashMap<Integer, Integer> hashMap = new HashMap<>();
private final Random random = new Random();
private final int sz;
public Solution(int n, int[] blacklist) {
sz = n - blacklist.length;
// 先将所有黑名单的数字存入
for (int item : blacklist) {
hashMap.put(item, -1);
}
int last = n - 1;
for (int item : blacklist) {
// 如果 blacklist 中的数字已经在范围内，就不需要映射
if (item < sz) {
// 跳过所有黑名单中的数字
while (hashMap.containsKey(last)) {
last--;
}
hashMap.put(item, last);
last--;
}
}
}
public int pick() {
int index = random.nextInt(sz);
return hashMap.getOrDefault(index, index);
}
}1.3.3 去重算法
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
这个题目需要满足三个条件：
- 去除重复字符串（通过 boolean[] 进行判断，如果存在重复字符串直接略过）；
- 不能打乱相对顺序（可以使用 Stack 进行保存，如果 stack.peek() > c，则进行替换）；
- 在所有符合上一条要求的去重字符串中，字典序最小的作为最终结果（可以使用 count[] 查询是否存在其他字母，如果存在才对字典序进行去除字母）。
public class RemoveDuplicateLetters {
public String removeDuplicateLetters(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
Stack<Character> stack = new Stack<>();
boolean[] inStack = new boolean[26];
for (char c : s.toCharArray()) {
count[c - 'a']--;
if (inStack[c - 'a']) {
continue;
}
while (!stack.isEmpty() && stack.peek() > c && count[stack.peek() - 'a'] != 0) {
inStack[stack.pop() - 'a'] = false;
}
stack.push(c);
inStack[c - 'a'] = true;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}1.4 差分数组
差分数组的思想类似前缀和，如果需要反复针对 i……j 内进行增减，数组内正常需要进行遍历。但是在差分数组中，只需要更改一次数字即可（剩下的数组可以通过直接差分数组进行构造）。
int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
这样构造差分数组 diff，就可以快速进行区间增减的操作，如果你想对区间 nums[i..j] 的元素全部加 3，那么只需要让 diff[i] += 3，然后再让 diff[j+1] -= 3 即可。
Difference 工具类如下：
public class Difference {
private final int[] diff;
private final int n;
public Difference(int[] nums) {
n = nums.length;
diff = new int[n];
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
public Difference(int n) {
this.n = n;
diff = new int[n];
}
public void increment(int i, int j, int val) {
diff[i] += val;
if (j + 1 < n) {
diff[j + 1] -= val;
}
}
public int[] result() {
int[] res = new int[n];
res[0] = diff[0];
for (int i = 1; i < n; i++) {
res[i] += diff[i] + res[i - 1];
}
return res;
}
}1.4.1 航班预定统计
这里有 n 个航班，它们分别从 1 到 n 进行编号。有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。
请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]这题是标准的差分数组模板：
public class CorporateFlightBookings {
public int[] corpFlightBookings(int[][] bookings, int n) {
int[] res = new int[n];
Difference difference = new Difference(n);
for (int[] booking : bookings) {
difference.increment(booking[0] - 1, booking[1] - 1, booking[2]);
}
return difference.result();
}
}1.4.2 拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
public class CarPooling {
public boolean carPooling(int[][] trips, int capacity) {
// 因为 to 最高值为 10000，所以数组设定为 10001
int n = 10001;
Difference difference = new Difference(n);
for (int[] trip : trips) {
// 乘客在 j 已经下车，在 j - 1 ((j - 1) + 1) 处停止增加
difference.increment(trip[1], trip[2] - 1, trip[0]);
}
int[] res = difference.result();
for (int i : res) {
if (i > capacity) {
return false;
}
}
return true;
}
}1.5 前缀和
1.5.1 二维区域和检索
给定一个二维矩阵 matrix，以下类型的多个请求：
- 计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。
实现 NumMatrix 类：
- NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化；
- int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
不妨将 preSum 设为 row，col 组成的矩形的综合，任何小矩形都可以转化为大矩形的切割结果。
class NumMatrix {
private final int[][] preSum;
public NumMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
preSum = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1]
- preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1]
- preSum[row2 + 1][col1] + preSum[row1][col1];
}
}1.5.2 按权重随机选择
给你一个 下标从 0 开始 的正整数数组 w ，其中 w[i] 代表第 i 个下标的权重。请你实现一个函数 pickIndex ，它可以 随机地 从范围 [0, w.length - 1] 内（含 0 和 w.length - 1）选出并返回一个下标。选取下标 i 的 概率 为 w[i] / sum(w) 。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
通过权重的问题，可以转化为前缀和之后取随机数。如下图，将 w = [1,3,2,1]，转化为随机数问题（取值应该为 [1, 7]，因为 0 也算占位符）。
随机数的范围确定好了，之后就是确定索引，根据图示，我们应该查找最近的左边界（在 preSum 中寻找大于等于 target 的最小元素索引）。
class Solution {
private final int[] preSum;
private final Random rand = new Random();
public Solution(int[] w) {
int n = w.length;
preSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
preSum[i] += preSum[i - 1] + w[i - 1];
}
}
public int pickIndex() {
int n = preSum.length;
int target = rand.nextInt(preSum[n - 1]) + 1;
// preSum 转化为原数组不要忘记 - 1
return left_bound(preSum, target) - 1;
}
private int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] >= target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
}1.6 滑动窗口
1.6.1 最小覆盖字串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量； - 如果
s中存在这样的子串，我们保证它是唯一的答案。
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。滑动窗口窗口标准写法，通过 HashMap 存储对应 window 和 need。每次 right 都往右移动，如果满足收缩条件，就进行收缩。
public class MinimumWindowSubstring {
public String minWindow(String s, String t) {
HashMap<Character, Integer> window = new HashMap<>();
HashMap<Character, Integer> need = new HashMap<>();
for (char i : t.toCharArray()) {
need.put(i, need.getOrDefault(i, 0) + 1);
}
int left = 0, right = 0;
int len = Integer.MAX_VALUE;
int start = 0, count = 0;
int n = s.length();
while (right < n) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
count++;
}
}
while (count == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
count--;
}
window.put(d, window.get(d) - 1);
}
}
}
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
}1.6.2 KMP
我们经常会碰到字符串匹配问题，如下题：
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。
一般会通过两个指针，i j，分别在两个数组中分别移动。KMP 算法妙处在于 i 指针不后退，时间复杂度被压缩到了 O(n)。
kmp 的核心在于 next 数组，这个存储当前索引字串的相同前后缀的长度，如果后缀相同，那么移动时就不需要每次都将从零开始，j 就可以移动到上一个公共前后缀处（如果存在）。
public class FindTheIndexOfTheFirstOccurrenceInAString {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
int[] next = next(needle);
int j = 0;
for (int i = 0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
j = next[j - 1];
}
if (haystack.charAt(i) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i - j + 1;
}
}
return -1;
}
// next 数组表示共同前后缀
public int[] next(String needle) {
int n = needle.length();
int[] next = new int[n];
// 当前共同前后缀长度
int prefix_len = 0;
for (int i = 1; i < n; i++) {
// 如果不相同就把 prefix 初始化到最近的前后缀处
while (prefix_len > 0 && needle.charAt(prefix_len) != needle.charAt(i)) {
prefix_len = next[prefix_len - 1];
}
// 如果前后缀相同，就不断移动 prefix_len++
if (needle.charAt(prefix_len) == needle.charAt(i)) {
prefix_len++;
}
next[i] = prefix_len;
}
return next;
}
}这个题目也可以理解成一个固定长度的滑动窗口，每次移动 i 也可以得出问题的解，但是使用 subString 方法的开销太大，远不如 KMP 算法的索引移动。
1.6.3 Rabin Karp
Rabin Karp 算法的核心在于“珠算”，即为一个数添加某一位或者删除某一位。
/* 在最低位添加一个数字 */
int number = 8264;
// number 的进制
int R = 10;
// 想在 number 的最低位添加的数字
int appendVal = 3;
// 运算，在最低位添加一位
number = R * number + appendVal;
// 此时 number = 82643
/* 在最高位删除一个数字 */
int number = 8264;
// number 的进制
int R = 10;
// number 最高位的数字
int removeVal = 8;
// 此时 number 的位数
int L = 4;
// 运算，删除最高位数字
number = number - removeVal * R ^ (L - 1);
// 此时 number = 264重复的 DNA 序列
DNA序列 由一系列核苷酸组成，缩写为 ‘A’, ‘C’, ‘G’ 和 ‘T’.。
例如，”ACGAATTCCG” 是一个 DNA序列 。在研究 DNA 时，识别 DNA 中的重复序列非常有用。给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。
根据题目分析，我们需要找出重复的长度为 10 的序列，这个题目可以通过固定长度的滑动窗口来做。
public class RepeatedDNASequences {
public List<String> findRepeatedDnaSequences(String s) {
int left = 0, right = 0;
int len = 10;
int n = s.length();
// 存储重复字符串
Set<String> seen = new HashSet<>();
Set<String> temp = new HashSet<>();
for (int i = 0; i <= s.length() - 10; i++) {
String sub = s.substring(i, i + len);
if (seen.contains(sub)) {
temp.add(sub);
} else {
seen.add(sub);
}
}
return new ArrayList<>(temp);
}
}然而每次都使用 subString 肯定会导致开销变大。因为 DNA 序列只存在 ACGT 这四个字符，我们可以使用 4 进制进行存储。总共需要 2 ^ 20 bit 的空间，对于 int 类型也可以存入。
public class RepeatedDNASequences {
public List<String> findRepeatedDnaSequences(String s) {
// 将 String 转化为 int 数组
int n = s.length();
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
switch (s.charAt(i)) {
case 'A':
nums[i] = 0;
break;
case 'G':
nums[i] = 1;
break;
case 'C':
nums[i] = 2;
break;
case 'T':
nums[i] = 3;
break;
}
}
Set<Integer> seen = new HashSet<>();
Set<String> res = new HashSet<>();
// 位数，数制（4 进制，10 位）
int L = 10, R = 4;
int LR = (int) Math.pow(R, L - 1);
int left = 0, right = 0;
int windowsHash = 0;
while (right < n) {
windowsHash = R * windowsHash + nums[right];
right++;
if (right - left == L) {
if (seen.contains(windowsHash)) {
res.add(s.substring(left, right));
} else {
seen.add(windowsHash);
}
windowsHash = windowsHash - nums[left] * LR;
left++;
}
}
return new ArrayList<>(res);
}
}完整算法
完整 Rabin Karp 可以应对各种字符，所以我们需要对 256 个 ASCⅡ 字符进行再编码。但是因为溢出问题，我们需要使用哈希取模，使用一个比较大的素数作为求模的除数。
// Rabin-Karp 指纹字符串查找算法
int rabinKarp(String txt, String pat) {
// 位数
int L = pat.length();
// 进制（只考虑 ASCII 编码）
int R = 256;
// 取一个比较大的素数作为求模的除数
long Q = 1658598167;
// R ^ (L - 1) 的结果
long RL = 1;
for (int i = 1; i <= L - 1; i++) {
// 计算过程中不断求模，避免溢出
RL = (RL * R) % Q;
}
// 计算模式串的哈希值，时间 O(L)
long patHash = 0;
for (int i = 0; i < pat.length(); i++) {
patHash = (R * patHash + pat.charAt(i)) % Q;
}
// 滑动窗口中子字符串的哈希值
long windowHash = 0;
// 滑动窗口代码框架，时间 O(N)
int left = 0, right = 0;
while (right < txt.length()) {
// 扩大窗口，移入字符
windowHash = ((R * windowHash) % Q + txt.charAt(right)) % Q;
right++;
// 当子串的长度达到要求
if (right - left == L) {
// 根据哈希值判断是否匹配模式串
if (windowHash == patHash) {
// 当前窗口中的子串哈希值等于模式串的哈希值
// 还需进一步确认窗口子串是否真的和模式串相同，避免哈希冲突
// 因为 hash 冲突防止不同字符串相同哈希值
if (pat.equals(txt.substring(left, right))) {
return left;
}
}
// 缩小窗口，移出字符
windowHash = (windowHash - (txt.charAt(left) * RL) % Q + Q) % Q;
// X % Q == (X + Q) % Q 是一个模运算法则
// 因为 windowHash - (txt[left] * RL) % Q 可能是负数
// 所以额外再加一个 Q，保证 windowHash 不会是负数
left++;
}
}
// 没有找到模式串
return -1;
}1.7 二分搜索
几个最常用的二分查找场景：寻找一个数、寻找左侧边界、寻找右侧边界。
public class BinarySearch {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
return mid;
}
}
return -1;
}
}1.7.1 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
public class FindFirstAndLastPositionOfElementInSortedArray {
public int[] searchRange(int[] nums, int target) {
int n = nums.length;
int[] res = new int[2];
int left = 0, right = nums.length - 1;
// 查询左边界
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
res[0] = (left < n && nums[left] == target) ? left : -1;
left = 0;
right = nums.length - 1;
// 查询右边界
while (left <= right) {
int mid = (right - left) / 2 + left;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
res[1] = (left - 1 >= 0 && nums[left - 1] == target) ? (left - 1) : -1;
return res;
}
}
1.7.2 解方程
如果将搜索左边界的过程抽象成一张图，可以画出一个函数式。
而题目一般不会明确告诉你使用这个思路，我们需要自己从题目中抽象出 x，f(x)，以及目标值 target。
爱吃香蕉的珂珂
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
通过题目给出的条件，我们可以通过速度 k（自变量 x）得出所需时间，H 表示极限时间，我们需要在这个条件内令 x 最小。问题转化成了求左边界问题。
public class KokoEatingBananas {
// 本题需要注意溢出问题
public int minEatingSpeed(int[] piles, int h) {
// 题目中 piles[i] 最大值为 10^9
int left = 1, right = (int) Math.pow(10, 9);
while (left <= right) {
int mid = (right - left) / 2 + left;
if (f(piles, mid) > h) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
public long f(int[] piles, int x) {
long hours = 0;
for (int pile : piles) {
hours += pile / x;
if (pile % x > 0) {
hours++;
}
}
return hours;
}
}在 D 天内送达包裹的能力
传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
这题同理，也可以得出对应方程，以载重能力作为自变量 x，时间为 f(x)。
public class CapacityToShipPackagesWithinDDays {
public int shipWithinDays(int[] weights, int days) {
int left = 0, right = 0;
// 通过遍历得出最小的 left 和最大的 right
for (int weight : weights) {
left = Math.max(left, weight);
right += weight;
}
while (left <= right) {
int mid = (right - left) / 2 + left;
if (f(weights, mid) <= days) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return left;
}
public int f(int[] weights, int x) {
int days = 0;
int i = 0;
while (i < weights.length) {
int cap = x;
while (i < weights.length && cap >= weights[i]) {
cap -= weights[i];
i++;
}
days++;
}
return days;
}
}分割数组的最大值
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。这个题目乍看无解，但是可以转化为上面的装货问题。装货问题本质上就是划分若干子数组，得出最小的最大子数组和（最小载重），答案就呼之欲出了。
2. 暴力搜索
2.1 回溯
回溯遵循“不撞南墙不回头的道理”，在可能情况中进行遍历。在保存当前状态之后，进入下一个状态，或者撤回当前状态，继续遍历。
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表2.1.1 棋盘类问题
n 皇后问题
n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。
需要提前写一个判断方法，判断是否棋盘中是否存在重复（每次都一行一行放置，这样只需判断左上角、右上角、上面的放置）。
public class NQueens2 {
private int res = 0;
private int[][] check;
public int totalNQueens(int n) {
check = new int[n][n];
backtrack(check, 0);
return res;
}
public void backtrack(int[][] check, int start) {
int n = check.length;
if (start == n) {
res++;
return;
}
for (int i = 0; i < n; i++) {
if (isRight(check, start, i)) {
check[start][i] = 1;
backtrack(check, start + 1);
check[start][i] = 0;
}
}
}
// 因为从上往下放置，不需要下面的放置
public boolean isRight(int[][] check, int row, int col) {
int n = check.length;
// 确认其他列是否有冲突
for (int i = 0; i < row; i++) {
if (check[i][col] == 1) {
return false;
}
}
// 检查右上方
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (check[i][j] == 1) {
return false;
}
}
// 检查左上方
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (check[i][j] == 1) {
return false;
}
}
return true;
}
}解数独
编写一个程序，通过填充空格来解决数独问题。数独的解法需 遵循如下规则：
- 数字 1-9 在每一行只能出现一次；
- 数字 1-9 在每一列只能出现一次；
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次（数独部分空格内已填入了数字，空白格用 ‘.’ 表示）。
整体思路同 n 皇后问题，难点在于如何判断当天填写格子所在的 3 x 3 方框。
public class SudokuSolver {
public void solveSudoku(char[][] board) {
backtrack(board, 0, 0);
}
// 如果直接使用 void，会出现没有 base case 的情况
public boolean backtrack(char[][] board, int i, int j) {
int m = 9, n = 9;
if (j == n) {
return backtrack(board, i + 1, 0);
}
if (i == m) {
return true;
}
if (board[i][j] != '.') {
return backtrack(board, i, j + 1);
}
for (char ch = '1'; ch <= '9'; ch++) {
if (!judge(board, i, j, ch)) {
continue;
}
board[i][j] = ch;
if (backtrack(board, i, j + 1)) {
return true;
}
board[i][j] = '.';
}
return false;
}
public boolean judge(char[][] board, int r, int c, char n) {
for (int i = 0; i < 9; i++) {
// 判断行，列，3 x 3 方框
if (board[r][i] == n || board[i][c] == n ||
board[(r / 3) * 3 + i / 3][(c / 3) * 3 + i % 3] == n) {
return false;
}
}
return true;
}
}括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
双回溯，对左括号和右括号都进行回溯，如果不满足条件就结束。
public class GenerateParentheses {
private final List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
backtrack(n, n, new StringBuilder());
return res;
}
public void backtrack(int left, int right, StringBuilder sb) {
if (right < left || left < 0) {
return;
}
if (left == 0 && right == 0) {
res.add(sb.toString());
return;
}
sb.append('(');
backtrack(left - 1, right, sb);
sb.deleteCharAt(sb.length() - 1);
sb.append(')');
backtrack(left, right - 1, sb);
sb.deleteCharAt(sb.length() - 1);
}
}2.1.2 排列/组合/集合问题
- 形式一、元素无重不可复选，即
nums中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式；
以组合为例，如果输入nums = [2,3,6,7]，和为 7 的组合应该只有[7]。 - 形式二、元素可重不可复选，即
nums中的元素可以存在重复，每个元素最多只能被使用一次；
以组合为例，如果输入nums = [2,5,2,1,2]，和为 7 的组合应该有两种[2,2,2,1]和[5,2]。 - 形式三、元素无重可复选，即
nums中的元素都是唯一的，每个元素可以被使用若干次。
以组合为例，如果输入nums = [2,3,6,7]，和为 7 的组合应该有两种[2,2,3]和[7]。
组合总和
给你一个无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。candidates 中的同一个数字可以无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
这是一个标准的回溯问题，模板比较经典。主要是考虑如何剪枝。重复存在的原因是因为反复调用前面的元素，我们可以先对数组进行排序，搜索以第一个数为起点所有数的组合（这样之后就不需要考虑第一个数，因为我们已经排序，如果需要更大的数就往后进行遍历）。
// 回溯 + 剪枝
public class CombinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
// 排序帮助剪枝
Arrays.sort(candidates);
dfs(res, 0, candidates, target, new ArrayDeque<>());
return res;
}
// 设置 begin 表示下一个节点的位置
public void dfs(List<List<Integer>> res, int begin, int[] candidates, int target, Deque<Integer> node) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(node));
return;
}
for (int i = begin; i < candidates.length; i++) {
// 直接剪枝
if (target - candidates[i] < 0) {
break;
}
node.addLast(candidates[i]);
dfs(res, i, candidates, target - candidates[i], node);
node.removeLast();
}
}
}组合总和Ⅱ 的条件变成了数字使用一次，数组中会出现重复数字。所以需要考虑一次去重，去重可以参考 nSum 的去重方式。考虑完两个坑之后本题就套用模板的事情了。
public class CombinationSum2 {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
dfs(res, candidates, 0, target, new ArrayDeque<>());
return res;
}
public void dfs(List<List<Integer>> res, int[] candidates, int begin, int target, Deque<Integer> node) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(node));
return;
}
for (int i = begin; i < candidates.length; i++) {
if (target - candidates[i] < 0) {
break;
}
// 防止重复解
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
node.addLast(candidates[i]);
// 因为一个数只能使用一次，从 i + 1 开始
dfs(res, candidates, i + 1, target - candidates[i], node);
node.removeLast();
}
}
}全排列
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]因为是排列问题，最开始的选择就是谁作为当前的第一个节点。需要不断从第一个数开始进行遍历，需要使用 used 数组来存储是否被选入。之后因为存在重复数字，需要进行去重操作（同集合类问题）。
public class Permutations2 {
private final List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
backtrack(new ArrayList<>(), nums, new boolean[nums.length]);
return this.res;
}
public void backtrack(List<Integer> track, int[] nums, boolean[] used) {
if (track.size() == nums.length) {
this.res.add(new ArrayList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// 如果已经被使用就不排除
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
continue;
}
if (!used[i]) {
track.add(nums[i]);
used[i] = true;
backtrack(track, nums, used);
track.remove(track.size() - 1);
used[i] = false;
}
}
}
}子集
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]集合问题就不设置 base case，直接遍历到最后就能得出所有的结果：
public class Subsets2 {
private final List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
backtrack(new LinkedList<>(), nums, 0);
return res;
}
public void backtrack(LinkedList<Integer> track, int[] nums, int start) {
res.add(new ArrayList<>(track));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
track.addLast(nums[i]);
backtrack(track, nums, i + 1);
track.removeLast();
}
}
}划分为 k 个相等的子集
给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
这道题可以简化为高中的放球问题，有 k 个桶，将 nums 中的球全部放入，并保证总和相等。总共有两种考虑方式，以桶的角度或者以球的角度。
按照球的角度，每次都选择一个桶放置。题目优化的主要点在于，球放入那个桶结果都是一样的（与顺序无关），这是一个剪枝重大考虑。
public class PartitionToKEqualSumSubsets {
public boolean canPartitionKSubsets1(int[] nums, int k) {
int sum = 0;
for (int num : nums) {
sum += num;
}
// 如果不能整除直接返回 false
if (sum % k != 0) {
return false;
}
Arrays.sort(nums);
int n = nums.length;
// 通过倒序排序，针对下面的 bucket[i] + nums[index] > target
for (int i = 0, j = n - 1; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return backtrack(nums, 0, new int[k], sum / k);
}
public boolean backtrack(int[] nums, int index, int[] bucket, int target) {
int n = nums.length, k = bucket.length;
// 如果 index 已经为 n，已经装填结束，可以直接返回结果
if (index == n) {
return true;
}
for (int i = 0; i < k; i++) {
// 如果两个桶已经相等，说明已经装填结束
if (bucket[i] + nums[index] > target || (i > 0 && bucket[i] == bucket[i - 1])) {
continue;
}
bucket[i] += nums[index];
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
bucket[i] -= nums[index];
// 如果 index 无法放入当前桶中，放入其他桶中也无效，剪枝
if (bucket[i] == 0) {
return false;
}
}
return false;
}
}如果以桶为考虑，需要使用 used 记录数字是否使用过。题目给出 k <= 16，可以使用位运算代替数组，进一步节省空间。
public class PartitionToKEqualSumSubsets {
private final HashMap<Integer, Boolean> memo = new HashMap<>();
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % k != 0) {
return false;
}
Arrays.sort(nums);
int n = nums.length;
for (int i = 0, j = n - 1; i < j; i++, j--) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// 通过使用 16 位的 int 来代替 used 数组，节省空间消耗
return backtrack(k, 0, nums, 0, 0, sum / k);
}
public boolean backtrack(int k, int bucket, int[] nums,
int start, int used, int target) {
if (k == 0) {
// 所有桶都已经填满
return true;
}
if (memo.containsKey(used)) {
return memo.get(used);
}
if (bucket == target) {
// 当前桶装填完成，穷举下一个桶
boolean res = backtrack(k - 1, 0, nums, 0, used, target);
memo.put(used, res);
return res;
}
for (int i = start; i < nums.length; i++) {
if (((used >> i) & 1) == 1 || nums[i] + bucket > target) {
continue;
}
// 将 used 的 i 位设为 1
used |= 1 << i;
bucket += nums[i];
// 判断下一位数字是否可以填入
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
used ^= 1 << i;
bucket -= nums[i];
if (bucket == 0) {
return false;
}
while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
i++;
}
}
return false;
}
}2.2 DFS
DFS 算法就是回溯算法。深度优先搜索算法是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。
// 二叉树遍历框架
void traverse(TreeNode root) {
traverse(root.left);
traverse(root.right);
}
// 二维矩阵遍历框架
void dfs(int[][] grid, int i, int j, boolean[][] visited) {
int m = grid.length, n = grid[0].length;
if (i < 0 || j < 0 || i >= m || j >= n) {
// 超出索引边界
return;
}
if (visited[i][j]) {
// 已遍历过 (i, j)
return;
}
// 进入节点 (i, j)
visited[i][j] = true;
dfs(grid, i - 1, j, visited); // 上
dfs(grid, i + 1, j, visited); // 下
dfs(grid, i, j - 1, visited); // 左
dfs(grid, i, j + 1, visited); // 右
}2.3.1 岛屿问题
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1题目基于 Flood Fill 算法。即每次找到陆地（1）之后，我们都用海水（0）把对应岛屿替代。填充岛屿之后，剩下就是其他不相邻的岛屿。剩下的岛屿都是对应的变种。
public class NumberOfIslands {
public int numIslands(char[][] grid) {
int res = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
res++;
}
}
}
return res;
}
public void dfs(char[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
// 向上下左右进行填充
if (grid[i][j] == '1') {
grid[i][j] = '0';
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
}飞地数量
给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
这次题目增添了不能靠近边界的限制，那对边界进行遍历，将所有边界的岛屿消除即可（这里统计的为面积）。
public class NumberOfEnclaves {
public int numEnclaves(int[][] grid) {
int res = 0;
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; i++) {
dfs(grid, i, 0);
dfs(grid, i, n - 1);
}
for (int i = 0; i < n; i++) {
dfs(grid, 0, i);
dfs(grid, m - 1, i);
}
for (int[] ints : grid) {
for (int j = 0; j < n; j++) {
if (ints[j] == 1) {
res++;
}
}
}
return res;
}
public void dfs(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] == 1) {
grid[i][j] = 0;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
}1254.统计封闭岛屿的数目 要求统计完全由水包裹的陆地数量，同理将边界岛屿去除即可。
统计子岛屿
给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。
如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那么我们称 grid2 中的这个岛屿为 子岛屿 。请你返回 grid2 中 子岛屿 的 数目 。
因为是子岛屿，题目核心在于 grid2。只有 grid1[i][j] == grid2[i][j] == 1 才为子岛屿。如果 a 为 0，b 为 1，那 b 所在的岛屿就不是子岛屿，就使用 dfs 去除。剩下的岛屿就是答案。
public class CountSubIslands {
public int countSubIslands(int[][] grid1, int[][] grid2) {
int m = grid1.length, n = grid1[0].length;
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid1[i][j] == 0 && grid2[i][j] == 1) {
dfs(grid2, i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid2[i][j] == 1) {
res++;
dfs(grid2, i, j);
}
}
}
return res;
}
public void dfs(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i < 0 || i >= m || j < 0 || j >= n) {
return;
}
if (grid[i][j] == 1) {
grid[i][j] = 0;
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
}2.3 BFS
BFS 找到的路径一定是最短的，但代价就是空间复杂度可能比 DFS 大很多。问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离。
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核心数据结构
Set<Node> visited; // 避免走回头路
q.offer(start); // 将起点加入队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这里判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加入队列 */
for (Node x : cur.adj()) {
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
}
/* 划重点：更新步数在这里 */
step++;
}
}2.3.1 打开转盘锁
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
典型的 BFS 问题，状态列表便是将四个数字选择一个向上或下拨动，之后存储。
public class OpenTheLock {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>();
Collections.addAll(dead, deadends);
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
int res = 0;
visited.add("0000");
queue.offer("0000");
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (dead.contains(cur)) {
continue;
}
if (cur.equals(target)) {
return res;
}
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
queue.offer(up);
visited.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
queue.offer(down);
visited.add(down);
}
}
}
res++;
}
return -1;
}
// 将 s[j] 向上拨动一次
public String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] != '9') {
ch[j] += 1;
} else {
ch[j] = '0';
}
return new String(ch);
}
// 将 s[i] 向下拨动一次
public String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] != '0') {
ch[j] -= 1;
} else {
ch[j] = '9';
}
return new String(ch);
}
}BFS 算法还有一种稍微高级一点的优化思路：双向 BFS，可以进一步提高算法的效率。传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。
不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集。while 循环的最后交换 q1 和 q2 的内容，所以只要默认扩散 q1 就相当于轮流扩散 q1 和 q2。
public class OpenTheLock {
public int openLock(String[] deadends, String target) {
Set<String> dead = new HashSet<>();
Collections.addAll(dead, deadends);
// 使用 Set 快速判断是否存在
Set<String> q1 = new HashSet<>();
Set<String> q2 = new HashSet<>();
Set<String> visited = new HashSet<>();
int res = 0;
q1.add("0000");
q2.add(target);
while (!q1.isEmpty() && !q2.isEmpty()) {
Set<String> temp = new HashSet<>();
for (String cur : q1) {
if (dead.contains(cur)) {
continue;
}
if (q2.contains(cur)) {
return res;
}
visited.add(cur);
for (int j = 0; j < 4; j++) {
String up = plusOne(cur, j);
if (!visited.contains(up)) {
temp.add(up);
}
String down = minusOne(cur, j);
if (!visited.contains(down)) {
temp.add(down);
}
}
}
res++;
// temp 相当于 q1，交换进行 q2 扩散
q1 = q2;
q2 = temp;
}
return -1;
}
public String plusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] != '9') {
ch[j] += 1;
} else {
ch[j] = '0';
}
return new String(ch);
}
public String minusOne(String s, int j) {
char[] ch = s.toCharArray();
if (ch[j] != '0') {
ch[j] -= 1;
} else {
ch[j] = '9';
}
return new String(ch);
}
}2.3.2 滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字（上下左右）进行交换.最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态 board ，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
BFS 只能解决一维状态的问题，题目给出的二维的谜板数组。因为每次都是将 0 所在的位置进行上下左右移动，可以通过给出索引存在的上下左右对应的二维数组索引位压缩至一维数组。之后可以通过对应数组进行移动（给出的题解为适用于任何情况的题解，题目有限制大小，可以直接写出映射数组）。
public class SlidingPuzzle {
// 适用于任何 m * n 数组的情况
public int slidingPuzzle(int[][] board) {
int m = board.length, n = board[0].length;
StringBuilder sb = new StringBuilder();
int count = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
sb.append(count++);
}
}
sb.deleteCharAt(sb.length() - 1).append(0);
String target = sb.toString();
// 将二维数组压缩成一维，neighbor 中存储对应上下左右索引值
// 2 * 3 数组可以直接写出索引，如果针对 m * n 数组可以通过下述公式转化为一维数组
int[][] neighbor = new int[m * n][];
int k = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
List<Integer> temp = new ArrayList<>();
if (i - 1 >= 0) {
temp.add((i - 1) * n + j);
}
if (j - 1 >= 0) {
temp.add(i * n + j - 1);
}
if (j + 1 < n) {
temp.add(i * n + j + 1);
}
if (i + 1 < m) {
temp.add((i + 1) * n + j);
}
int size = temp.size();
neighbor[k] = new int[size];
for (int l = 0; l < size; l++) {
neighbor[k][l] = temp.get(l);
}
k++;
}
}
sb = new StringBuilder();
for (int[] i : board) {
for (int value : i) {
sb.append(value);
}
}
String start = sb.toString();
// BFS 框架
Queue<String> queue = new LinkedList<>();
HashSet<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
String cur = queue.poll();
if (target.equals(cur)) {
return step;
}
// 找到数字 0 的索引
int index = 0;
while (cur.charAt(index) != '0') {
index++;
}
for (int adj : neighbor[index]) {
String new_board = swap(cur.toCharArray(), adj, index);
if (!visited.contains(new_board)) {
queue.offer(new_board);
visited.add(new_board);
}
}
}
step++;
}
return -1;
}
private String swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
return new String(chars);
}
}3. 哈希表
3.1 原地哈希
3.1.1 缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
这个问题的难点在于如何使用常熟级别的额外空间，这个问题用到原地哈希。将数组的索引和值分别作为 Key 和 Value，即 num[i - 1] == i。
class FirstMissingPositive {
public int firstMissingPositive(int[] nums) {
// 将对应的值放入索引处（无需考虑非正整数和大于数组长度的情况，因为最后一定会被剔除）
for (int i = 0; i < nums.length; i++) {
while (nums[i] > 0 && nums[i] <= nums.length && nums[nums[i] - 1] != nums[i]) {
swap(nums, nums[i] - 1, i);
}
}
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return nums.length + 1;
}
public void swap(int[] nums, int index1, int index2) {
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = tmp;
}
}3.1.2 错误的集合
集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。
给定一个数组 nums 代表了集合 S 发生错误后的结果。请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。
输入：nums = [1,2,2,4]
输出：[2,3]
类似原地哈希的策略通过将每个索引对应的元素变成负数，以表示这个索引被对应过一次了。会导致有两个元素对应到了同一个索引，而且会有一个索引没有元素对应过去。
如果有反复 index 的情况，那就是重复的数。没有索引过去的数就是缺失的数（原数组已经进行过排序）。
public class SetMismatch {
public int[] findErrorNums(int[] nums) {
int n = nums.length;
int[] res = new int[2];
for (int i = 0; i < n; i++) {
int index = Math.abs(nums[i]) - 1;
if (nums[index] < 0) {
res[0] = Math.abs(nums[i]);
} else {
nums[index] *= -1;
}
}
for (int i = 0; i < n; i++) {
// nums[i] 大于 0 则说明没有访问
if (nums[i] > 0) {
res[1] = i + 1;
}
}
return res;
}
}4. 链表
4.1 基本操作
4.1.1 旋转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
对于链表翻转，最常见的翻转方式为迭代。即定义 pre，每次将 cur 指向 pre，之后再将 next 赋值给 cur。
public class ReverseLinkedList {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode node = head;
while (node != null) {
ListNode temp = node.next;
node.next = pre;
pre = node;
node = temp;
}
return pre;
}
}使用递归也是个不错的方式（在写递归代码时，不用刻意带入代码，需要知道函数在递归完成之后会发生什么）。
public class ReverseLinkedList {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}
}翻转链表Ⅱ
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
我们先写一个翻转前 N 个节点的，简而言之就是表示 0，right 范围的翻转。旋转 left，right 可以转化为这个问题。
public class ReverseLinkedList2 {
private ListNode successor = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) {
return reverseN(head, right);
}
// 通过递归，将问题转化为 reverseN 函数
head.next = reverseBetween(head.next, left - 1, right - 1);
return head;
}
public ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 定义 head 的尾部
successor = head.next;
return head;
}
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return last;
}
}K 个一组翻转链表
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
这个思路比较简单，需要考虑的细节比较多，前置条件是要知道翻转链表：
public class ReverseLinkedList {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode node = head;
// 原地翻转，将头节点一个个指向尾部
while (node != null) {
ListNode temp = node.next;
node.next = pre;
pre = node;
node = temp;
}
return pre;
}
}重点在于如何保证翻转之后能连接上原来的链表。
public class ReverseNodesInKGroup {
public ListNode reverseKGroup(ListNode head, int k) {
ListNode res = new ListNode(0);
res.next = head;
ListNode pre = res;
while (head != null) {
ListNode tail = pre;
for (int i = 0; i < k; i++) {
tail = tail.next;
if (tail == null) {
return res.next;
}
}
ListNode next = tail.next;
// 翻转中通过数组返回反转过的 head 和 tail
ListNode[] reverse = swap(head, tail);
head = reverse[0];
tail = reverse[1];
pre.next = head;
tail.next = next;
// 之后重新初始化 pre 和 head
pre = tail;
head = tail.next;
}
return res.next;
}
public ListNode[] swap(ListNode head, ListNode tail) {
ListNode pre = tail.next;
ListNode node = head;
while (pre != tail) {
ListNode next = node.next;
node.next = pre;
pre = node;
node = next;
}
return new ListNode[]{tail, head};
}
}通过递归，可以优化这个代码结构：
public class ReverseNodesInKGroup {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode a, b;
a = b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return head;
}
b = b.next;
}
// 区间 [a,b)
ListNode newHead = reverse(a, b);
// a 已经翻转到链表最后，通过递归，进行剩下链表的翻转
a.next = reverseKGroup(b, k);
return newHead;
}
public ListNode reverse(ListNode a, ListNode b) {
ListNode cur = a;
ListNode pre = null;
while (cur != b) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}4.1.2 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
在数组中可以直接使用双指针进行操作，但是链表中我们无法直接调用对应索引。
第一个思路是参考二叉树（二叉树本身就是特殊的链表），通过后序操作进行判断，从而避免我们显示将链表进行翻转（回文链表 = 原链表 == 翻转原链表）。
public class PalindromeLinkedList {
private ListNode left;
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
public boolean traverse(ListNode right) {
if (right == null) {
return true;
}
// 后序遍历，使用递归栈进行隐式翻转
boolean res = traverse(right.next);
res = res && (left.val == right.val);
left = left.next;
return res;
}
}我们也可以使用快慢指针的思想，在 fast 指针到达之后，slow 指针会接近链表一般位置（如果是奇数不需要判断中间数）。这时只需要翻转 slow 所在链表，并且进行双指针操作即可。
public class PalindromeLinkedList {
public boolean isPalindrome(ListNode head) {
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 如果是奇数，slow 需要多移动一步
if (fast != null) {
slow = slow.next;
}
ListNode left = head, right = reverse(slow);
while (right != null) {
if (left.val != right.val) {
return false;
}
left = left.next;
right = right.next;
}
// 如果纠结链表被破坏，可以再次通过 reverse 重新恢复
return true;
}
public ListNode reverse(ListNode head) {
ListNode cur = head, pre = null;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}4.1.3 删除链表的倒数第 N 个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
最简单的方法可以通过两次遍历实现（第一次返回链表的总长度），力扣的进阶要求我们只扫描一次（只遍历 n 一次）。这里使用技巧和双指针。
倒数第 n 个节点本质就是正数第 size - n + 1 个节点。可以先让一个指针到达 n - 1 的位置，之后让第二个指针跟着第一个指针遍历，就可以到达 siez - n + 1 个节点的位置（这里题目的描述应该再严谨一些）。
public class RemoveNthNodeFromEndOfList {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = new ListNode(0, head);
ListNode point = first;
ListNode target = first;
ListNode pre = first;
for (int i = 0; i < n; i++) {
point = point.next;
}
while (point.next != null) {
point = point.next;
pre = target;
target = target.next;
}
pre.next = target.next;
return first.next;
}
}4.2 合并 K 个排序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6这个题目的前置题目为合并 2 个排序链表，实现代码如下（递归为例）：
public class MergeTwoSortedLists {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}我们可以通过前置直接暴力解除，但是既然已经有两个合并的方法，可以使用分治简化时间复杂度：
class MergeKSortedLists {
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] listNodes, int l, int r) {
if (l == r) {
return listNodes[l];
}
if (l > r) {
return null;
}
int mid = (r - l) / 2 + l;
return mergeTwoLists(merge(listNodes, l, mid), merge(listNodes, mid + 1, r));
}
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if (list1.val < list2.val) {
list1.next = mergeTwoLists(list1.next, list2);
return list1;
} else {
list2.next = mergeTwoLists(list1, list2.next);
return list2;
}
}
}合并 K 个链表，也可以同时对 K 个链表进行操作，即使用 K 个指针进行比对。可以通过优先队列快速实现（需要定义排序规则）。
class Solution {
class Status implements Comparable<Status> {
public int val;
public ListNode node;
public Status(int val, ListNode node) {
this.val = val;
this.node = node;
}
@Override
public int compareTo(Status o) {
return this.val - o.val;
}
}
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<Status> queue = new PriorityQueue<>();
for (ListNode list : lists) {
if (list != null) {
queue.offer(new Status(list.val, list));
}
}
ListNode head = new ListNode(0);
ListNode tail = head;
while (!queue.isEmpty()) {
Status temp = queue.poll();
tail.next = temp.node;
tail = tail.next;
if (temp.node.next != null) {
queue.offer(new Status(temp.node.next.val, temp.node.next));
}
}
return head.next;
}
}4.3 快慢指针
4.3.1 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false。
最容易想到的方法是哈希表存储：
public class LinkedListCycle {
public boolean hasCycle1(ListNode head) {
Set<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.isEmpty() && set.contains(head)) {
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}这里可以用到高中的追及问题，设置一个快慢指针，快指针移动两次，慢指针移动一次。如果存在环，那必然会有相遇的情况。
public class LinkedListCycle {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}后面还有一个进阶题：
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。
不同处在于这里要返回环的节点。
假设快慢指针相遇时，慢指针 slow 走了 k 步，那么快指针 fast 一定走了 2k 步。此时 k 也是圆环的长度。
假设相遇点距环的起点的距离为 m，那么结合上图的 slow 指针，环的起点距头结点 head 的距离为 k - m，也就是说如果从 head 前进 k - m 步就能到达环起点。如果从相遇点继续前进 k - m 步，也恰好到达环起点（因为慢指针）。
这样一解析，代码就呼之欲出了：
public class LinkedListCycle2 {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
// 没有圆环的情况
if (fast == null || fast.next == null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}4.4 相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据保证整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构。
解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 c1。
可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。如果这样进行拼接，就可以让 p1 和 p2 同时进入公共部分，也就是同时到达相交节点 c1。
public class IntersectionOfTwoLinkedLists {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
if (p1 == null) {
p1 = headB;
} else {
p1 = p1.next;
}
if (p2 == null) {
p2 = headA;
} else {
p2 = p2.next;
}
}
return p1;
}
}5. 栈
5.1 单调栈
输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。通过单调栈，我们就可以存储当前距离最近的更大元素。单调栈解决问题模板如下：
int[] nextGreaterElement(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Stack<Integer> s = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
// 比当前高度小直接弹出
while (!s.isEmpty() && s.peek() <= nums[i]) {
s.pop();
}
res[i] = s.isEmpty() ? -1 : s.peek();
s.push(nums[i]);
}
return res;
}5.1.1 下一个更大元素
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
可以直接使用刚刚的模板做出，因题目要求需要额外使用 hash 表存储 nums2 中对应数值的位置。
public class NextGreaterElement {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
int n = nums1.length, m = nums2.length;
int[] res = new int[n];
for (int i = 0; i < m; i++) {
hashMap.put(nums2[i], i);
}
int[] temp = find(nums2);
for (int i = 0; i < n; i++) {
res[i] = temp[hashMap.get(nums1[i])];
}
return res;
}
public int[] find(int[] nums) {
Stack<Integer> stack = new Stack<>();
int n = nums.length;
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
// 去除 stack 中低的数字
while (!stack.isEmpty() && nums[i] >= stack.peek()) {
stack.pop();
}
res[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i]);
}
return res;
}
}给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。题目的难点在于数组为环形数组，可以通过两倍长度进行解决。但不一定真的需要扩充两倍长度，可以在遍历时使用两倍长度解决对应问题。
public class NextGreaterElement2 {
public int[] nextGreaterElements(int[] nums) {
Stack<Integer> stack = new Stack<>();
int n = nums.length;
int[] res = new int[n];
for (int i = 2 * n - 1; i >= 0; i--) {
while (!stack.isEmpty() && nums[i] >= stack.peek()) {
stack.pop();
}
res[i] = stack.isEmpty() ? -1 : stack.peek();
stack.push(nums[i]);
}
return res;
}
}5.1.2 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
同上一个题目思路，直接套用模板即可。
public class DailyTemperatures {
public int[] dailyTemperatures(int[] temperatures) {
Deque<Integer> stack = new LinkedList<>();
int n = temperatures.length;
int[] res = new int[n];
for (int i = n - 1; i >= 0; i--) {
while (!stack.isEmpty() && temperatures[i] >= temperatures[stack.peek()]) {
stack.pop();
}
res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.push(i);
}
return res;
}
}5.1.3 接雨水
给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。 每个雨水的柱子可以类比为一个个括号匹配。通过单调栈思想，存储一个递减的栈，如果下一个柱子比上一个柱子高说明会有雨水。总体的原则就是：
- 当前高度小于等于栈顶高度，入栈，指针后移；
- 当前高度大于栈顶高度，出栈，计算出当前墙和栈顶的墙之间水的多少，然后计算当前的高度和新栈的高度的关系，重复第 2 步。直到当前墙的高度不大于栈顶高度或者栈空，然后把当前墙入栈，指针后移。
public class TrappingRainWater {
public int trap(int[] height) {
int res = 0;
// 单调栈内存储数组索引
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
int h = stack.pop();
if (stack.isEmpty()) {
break;
}
int tmp = stack.peek();
// 按照行来计算，需要减去去除行的高度
res += (i - tmp - 1) * (Math.min(height[i], height[tmp]) - height[h]);
}
stack.push(i);
}
return res;
}
}如果换个思路，按照每个列来求，其实就是左右两边最高的墙最小值 - 正在求的列高度，之后把这些值相加。如果使用暴力，每次都需要遍历，那么可以用动态规划的思想。设置 max_left，记录 i 索引处的左右墙最大值，避免反复遍历。
public class TrappingRainWater {
public int trap(int[] height) {
int res = 0;
int n = height.length;
int[] max_left = new int[n];
int[] max_right = new int[n];
// 要注意是左边右边的墙，不包括本身
for (int i = 1; i < n - 1; i++) {
max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
}
for (int i = 1; i < n - 1; i++) {
int temp = Math.min(max_right[i], max_left[i]) - height[i];
if (temp > 0) {
res += temp;
}
}
return res;
}
}因为定义的状态只会使用一次，所以可以再在空间上进行优化。通过双指针进行处理，这个问题的核心就是左右两边的柱子高度，雨水量也和左右两边较小值决定。
双指针的思路是两边柱子同时进行接水，同样要知道它们左右两边最大值的较小值。假设两柱子分别为 i，j。那么就有 iLeftMax、iRightMax、jLeftMx、jRightMax 这个四个变量。由于 j > i ，故 jLeftMax >= iLeftMax，iRigthMax >= jRightMax。
- 如果 iLeftMax > jRightMax，则必有 jLeftMax >= jRightMax，所有我们能接 j 点的水；
- 如果 jRightMax > iLeftMax，则必有 iRightMax >= iLeftMax，所以我们能接 i 点的水。
最后，我们只需要维护 iLeftMax，jRightMax 两个变量即可。
public class TrappingRainWater {
public int trap(int[] height) {
int res = 0;
int n = height.length;
int left = 0, right = n - 1;
int max_left = 0, max_right = 0;
while (left < right) {
max_left = Math.max(max_left, height[left]);
max_right = Math.max(max_right, height[right]);
if (height[left] < height[right]) {
res += max_left - height[left];
left++;
} else {
res += max_right - height[right];
right--;
}
}
return res;
}
}6. 数学
6.1 数学推导
6.1.1 旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
这样，在循环的时候只需要循环四分之一的位置（每一次原地交换 4 个位置）。
public class RotateImage {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
for (int j = 0; j < (n + 1) / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][i];
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
matrix[j][n - i - 1] = temp;
}
}
}
}public class RotateImage {
public void rotate(int[][] matrix) {
int n = matrix.length;
// 水平翻转
for (int i = 0; i < n / 2; ++i) {
for (int j = 0; j < n; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - i - 1][j];
matrix[n - i - 1][j] = temp;
}
}
// 主对角线翻转
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
}6.1.2 扁平化嵌套列表迭代器
给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。
实现扁平迭代器类 NestedIterator ：
NestedIterator(List<NestedInteger> nestedList)用嵌套列表 nestedList 初始化迭代器；- int next() 返回嵌套列表的下一个整数；
- boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。
public interface NestedInteger {
boolean isInteger();
Integer getInteger();
List<NestedInteger> getList();
}输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。题目要求我们不应该对接口进行推导，但是根据推导，我们才可以确认数据结构的样子。通过推导出可以发现整个数据结构类似一颗 N 叉树。
public class NestedInteger {
private Integer val;
private List<NestedInteger> list;
public NestedInteger(Integer val) {
this.val = val;
this.list = null;
}
public NestedInteger(List<NestedInteger> list) {
this.list = list;
this.val = null;
}
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger() {
return val != null;
}
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger() {
return this.val;
}
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList() {
return this.list;
}
}
比较简单的方法即利用一个 List 存储 N 叉树的遍历结果，iterator 采用 List 的 iterator。这样的问题也很明显，在初始化的时候就已经将所有的数据加载到 List 中了，这不满足迭代器惰性的特性（接口中定义的方法也没能完全使用）。
class NestedIterator implements Iterator<Integer> {
private final Iterator<Integer> it;
public NestedIterator1(List<NestedInteger> nestedList) {
List<Integer> result = new LinkedList<>();
for (NestedInteger node : nestedList) {
traverse(node, result);
}
this.it = result.iterator();
}
@Override
public Integer next() {
return it.next();
}
@Override
public boolean hasNext() {
return it.hasNext();
}
public void traverse(NestedInteger root, List<Integer> result) {
if (root.isInteger()) {
result.add(root.getInteger());
return;
}
for (NestedInteger list : root.getList()) {
traverse(list, result);
}
}
}正确的做法是利用 LinkedList，在迭代器遍历遇到列表时，将列表展开。这里要注意展开的时候必须要添加到链表的头部（尾部可能还有数据，不能打乱相对顺序）。
public class NestedIterator implements Iterator<Integer> {
private final LinkedList<NestedInteger> list;
public NestedIterator(List<NestedInteger> nestedList) {
list = new LinkedList<>(nestedList);
}
@Override
public Integer next() {
return list.remove(0).getInteger();
}
@Override
public boolean hasNext() {
while (!list.isEmpty() && !list.get(0).isInteger()) {
List<NestedInteger> first = list.remove(0).getList();
// 因为链表中已经有其他值，所有要添加在表头保持相对顺序
for (int i = first.size() - 1; i >= 0; i--) {
list.addFirst(first.get(i));
}
}
return !list.isEmpty();
}
}6.2 位运算
// 利用或操作 | 和空格将英文字符转换为小写
('a' | ' ') = 'a'
('A' | ' ') = 'a'
// 利用与操作 & 和下划线将英文字符转换为大写
('b' & '_') = 'B'
('B' & '_') = 'B'
// 利用异或操作 ^ 和空格进行英文字符大小写互换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
// 不用临时变量交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b;
// 判断两个数是否异号
int x = -1, y = 2;
boolean f = ((x ^ y) < 0); // true
int x = 3, y = 2;
boolean f = ((x ^ y) < 0); // false针对环形数组，可以通过 index % length 的方式进行环状遍历。index & (arr.length - 1) 可以以更加高效的方式执行，并且不存在负数问题。
6.2.1 n & (n - 1)
n & (n-1) 这个操作在算法中比较常见，作用是消除数字 n 的二进制表示中的最后一个 1。
位1的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的；
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。
public class NumberOf1Bits {
public int hammingWeight(int n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
}2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。
如果是 2 的幂，转化为二进制就是只有最高位为 1。
public class PowerOfTwo {
public boolean isPowerOfTwo(int n) {
if (n <= 0) {
return false;
}
return (n & (n - 1)) == 0;
}
}6.2.2 a ^ a = 0
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
因为 a ^ a = 0，对数组遍历后，只会剩下单独的元素，a ^ 0 = a。
public class SingleNumber {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}丢失的数字
给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
数组长度为 n，给出的数据范围为 0……n + 1。可以将索引和数字取异或，剩下的数字即缺失的数字。
public class MissingNumber {
public int missingNumber(int[] nums) {
int n = nums.length;
int res = 0;
res ^= n;
for (int i = 0; i < n; i++) {
res ^= i ^ nums[i];
}
return res;
}
}6.3 阶乘
6.3.1 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1。
出现 0 的情况必定存在参数 5。要注意 25 可以提供两个 0。所以直接做 n / 5 的运算，得出所有 5 的倍数。
public class FactorialTrailingZeroes {
public int trailingZeroes(int n) {
int res = 0;
while(n > 0) {
res += n / 5;
n /= 5;
}
return res;
}
}6.3.2 阶乘函数后 K 个零
f(x) 是 x! 末尾是 0 的数量。回想一下 x! = 1 2 3 … x，且 0! = 1 。
例如， f(3) = 0 ，因为 3! = 6 的末尾没有 0 ；而 f(11) = 2 ，因为 11!= 39916800 末端有 2 个 0 。给定 k，找出返回能满足 f(x) = k 的非负整数 x 的数量。
本题可以类比之前的二分搜索的题目，设 f(x)，自变量 x 为 0 的个数，f(x) 为满足的所有数字个数（注意这里是 <= k）。列出一个单调递增的函数（数字越大，0 数量越多）。因为要找到所有的 x 数量，所以要求为右界。
public class PreimageSizeOfFactorialZeroesFunction {
public int preimageSizeFZF(int k) {
if (k <= 1) {
return 5;
}
return f(k) - f(k - 1);
}
public int f(int x) {
long l = 0, r = (long) 1e10;
while (l <= r) {
long mid = (r - l) / 2 + l;
if (trailingZeroes(mid) <= x) {
l = mid + 1;
} else {
r = mid - 1;
}
}
return (int) l - 1;
}
public long trailingZeroes(long x) {
long count = 0;
while (x != 0) {
count += x / 5;
x /= 5;
}
return count;
}
}6.4 素数
6.4.1 计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
素数筛选法，先假设范围内所有的数字都是素数，之后将所有素数的倍数都标记为非素数。由于因子的对称性，其中的 for 循环只需要遍历 [2,sqrt(n)] 就够了。
public class CountPrimes {
public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
Arrays.fill(isPrime, true);
// sqrt(n) 后面的数 如果不是素数 则已经被标记为了 false, 如果是素数则默认就是 true
// 所以外层循环不用遍历到 n 只用遍历到 sqrt(n)
for (int i = 2; i < Math.sqrt(n); i++) {
if (isPrime[i]) {
// 从 i * i 开始，前面已经被标记过
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) {
count++;
}
}
return count;
}
}6.5 模幂运算
6.5.1 Pow(x, n)
实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，x^n ）。
最简单的实现方法就是遍历，但是题目给出的底数很小，指数很大，直接遍历肯定会超时。通过位运算将算法进行优化。比如 10 = 2 ^ 3 + 2。将指数拆分为 2 的米相加。
public class PowXN {
public double myPow(double x, int n) {
double res = 1;
if (x == 0.0f) {
return 0.0d;
}
// 使用 long 防止越界
long b = n;
if (b < 0) {
x = 1 / x;
b = -b;
}
while (b > 0) {
if ((b & 1) == 1) {
res *= x;
}
x *= x;
b >>= 1;
}
return res;
}
}6.5.2 超级次方
你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
(a * b) % k = (a % k) * (b % k) % k。在修改后的 myPow 方法中使用，防止结果溢出。
public class SuperPow {
private final int base = 1337;
public int superPow(int a, int[] b) {
return superPow(a, b, b.length - 1);
}
public int superPow(int a, int[] b, int i) {
if (i < 0) {
return 1;
}
return (myPow(a, b[i]) *
myPow(superPow(a, b, i - 1), 10)
) % base;
}
// myPow 递归使用
public int myPow(int a, int k) {
if (k == 0) {
return 1;
}
// 对因子取模，保证 a * myPow(a, k - 1) 不会溢出
a %= base;
if (k % 2 == 1) {
return (a * myPow(a, k - 1)) % base;
}
int sub = myPow(a, k / 2);
return (sub * sub) % base;
}
}7. 动态规划
动态规划问题的一般形式就是求最值。求解动态规划的核心问题是穷举。只有列出正确的「状态转移方程」，才能正确地穷举。而且，需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
通过递归自顶向上/通过线性表达式自底向上。
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
7.0 动规思想
7.0.1 最优子结构
最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质。动态规划的本质还是从 base case 不断向后推导，之后明确状态公式。判断重叠子问题，最简单粗暴的方式就是画图，把递归树画出来，看看有没有重复的节点。之后针对重复节点使用备忘录进行保存（针对复杂的动态规划，可以通过只抽象出递归观察是否存在重复节点）。
通过状态公式，观察 dp table 按照何方向进行遍历。
7.0.2 base case
以力扣 931.下降路径最小和 为例。
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
分析可知对于 matrix[i][j]，只有可能从 matrix[i-1][j], matrix[i-1][j-1], matrix[i-1][j+1] 这三个位置转移过来。关键是在于如何处理越界之后的值。base 即 i == 0 时的值。题目中的数值最大为 10000，所以用一个较大值规避越界情况。
public class MinimumFallingPathSum {
private int[][] memo;
public int minFallingPathSum(int[][] matrix) {
int res = Integer.MAX_VALUE;
int n = matrix.length;
memo = new int[n][n];
for (int[] m : memo) {
Arrays.fill(m, -1);
}
for (int i = 0; i < n; i++) {
res = Math.min(res, dp(matrix, n - 1, i));
}
return res;
}
public int dp(int[][] matrix, int i, int j) {
int n = matrix.length;
if (i < 0 || j < 0 || i >= n || j >= n) {
// 应用特殊值进行排除越界情况，大于 matrix 最大值
return 99999;
}
if (i == 0) {
return matrix[0][j];
}
if (memo[i][j] != -1) {
return memo[i][j];
}
memo[i][j] = matrix[i][j] +
Math.min(dp(matrix, i - 1, j),
Math.min(dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1)));
return memo[i][j];
}
}7.0.3 简化空间
如果计算状态 dp[i][j] 需要的都是 dp[i][j] 相邻的状态，那么就可以使用空间压缩技巧，将二维的 dp 数组转化成一维，将空间复杂度从 O(N^2) 降低到 O(N)。
给出一段示例代码：
for (int i = n - 2; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
// 状态转移方程
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}对 dp[i][j] 的更新，其实只依赖于 dp[i+1][j-1], dp[i][j-1], dp[i+1][j] 这三个状态。空间压缩的核心思路就是，将二维数组「投影」到一维数组。想把二维 dp 数组压缩成一维，一般来说是把第一个维度，也就是 i 这个维度去掉，只剩下 j 这个维度。
分析中可以得知，在更新一维 dp 数组的时候，dp[i+1][j-1] 会被 dp[i][j-1] 覆盖掉。所以在压缩为一维数组时，应该用变量将 dp[i + 1][j - 1] 保存下来。
for (int i = n - 2; i >= 0; i--) {
// 存储 dp[i+1][j-1] 的变量
int pre = 0;
for (int j = i + 1; j < n; j++) {
int temp = dp[j];
if (s[i] == s[j])
// dp[i][j] = dp[i+1][j-1] + 2;
dp[j] = pre + 2;
else
dp[j] = max(dp[j], dp[j - 1]);
// 到下一轮循环，pre 就是 dp[i+1][j-1] 了
pre = temp;
}
}针对动态规划的方式简化空间需要建立在 dp table 的基础上（将递归转化为迭代）。
7.1 子问题
7.1.1 最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
这个题目有很多想法都可以在这里，第一个是基于贪心想法滑动窗口思想。nums 中有正有负，这种情况下元素和最大的那个子数组一定是以正数开头的（以负数开头的话，把这个负数去掉，就可以得到和更大的子数组了，与假设相矛盾）。那么此时我们需要穷举所有以正数开头的子数组，计算他们的元素和，找到元素和最大的那个子数组。
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int left = 0, right = 0;
int temp = 0;
int res = Integer.MIN_VALUE;
for (right = 0; right < nums.length; right++) {
temp += nums[right];
res = Math.max(res, temp);
// 如果窗口的和为负数就缩小窗口，否则就扩张窗口
while (left <= right && temp < 0) {
temp -= nums[left];
left++;
}
}
return res;
}
}之后就是动态规划，首先需要考虑 dp 方程为何。因为是最大子数组，可以将 dp[i] 的值设为以 num[i] 结尾的子数组最大和，这样状态转移公式就可以写成 dp[i] = Math.max(num[i], num[i] + dp[i - 1])。
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
int[] dp = new int[n];
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < n; i++) {
dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
res = Math.max(res, dp[i]);
}
return res;
}
}
// 代码简化版本
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int pre = 0, res = nums[0];
for (int num : nums) {
pre = Math.max(pre + num, num);
res = Math.max(res, pre);
}
return res;
}
}通过状态转移方程推导以 nums[i] 结尾的最大子数组和，前缀和思想也能通过。preSum[i+1] - preSum[j] 其实就是子数组 nums[j..i] 之和。以 nums[i] 为结尾的最大子数组之和是多少？其实就是 preSum[i+1] - min(preSum[0..i])。
public class MaximumSubarray {
public int maxSubArray(int[] nums) {
int n = nums.length;
// nums[0] 不存在
int[] preSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
int res = Integer.MIN_VALUE;
int minVal = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
minVal = Math.min(minVal, preSum[i]);
res = Math.max(res, preSum[i + 1] - minVal);
}
return res;
}
}7.1.2 子序列
递增子序列
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
这个题目最简单的想法是使用 dp[i] 表示以 i 结尾的子数组的最长序列。
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int res = Integer.MIN_VALUE;
for (int i : dp) {
res = Math.max(res, i);
}
return res;
}
}力扣要求我们写出 O(Nlogn) 时间复杂度的算法，说明需要使用二分优化算法。
将状态定义为 tail，表示长度为 i + 1 的子序列尾部元素的值。不断遍历，保证尾部数字最小（尾部数字越小，越有可能性长度增大）。在更新尾部数字的同时，就可以使用二分查找。
public class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
int[] tails = new int[nums.length];
int res = 0;
for (int num : nums) {
int i = 0, j = res - 1;
// 利用二分查找找到左界
while (i <= j) {
int mid = (j - i) / 2 + i;
if (tails[mid] < num) {
i = mid + 1;
} else {
j = mid - 1;
}
}
tails[i] = num;
if (i == res) {
res++;
}
}
return res;
}
}整个过程可以用 Windows 中的纸牌游戏形容：
俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
这个二维问题可以通过排序转化为一维的最长递增子序列。
首先，对宽度 w 从小到大排序，确保了 w 这个维度可以互相嵌套，所以我们只需要专注高度 h 这个维度能够互相嵌套即可。其次，两个 w 相同的信封不能相互包含，所以对于宽度 w 相同的信封，对高度 h 进行降序排序，保证 LIS 中不存在多个 w 相同的信封（因为题目说了长宽相同也无法嵌套）。
public class RussianDollEnvelopes {
public int maxEnvelopes(int[][] envelopes) {
int n = envelopes.length;
Arrays.sort(
envelopes,
(o1, o2) -> o1[0] == o2[0] ?
o2[1] - o1[1] : o1[0] - o2[0]
);
int[] nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = envelopes[i][1];
}
int res = 0;
int[] tail = new int[n];
for (int num : nums) {
int left = 0, right = res - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
if (tail[mid] < num) {
left = mid + 1;
} else {
right = mid - 1;
}
}
tail[left] = num;
if (left == res) {
res++;
}
}
return tail[res];
}
}公共子序列
最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
- 例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
同编辑距离问题，使用指针进行移动。
// 使用 dp table 优化
public class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
public class LongestCommonSubsequence {
private int[][] memo;
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(text1, text2, 0, 0);
}
public int dp(String s1, String s2, int i, int j) {
if (i == s1.length() || j == s2.length()) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, s2, i + 1, j + 1) + 1;
} else {
// 移动 s1/s2，寻找相同字符
memo[i][j] = Math.max(
dp(s1, s2, i + 1, j),
dp(s1, s2, i, j + 1)
);
}
return memo[i][j];
}
}两个字符串的删除操作
给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的最小步数。每步 可以删除任意一个字符串中的一个字符。
输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ，第二步将 "eat "变为 "ea"题目本身可以转化为求最长公共子序列，因为最小删除的结果一定是最大公共子序列。
public class DeleteOperationForTwoStrings {
private int[][] memo;
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
int lcs = dp(word1, word2, 0, 0);
return m - lcs + n - lcs;
}
public int dp(String s1, String s2, int i, int j) {
if (i == s1.length() || j == s2.length()) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, s2, i + 1, j + 1) + 1;
} else {
memo[i][j] = Math.max(
dp(s1, s2, i + 1, j),
dp(s1, s2, i, j + 1)
);
}
return memo[i][j];
}
}两个字符串的最小 ASCⅡ 删除和
给定两个字符串s1 和 s2，返回 使两个字符串相等所需删除字符的 ASCII 值的最小和 。
将最长公共子序列的内容稍微改变即可，要注意 base case。
public class MinimumASCIIDeleteSumForTwoStrings {
private int[][] memo;
public int minimumDeleteSum(String s1, String s2) {
int m = s1.length(), n = s2.length();
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(s1, s2, 0, 0);
}
public int dp(String s1, String s2, int i, int j) {
int res = 0;
int m = s1.length(), n = s2.length();
// 注意 base case，任意结束都需要遍历其他结果
if (i == m) {
while (j < n) {
res += s2.charAt(j++);
}
return res;
}
if (j == n) {
while (i < m) {
res += s1.charAt(i++);
}
return res;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s1.charAt(i) == s2.charAt(j)) {
memo[i][j] = dp(s1, s2, i + 1, j + 1);
} else {
// 删除 s1/s2 的某个字符
memo[i][j] = Math.min(
dp(s1, s2, i + 1, j) + s1.charAt(i),
dp(s1, s2, i, j + 1) + s2.charAt(j)
);
}
return memo[i][j];
}
}7.1.3 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
题目的核心思路在于，如果 aba 是回文串，那么 xabax 也是回文串。即在保证中心为回文串的同时向周围扩散查找。
比较容易想到的做法是动态规划：
我们则设置一个二维数组 dp[i][j] 用于表示 i…j 是否为回文串。
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
int n = s.length();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp 表示 i...j 是否为回文子串
boolean[][] dp = new boolean[n][n];
// 所有单个字符都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
// 返回回文子串的长度
for (int L = 2; L <= n; L++) {
// 从左边界开始遍历
for (int l = 0, r = L - 1; r < n && l < n; l++, r = l + L - 1) {
if (charArray[l] != charArray[r]) {
dp[l][r] = false;
} else {
// 判断回文串的长度
if (r - l + 1 < 4) {
dp[l][r] = true;
} else {
dp[l][r] = dp[l + 1][r - 1];
}
}
if (dp[l][r] && r - l + 1 > maxLen) {
maxLen = r - l + 1;
begin = l;
}
}
}
return s.substring(begin, begin + maxLen);
}
}这里使用了 O(n^2) 的空间消耗，通过刚才的推断，我们可以简化空间消耗。本质上我们是确定中心，之后向两边扩散。并且中心存在奇偶区别。
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
// 奇数长度中心扩散
String s1 = palindrome(s, i, i);
// 偶数长度中心扩散
String s2 = palindrome(s, i, i + 1);
res = res.length() > s1.length()? res : s1;
res = res.length() > s2.length()? res : s2;
}
return res;
}
public String palindrome(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
return s.substring(l + 1, r);
}
}7.2 路径问题
7.2.1 不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
很经典的动态规划题，因为机器人只能进行右和下的移动，所以很容易得出状态转移方程为 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp 表示所在格子到达的方式。
public class UniquePaths {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// 记得初始化
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 && j == 0) {
continue;
}
if (i == 0) {
dp[i][j] += dp[i][j - 1];
} else if (j == 0) {
dp[i][j] += dp[i - 1][j];
} else {
dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。障碍物只需要略过即可，因为 dp[i][j] 已经设为 0。
public class UniquePaths2 {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = 1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 可能出现起点为障碍的情况
if (obstacleGrid[i][j] == 1) {
dp[i][j] = 0;
continue;
}
if (i == 0 && j == 0) {
continue;
}
if (i == 0) {
dp[i][j] += dp[i][j - 1];
} else if (j == 0) {
dp[i][j] += dp[i - 1][j];
} else {
dp[i][j] += dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}7.2.2 最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。题目和机器人走格子同理。
public class MinimumPathSum {
public int minPathSum(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = grid[i][j];
if (i == 0 && j == 0) {
continue;
}
if (i == 0) {
dp[i][j] += dp[i][j - 1];
} else if (j == 0) {
dp[i][j] += dp[i - 1][j];
} else {
dp[i][j] += Math.min(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[m - 1][n - 1];
}
}7.2.3 三角形最小路径和
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
本质上，将三角形变形之后：
2
3 4
6 5 7
4 1 8 3这个题目解题方法非常好想，但是现在力扣要求我们通过使用 O(n) 的空间复杂度完成这个问题。因为本质上都是使用数组进行相加，二维的 dp 数组可以压缩为一维。
所以 dp[i] = Math.min(dp[i], dp[i - 1]) + list.get(i).get(j)。但是我们不能进行正序遍历，因为这样会改变 dp 的值，导致之后结果不对，所以我们需要倒序遍历，这样只会修改 dp[i]，而不会修改 dp[i - 1]。
public class Triangle {
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
int[] dp = new int[n];
dp[0] = triangle.get(0).get(0);
for (int i = 1; i < n; i++) {
// 当前层尾节点
dp[i] = dp[i - 1] + triangle.get(i).get(i);
// 倒序遍历，防止 dp 修改问题
for (int j = i - 1; j > 0; j--) {
dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j);
}
dp[0] += triangle.get(i).get(0);
}
int res = dp[0];
for (int i = 1; i < dp.length; i++) {
res = Math.min(dp[i], res);
}
return res;
}
}7.2.4 地下城游戏
一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。
| -2 (K) | -3 | 3 |
|---|---|---|
| -5 | -10 | 1 |
| 10 | 30 | -5 (P) |
说明:
- 骑士的健康点数没有上限。
- 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
题目简化为一个二维矩阵，从左上角到达右下角，算出最小的初始值。但是这不是简单的最短路径，因为本题并不是“无后效性”的题目。在向下递归的过程中，怪物（负数）会影响初始值（血量）的选择。之后的状态会影响之前的状态。
某些情况下，子问题对于整个问题的影响，可以归纳到一个比“所有子问题解法”的空间小得多的“子问题状态”空间中，只要子问题解决后的状态处于某个状态，它对于整个问题的影响就是一致的，这样如果已知子问题处于某个状态，我们就可以求出这个状态条件下子问题的最优解，当全局最优且这个子问题取这个状态时，子问题本身的解法一定是我们刚刚求出的最优解。
这样我们只需要对每个子问题的每个状态计算最优解，然后通过这些最优解的递推关系就可以求出整个问题的最优解。这种子问题对主问题的影响可以总结为少数“状态”的特性就叫做无后效性，意味着只要状态一致，具体经过怎样的步骤到达这一状态是没有影响的。
public class DungeonGame {
private int[][] memo;
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(dungeon, 0, 0);
}
public int dp(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
if (i == m || j == n) {
return Integer.MAX_VALUE;
}
if (i == m - 1 && j == n - 1) {
return grid[i][j] >= 0 ? 1 : -grid[i][j] + 1;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
// res 至少为 1
int res = Math.min(dp(grid, i + 1, j),
dp(grid, i, j + 1)) - grid[i][j];
memo[i][j] = res <= 0 ? 1 : res;
return memo[i][j];
}
}针对于这种情况，可以将题目反方向进行遍历，从右下达到左上。设置 dp[i][j] 为当前位置到达结尾的最小初始值。
public class DungeonGame {
private int[][] memo;
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length, n = dungeon[0].length;
int[][] dp = new int[m + 1][n + 1];
for (int[] row : dp) {
Arrays.fill(row, Integer.MAX_VALUE);
}
// 初始的转移值为无效值，dp[m - 1][n - 1]，对无效值设为 1
dp[m][n - 1] = dp[m - 1][n] = 1;
for (int i = m - 1; i >= 0; i--) {
for (int j = n - 1; j >= 0; j--) {
// 防止出现fu'shu
dp[i][j] = Math.max(
Math.min(dp[i + 1][j], dp[i][j + 1])
- dungeon[i][j],
1);
}
}
return dp[0][0];
}
}7.3 背包问题
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for ...
dp[状态1][状态2][...] = 计算(选择1，选择2...)
int knapsack(int W, int N, int[] wt, int[] val) {
assert N == wt.length;
// base case 已初始化
int[][] dp = new int[N + 1][W + 1];
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i - 1] < 0) {
// 这种情况下只能选择不装入背包
dp[i][w] = dp[i - 1][w];
} else {
// 装入或者不装入背包，择优
dp[i][w] = Math.max(
dp[i - 1][w - wt[i-1]] + val[i-1],
dp[i - 1][w]
);
}
}
}
return dp[N][W];
}
// 可以通过降维进行不断优化
int knapsack(int W, int N, int[] wt, int[] val) {
assert N == wt.length;
// base case 已初始化
int[] dp = new int[W + 1];
for (int i = 1; i <= N; i++) {
for (int w = 1; w <= W; w++) {
if (w - wt[i - 1] >= 0) {
dp[w] = Math.max(
dp[w - wt[i-1]] + val[i-1],
dp[w]
);
}
}
}
return dp[N][W];
}7.3.1 0/1 背包 & 完全背包
零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
使用动态规划思想，将问题分解为其他 i - coin 的小问题，下面是递归做法：
public class CoinChange {
public int coinChange(int[] coins, int amount) {
// 定义 memo 作为备忘录
int[] memo = new int[amount + 1];
Arrays.fill(memo, -2);
memo[0] = 0;
return dp(coins, amount, memo);
}
public int dp(int[] coins, int amount, int[] memo) {
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
// 如果已经存储，直接返回
if (memo[amount] != -2) {
return memo[amount];
}
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int subProblem = dp(coins, amount - coin, memo);
if (subProblem != -1) {
res = Math.min(res, subProblem + 1);
}
}
memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
return memo[amount];
}
}定义 dp[i] 为钱为 i 时需要的零钱数量，之后写出状态转移方程为 dp[i] = min(dp[i], dp[i - coin] + 1)。
public class CoinChange {
public int coinChange1(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 防止越界情况
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0。
之后的换零钱Ⅱ是一个完全背包问题，因为我们背包数量无限，不需要考虑放入或者不放入的情况，可以直接相加。
通过背包标准模板的写法：
public class CoinChange2 {
public int change(int amount, int[] coins) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int i = 0; i <= n; i++) {
dp[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= amount; j++) {
if (j - coins[i - 1] >= 0) {
dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][amount];
}
}通过优化，将 dp 压缩成一维数组。因为题目要求我们求出所有的可能性情况，coin 可以随意使用。
public class CoinChange2 {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
}7.3.2 子集背包
给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
分割成两个相同和的子集，只需要计算是否有和相加为 sum / 2，另一半自然也为 sum / 2（需要保证和不为奇数）。dp 方程为 dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]]。
public class PartitionEqualSubsetSum {
public boolean canPartition(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum /= 2;
boolean[] dp = new boolean[sum + 1];
dp[0] = true;
for (int num : nums) {
for (int j = sum; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[sum];
}
}7.4 股票买卖问题
这个题目从Ⅰ~Ⅳ体现了一般到特殊的推导过程，还有两个变种形态。
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
dp[i][k][0] = Math.max(dp[i - 1][k][0], d[i - 1][k][1] + price[i]);
// 保持不变 / 今日将昨日股票卖出
dp[i][k][1] = Math.min(dp[i - 1][k][1], dp[i - 1][k - 1][0] - price[i]);
// 保持不变 / 今日买一份股票方程如下（因为 k - 1 只跟 i - 1 关联，所以可以在 for 中使用循环）：
public class BestTimeToBuyAndSellStock4 {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][k + 1][2];
for (int i = 0; i < n; i++) {
for (int j = k; j >= 1; j--) {
if (i == 0) {
dp[i][j][1] = -prices[i];
continue;
}
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[n - 1][k][0];
}
}7.4.1 一般到特殊
第一题只需要购买一次（通过贪心也可以做出），所以 k 不再成为约束（k = 1），状态方程转化为：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])// 动态规划，空间优化
public class BestTimeToBuyAndSellStock {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int price : prices) {
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price);
dp_i_1 = Math.max(dp_i_1, -price);
}
return dp_i_0;
}
}
// 贪心，找出最小 price
public class BestTimeToBuyAndSellStock {
public int maxProfit(int[] prices) {
int res = 0;
int n = prices.length;
int min_price = prices[0];
for (int i = 1; i < n; i++) {
if (min_price > prices[i]) {
min_price = prices[i];
} else {
res = Math.max(res, prices[i] - min_price);
}
}
return res;
}
}第二题我们可以无限次购买，所以可以认为 k == k - 1。状态转移方程为：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])// 优化空间
public class BestTimeToBuyAndSellStock2 {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
for (int price : prices) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price);
dp_i_1 = Math.max(dp_i_1, temp - price);
}
return dp_i_0;
}
}
// 标准状态机方程
public class BestTimeToBuyAndSellStock2 {
public int maxProfit1(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][2];
dp[0][1] = -prices[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}
}第三题限制 k = 2，状态方程类似第四题。
public class BestTimeToBuyAndSellStock4 {
public int maxProfit(int k, int[] prices) {
int n = prices.length;
int[][][] dp = new int[n][k + 1][2];
for (int i = 0; i < n; i++) {
for (int j = k; j >= 1; j--) {
if (i == 0) {
dp[i][j][1] = -prices[i];
continue;
}
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[n - 1][k][0];
}
}
// k = 2，进行两次交易，压缩空间简化动态规划
public class BestTimeToBuyAndSellStock3 {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp_1_0 = 0, dp_1_1 = Integer.MIN_VALUE;
int dp_2_0 = 0, dp_2_1 = Integer.MIN_VALUE;
for (int price : prices) {
dp_2_0 = Math.max(dp_2_0, dp_2_1 + price);
dp_2_1 = Math.max(dp_2_1, dp_1_0 - price);
dp_1_0 = Math.max(dp_1_0, dp_1_1 + price);
dp_1_1 = Math.max(dp_1_1, -price);
}
return dp_2_0;
}
}7.4.2 变种题
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
题目的变种为不能连续购买股票，卖出之后需要等待一天。
public class BestTimeToBuyAndSellStockWithCoolDown {
public int maxProfit(int[] prices) {
int n = prices.length;
int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
// 表示 dp[i - 2][0]
int dp_pre_0 = 0;
for (int price : prices) {
int temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + price);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - price);
dp_pre_0 = temp;
}
return dp_i_0;
}
}7.5 打家劫舍问题
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
题目的本质就是在数组内寻找最大和，并且需要隔一个索引。
// 递归解法
public class HouseRobber {
public int rob(int[] nums) {
int n = nums.length;
int[] memo = new int[n];
Arrays.fill(memo, -1);
return dp(memo, 0, nums);
}
public int dp(int[] memo, int start, int[] nums) {
if (start >= memo.length) {
return 0;
}
if (memo[start] != -1) {
return memo[start];
}
int res = Math.max(
dp(memo, start + 1, nums),
dp(memo, start + 2, nums) + nums[start]
);
memo[start] = res;
return res;
}
}
// 空间消耗优化动态规划
public class HouseRobber {
public int rob2(int[] nums) {
int n = nums.length;
int dp_i = 0;
int dp_i_1 = 0, dp_i_2 = 0;
for (int i = n - 1; i >= 0; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
}7.5.1 打家劫舍Ⅱ
问题变成了一个环，简化来说就说不能同时抢首或者尾，那么只需要进行两次计算取最大值即可。
public class HouseRobber2 {
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) {
return nums[0];
}
return Math.max(robArrange(nums, 0, n - 2),
robArrange(nums, 1, n - 1));
}
public int robArrange(int[] nums, int start, int end) {
int dp_i = 0;
int dp_i_1 = 0, dp_i_2 = 0;
for (int i = end; i >= start; i--) {
dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
dp_i_2 = dp_i_1;
dp_i_1 = dp_i;
}
return dp_i;
}
}7.5.2 打家劫舍Ⅲ
此时的数组变成了二叉树，其他条件不变。
// 一般的动态规划，状态机需要使用 HashMap 进行存储
public class HouseRobber3 {
private final HashMap<TreeNode, Integer> hashMap = new HashMap<>();
public int rob(TreeNode root) {
if (root == null) {
return 0;
}
if (hashMap.containsKey(root)) {
return hashMap.get(root);
}
// 这家抢，需要忽略下家
int dp_1 = root.val
+ (root.left == null ? 0 : rob(root.left.left) + rob(root.left.right))
+ (root.right == null ? 0 : rob(root.right.left) + rob(root.right.right));
int dp_2 = rob(root.left) + rob(root.right);
int res = Math.max(dp_1, dp_2);
hashMap.put(root, res);
return res;
}
}
// 通过应用子树思想，可以把状态机进行简化
public class HouseRobber3 {
public int rob(TreeNode root) {
int[] res = dp(root);
return Math.max(res[0], res[1]);
}
public int[] dp(TreeNode root) {
if (root == null) {
return new int[]{0, 0};
}
// 数组 0 表示不抢，1 表示抢
int[] left = dp(root.left);
int[] right = dp(root.right);
// 这家抢，下家不抢
int not_rob = Math.max(left[0], left[1])
+ Math.max(right[0], right[1]);
int rob = root.val + left[0] + right[0];
return new int[]{not_rob, rob};
}
}7.6 贪心
贪心算法可以认为是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。
每一步都做出一个局部最优的选择，最终的结果就是全局最优。注意，这是一种特殊性质，只有一部分问题拥有这个性质。
7.6.1 区间调度问题
区间问题基本都是对区间进行排序，通过排序之后结果结合贪心想法进行运算。
无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
题目转化一下就是要求重叠区间的数量，可以在转化为求不重叠区间的数量（重叠区间 = 总 - 不重叠区间）。先对题目中的区间对 end 进行排序，不难发现所有与 x 相交的区间必然会与 x 的 end 相交；如果一个区间不想与 x 的 end 相交，它的 start 必须要大于（或等于）x 的 end。
public class NonOverlappingIntervals {
public int eraseOverlapIntervals(int[][] intervals) {
int n = intervals.length;
Arrays.sort(intervals,
Comparator.comparingInt((int[] a) -> a[1])
);
int count = 1;
int x_end = intervals[0][1];
for (int[] interval : intervals) {
int start = interval[0];
if (start >= x_end) {
count++;
x_end = interval[1];
}
}
return n - count;
}
}用最少的箭头射爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：气球可以用2支箭来爆破:
- 在x = 2处发射箭，击破气球[1,2]和[2,3]。
- 在x = 4处射出箭，击破气球[3,4]和[4,5]。同理上一题，但是如果边界值相同也可以算作重叠区间，稍微修改条件即可。
public class MinimumNumberOfArrowsToBurstBalloons {
public int findMinArrowShots(int[][] points) {
int n = points.length;
Arrays.sort(points,
Comparator.comparingInt((int[] a) -> a[1])
);
int count = 1;
int x_end = points[0][1];
for (int[] point : points) {
int start = point[0];
if (start > x_end) {
count++;
x_end = point[1];
}
}
return n - count;
}
}7.6.2 区间覆盖问题
跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
这道题目可以用动规做，但是本质可以用贪心优化。题目的要求可以简化为是否可以到达最后，即求出可以向右跳的最远距离。
public class JumpGame {
public boolean canJump(int[] nums) {
int n = nums.length;
int farthest = 0;
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(farthest, nums[i] + i);
// 防止出现无法到达的情况
if (farthest <= i) {
return false;
}
}
return farthest >= n - 1;
}
}给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
- 0 <= j <= nums[i]；
- i + j < n。
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
public class JumpGame2 {
public int jump(int[] nums) {
int n = nums.length;
int end = 0, farthest = 0;
int count = 0;
// 注意遍历到 n - 1，因为最开始已经做了 count + 1
for (int i = 0; i < n - 1; i++) {
farthest = Math.max(nums[i] + i, farthest);
// 触碰到边界之后将 end 更新到当前最远处
if (end == i) {
count++;
end = farthest;
}
}
return count;
}
}视频拼接
你将会获得一系列视频片段，这些片段来自于一项持续时长为 time 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
使用数组 clips 描述所有的视频片段，其中 clips[i] = [starti, endi] 表示：某个视频片段开始于 starti 并于 endi 结束。
甚至可以对这些片段自由地再剪辑：
- 例如，片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, time]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
输出：3
解释：
选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在手上的片段为 [0,2] + [2,8] + [8,10]，而这些覆盖了整场比赛 [0, 10]。给定一个目标区间和若干小区间，如何通过裁剪和组合小区间拼凑出目标区间？最少需要几个小区间？
按照起点升序排序，找到最长的 End 以及最多的不重叠区间。
public class VideoStitching {
public int videoStitching(int[][] clips, int time) {
Arrays.sort(clips, (a, b)
-> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]
);
int res = 0;
// 视频片段从 0 开始
int cur_end = 0, next_end = 0;
int n = clips.length, i = 0;
while (i < n && clips[i][0] <= cur_end) {
while (i < n && clips[i][0] <= cur_end) {
next_end = Math.max(next_end, clips[i][1]);
i++;
}
res++;
cur_end = next_end;
if (cur_end >= time) {
return res;
}
}
return -1;
}
}这个问题也可以转化为跳跃游戏，通过构建跳跃游戏的数组，根据边界进行 + 1（以影片的起点作为索引）。
public class VideoStitching {
public int videoStitching(int[][] clips, int time) {
int n = clips.length;
// 表示每个位置可以向右跳的最大距离，构建类似跳跃游戏数组
int[] nums = new int[time];
for (int[] clip : clips) {
int l = clip[0], r = clip[1];
if (l < time && nums[l] < time) {
nums[l] = Math.max(nums[l], r - l);
}
}
int step = 0;
// 下一次/本次 可以跳的最远距离
int next = 0, cur = 0;
for (int i = 0; i < time; i++) {
// 无法跳跃
if (i > cur) {
return -1;
}
next = Math.max(next, i + nums[i]);
// 到达边界，同跳跃游戏
if (i == cur) {
cur = next;
step++;
}
}
return cur >= time ? step : -1;
}
}7.7 匹配问题
7.7.1 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符；
- 删除一个字符；
- 替换一个字符。
输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')这个题目最难的地方在于解决单词的操作问题，这些操作可以使用指针移动进行代替。通过指针移动避免直接修改字符串，这样就需要考虑修改的具体字符。
public class EditDistance {
private int[][] memo;
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
memo = new int[m][n];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return dp(word1, word2, m - 1, n - 1);
}
public int dp(String s1, String s2, int i, int j) {
// 其余指针遍历到最后，剩下还需操作的次数
if (i < 0) {
return j + 1;
}
if (j < 0) {
return i + 1;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (s1.charAt(i) == s2.charAt(j)) {
// skip
memo[i][j] = dp(s1, s2, i - 1, j - 1);
} else {
// 插入，删除，替换操作
memo[i][j] = min(
dp(s1, s2, i, j - 1),
dp(s1, s2, i - 1, j),
dp(s1, s2, i - 1, j - 1)
) + 1;
}
return memo[i][j];
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}转化为 dp table 形式，需要注意 base case。
public class EditDistance {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 如果另外的字符串还有长度，需要做 i/j 次更改
for (int i = 1; i <= m; i++) {
dp[i][0] = i;
}
for (int j = 1; j <= n; j++) {
dp[0][j] = j;
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i][j - 1],
dp[i - 1][j],
dp[i - 1][j - 1])
+ 1;
}
}
}
return dp[m][n];
}
public int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}7.7.2 正则表达式
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘.’ 匹配任意单个字符；
- ‘*’ 匹配零个或多个前面的那一个元素。
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
针对 p 的匹配情况，存在两种情况（通过 i、j 指针表示）：
- i 和 j 所在的字符相同（之后判断是否后一个字符为
*）：- 存在可以匹配多次或者不匹配（匹配次数为 0）；
- i、j 指针都进行移动。
- i 和 j 所在的字符不同：
- 存在则必须匹配 0 次，即不匹配；
- 返回 false（匹配失败）。
在 dp 递归中，还需要定义 hash 表用于存储当前 i、j 指针位置是否进行匹配。还需要注意不同情况下的 base case。
public class RegularExpressionMatching {
private final HashMap<String, Boolean> memo = new HashMap<>();
public boolean isMatch(String s, String p) {
return dp(s, p, 0, 0);
}
public boolean dp(String s, String p, int i, int j) {
int m = s.length(), n = p.length();
if (j == n) {
return i == m;
}
// s 结束时如果 p 匹配一次也可以满足
// 即必须出现 a* 形式匹配 0 次
if (i == m) {
if ((n - j) % 2 == 1) {
return false;
}
for (int k = j; k < n; k += 2) {
if (p.charAt(k + 1) != '*') {
return false;
}
}
return true;
}
String key = i + "," + j;
if (memo.containsKey(key)) {
return memo.get(key);
}
boolean res;
// 满足 a* 匹配情况
boolean match = j < p.length() - 1 && p.charAt(j + 1) == '*';
if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
if (match) {
// 匹配 0 次或者多次
res = dp(s, p, i, j + 2) ||
dp(s, p, i + 1, j);
} else {
res = dp(s, p, i + 1, j + 1);
}
} else {
if (match) {
res = dp(s, p, i, j + 2);
} else {
res = false;
}
}
memo.put(key, res);
return res;
}
}通过分析可以得知状态转移方程如上，match 表示参数内部字符是否相同。
public class RegularExpressionMatching {
public boolean isMatch(String s, String p) {
int m = s.length(), n = p.length();
boolean[][] dp = new boolean[m + 1][n + 1];
dp[0][0] = true;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
if (matches(s, p, i, j - 1)) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
} else {
if (matches(s, p, i, j)) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
public boolean matches(String s, String p, int i, int j) {
// i 已经到末尾时不可匹配
if (i == 0) {
return false;
}
// '.' 可以匹配任意数
if (p.charAt(j - 1) == '.') {
return true;
}
return s.charAt(i - 1) == p.charAt(j - 1);
}
}7.8 博弈论
8. 树
二叉树解题的思维模式分两类：
- 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个
traverse函数配合外部变量来实现，这叫「遍历」的思维模式； - 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
8.1 二叉树
8.1.1 遍历问题
中序遍历
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 （左节点、根节点、右节点）。
直接使用递归：
public class BinaryTreeInorderTraversal {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
print(res, root);
return res;
}
public void print(List<Integer> res, TreeNode root) {
if (root == null) {
return;
}
print(res, root.left);
res.add(root.val);
print(res, root.right);
}
}迭代方法，使用栈存储节点：
public class BinaryTreeInorderTraversal {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root != null || !stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
res.add(root.val);
root = root.right;
}
return res;
}
}8.1.2 BFS/DFS
很多题目都可以用到遍历思想。
二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
这个题目可以通过层序遍历来做，每一层对结果加一直到叶子节点。
public class MaximumDepthOfBinaryTree {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int res = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size > 0) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
size--;
}
res++;
}
return res;
}
}这个题目可以用递归简化，即每次都往左/右节点进行搜索：
public class MaximumDepthOfBinaryTree {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL。
每层遍历自然可以：
public class PopulatingNextRightPointersInEachNode {
public Node connect(Node root) {
if (root == null) {
return null;
}
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
Node node = queue.poll();
if (i < size - 1) {
node.next = queue.peek();
}
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
}这个题目的树可以进行进一步抽象，将每两个节点作为一个节点。
public class PopulatingNextRightPointersInEachNode {
public Node connect(Node root) {
if (root == null) {
return null;
}
traverse(root.left, root.right);
return root;
}
public void traverse(Node node1, Node node2) {
if (node1 == null || node2 == null) {
return;
}
node1.next = node2;
traverse(node1.left, node1.right);
traverse(node1.right, node2.left);
traverse(node2.left, node2.right);
}
}翻转二叉树
给你一棵二叉树的根节点 root，翻转这棵二叉树，并返回其根节点。
在分析之后可以发现，每次只需要交换左右两个节点，就可以完成目标。
迭代法如下：
public class InvertBinaryTree {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode node = root;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(node);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
node = queue.poll();
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
return root;
}
}翻转本质上还是交换左右子树，可以用递归简化代码：
public class InvertBinaryTree {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：
- 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null；
- 展开后的单链表应该与二叉树先序遍历顺序相同。
因为题目给出的方法返回值是 void，只能通过直接更改原二叉树。因为是先序遍历的结果，其实就是将右子树更改为根节点 + 左节点 + 右节点。
public class FlattenBinaryTreeToLinkedList {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
// 分别改变左右子树
flatten(root.left);
flatten(root.right);
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
root.right = left;
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
// 将原来的右子树接到改变后的左子树的后面
p.right = right;
}
}8.1.4 构造问题
这种题目只要掌握遍历的特性，之后通过递归计算出正确答案即可。
构造最大二叉树
给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建：
- 创建一个根节点，其值为 nums 中的最大值；
- 递归地在最大值 左边 的 子数组前缀上 构建左子树；
- 递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums 构建的最大二叉树。通过提示，可以直接写出递归。
public class MaximumBinaryTree {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return traverse(nums, 0, nums.length - 1);
}
public TreeNode traverse(int[] nums, int i, int j) {
if (i > j) {
return null;
}
if (i == j) {
return new TreeNode(nums[i]);
}
int maxIndex = i;
for (int k = i + 1; k <= j; k++) {
if (nums[k] > nums[maxIndex]) {
maxIndex = k;
}
}
TreeNode root = new TreeNode(nums[maxIndex]);
root.left = traverse(nums, i, maxIndex - 1);
root.right = traverse(nums, maxIndex + 1, j);
return root;
}
}xx遍历+xx遍历转为二叉树
所有的构造都是遵循根节点 + 左子树 + 右子树 。
从前序与中序遍历序列构造二叉树
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
通过前序遍历，第一个节点就是根节点，因为保证不会有重复节点，可以通过 rootVal 查询到 index。之后可以通过 leftSize 计算出其他子树的索引。
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
public TreeNode buildTree(int[] preorder, int[] inorder) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
hashMap.put(inorder[i], i);
}
return traverse(hashMap, preorder,
0, preorder.length - 1,
0, inorder.length - 1);
}
public TreeNode traverse(HashMap<Integer, Integer> hashMap, int[] preorder,
int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return null;
}
int rootVal = preorder[preStart];
TreeNode root = new TreeNode(rootVal);
int rootIndex = hashMap.get(rootVal);
// 计算左子树的长度
int leftSize = rootIndex - inStart;
root.left = traverse(hashMap, preorder,
preStart + 1, preStart + leftSize,
inStart, rootIndex - 1);
root.right = traverse(hashMap, preorder,
preStart + leftSize + 1,
preEnd, rootIndex + 1, inEnd);
return root;
}
}从中序与后序遍历序列构造二叉树
给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗二叉树 。
public class ConstructBinaryTreeFromInorderAndPostorderTraversal {
public TreeNode buildTree(int[] inorder, int[] postorder) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
hashMap.put(inorder[i], i);
}
return traverse(hashMap, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
public TreeNode traverse(HashMap<Integer, Integer> hashMap, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
int rootVal = postorder[postEnd];
int index = hashMap.get(rootVal);
int leftSize = index - inStart;
TreeNode root = new TreeNode(rootVal);
root.left = traverse(hashMap, inStart, index - 1,
postorder, postStart, postStart + leftSize - 1);
root.right = traverse(hashMap, index + 1, inEnd,
postorder, postStart + leftSize, postEnd - 1);
return root;
}
}从前序与后序遍历序列构造二叉树
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有无重复值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中任何一个。前序后序并不能确认一个二叉树，所以只需要返回一种答案。
public class ConstructBinaryTreeFromPreorderAndPostorderTraversal {
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < postorder.length; i++) {
hashMap.put(postorder[i], i);
}
return traverse(preorder, 0, preorder.length - 1,
hashMap, 0, postorder.length - 1);
}
public TreeNode traverse(int[] preorder, int preStart, int preEnd,
HashMap<Integer, Integer> hashMap, int postStart, int postEnd) {
if (preStart > preEnd || postStart > postEnd) {
return null;
}
int rootVal = preorder[preStart];
// 防止超出索引
if (preStart == preEnd) {
return new TreeNode(rootVal);
}
int index = hashMap.get(preorder[preStart + 1]);
int leftSize = index - postStart + 1;
TreeNode root = new TreeNode(rootVal);
root.left = traverse(preorder, preStart + 1, preStart + leftSize,
hashMap, postStart, index);
root.right = traverse(preorder, preStart + leftSize + 1, preEnd,
hashMap, index + 1, postEnd - 1);
return root;
}
}8.1.4 后序问题
寻找重复的子树
给你一棵二叉树的根节点 root ，返回所有 重复的子树 。对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]本题要求我们找到所有的相同子树，可以通过后序遍历，遍历出所有的子树，之后进行组装。利用哈希表存储重复的部分。重复部分的判断通过序列化形成的 String 进行存储。
public class FindDuplicateSubtrees {
private final HashMap<String, Integer> hashMap = new HashMap<>();
private final List<TreeNode> res = new ArrayList<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return res;
}
public StringBuilder traverse(TreeNode root) {
StringBuilder sb = new StringBuilder();
// 将空节点设置为 #
if (root == null) {
return sb.append("#");
}
// 先查找子树
StringBuilder left = traverse(root.left);
StringBuilder right = traverse(root.right);
// 使用 “，”隔开不同节点，防止出现额外重复问题
sb.append(left).append(",").append(right).append(",").append(root.val);
String cur = sb.toString();
// 只需要添加一次
if (hashMap.getOrDefault(cur, 0) == 1) {
res.add(root);
}
hashMap.put(cur, hashMap.getOrDefault(cur, 0) + 1);
return sb;
}
}上述方法瓶颈在于最后的序列会很长，即使使用 StringBuilder 也会消耗大量时间空间。
可以用一个三元组直接表示一棵子树，它们分别表示：
- 根节点的值为 x；
- 左子树的序号为 l；
- 右子树的序号为 r。
这里的「序号」指的是：每当我们发现一棵新的子树，就给这棵子树一个序号，用来表示其结构。那么两棵树是重复的，当且仅当它们对应的三元组完全相同。
public class FindDuplicateSubtrees {
private final Map<String, Pair<TreeNode, Integer>> seen = new HashMap<>();
private final Set<TreeNode> repeat = new HashSet<>();
private int idx = 0;
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return new ArrayList<>(repeat);
}
public int dfs(TreeNode node) {
if (node == null) {
return 0;
}
int[] tri = {node.val, dfs(node.left), dfs(node.right)};
String hash = Arrays.toString(tri);
if (seen.containsKey(hash)) {
Pair<TreeNode, Integer> pair = seen.get(hash);
repeat.add(pair.getKey());
return pair.getValue();
} else {
seen.put(hash, new Pair<>(node, ++idx));
return idx;
}
}
}8.1.5 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
最简单的方法直接通过递归实现（这个方法同样也适用于二叉树）：
public class CountCompleteTreeNodes {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}对于完全二叉树可以进行部分优化。完全二叉树的特殊情况是满二叉树，满二叉树的高度 h 公式为 h = 2 ^ (r - 1)。在递归的过程中可以计算出左右左右子树的深度进行简化计算。
public class CountCompleteTreeNodes {
public int countNodes(TreeNode root) {
TreeNode l = root, r = root;
int lh = 0, rh = 0;
while (l != null) {
lh++;
l = l.left;
}
while (r != null) {
rh++;
r = r.right;
}
if (lh == rh) {
return (int) Math.pow(2, lh) - 1;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}8.2 二叉搜索树
BST 的特性：
1、对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
2、对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。
从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。
8.2.1 有序性
二叉搜索树中第 K 小的元素
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
题目比较简单，通过计算中序遍历的次数就能得出答案。
public class KthSmallestElementInABST {
private int cur = 0;
private int res;
public int kthSmallest(TreeNode root, int k) {
traverse(root, k);
return res;
}
public void traverse(TreeNode root, int k) {
if (root == null) {
return;
}
traverse(root.left, k);
cur++;
if (cur == k) {
res = root.val;
return;
}
traverse(root.right, k);
}
}把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点；
- 节点的右子树仅包含键 大于 节点键的节点；
- 左右子树也必须是二叉搜索树。
因为正常遍历是升序，那我们只需要反向遍历即可。
package LeetCode.tree.day20;
import LeetCode.tree.TreeNode;
/**
* @program: tea
* @author: cxy621
* @create: 2023-02-03 00:19
**/
public class ConvertBSTToGreaterTree {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
traverse(root);
return root;
}
public void traverse(TreeNode root) {
if (root == null) {
return;
}
traverse(root.right);
sum += root.val;
root.val = sum;
traverse(root.left);
}
}8.2.2 基本操作
在 BST 中，搜索某个节点同二分搜索，小左大右。插入也是同理，找到对应的位置，最后创建 node 即可。
二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果。
public class InsertIntoABinarySearchTree {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) {
return new TreeNode(val);
}
if (val > root.val) {
root.right = insertIntoBST(root.right, val);
} else {
root.left = insertIntoBST(root.left, val);
}
return root;
}
}删除二叉搜索树中的节点
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
找到对应节点不难，重点在于删除之后要保持二叉搜索树的特性。这需要找到右子树最小的部分或者左子树最大的部分。
public class DeleteNodeInABST {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (key > root.val) {
root.right = deleteNode(root.right, key);
} else if (key < root.val){
root.left = deleteNode(root.left, key);
} else {
if (root.left == null) {
return root.right;
}
if (root.right == null) {
return root.left;
}
TreeNode minNode = getMin(root.right);
// 因为是要真的对节点做出改变，不能简单对值进行更改
root.right = deleteNode(root.right, minNode.val);
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
}
return root;
}
public TreeNode getMin(TreeNode root) {
while (root.left != null) {
root = root.left;
}
return root;
}
}验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
- 节点的左子树只包含 小于 当前节点的数；
- 节点的右子树只包含 大于 当前节点的数；
- 所有左子树和右子树自身必须也是二叉搜索树。
题目的主要坑在于需要保证左右子树也是二叉搜索树，就不能单纯对当前根节点和左右节点进行判断。
public class ValidateBinarySearchTree {
public boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
public boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) {
return true;
}
if (min != null && root.val <= min.val) {
return false;
}
if (max != null && root.val >= max.val) {
return false;
}
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
}8.2.3 构造二叉搜索树
不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
不同的二叉搜索区别在于如何选取 root 节点，通过这点可以构建递归。
public class UniqueBinarySearchTrees {
private int[][] memo;
public int numTrees(int n) {
memo = new int[n + 1][n + 1];
return count(1, n);
}
public int count(int low, int high) {
if (low > high) {
return 1;
}
if (memo[low][high] != 0) {
return memo[low][high];
}
int res = 0;
for (int mid = low; mid <= high; mid++) {
int left = count(low, mid - 1);
int right = count(mid + 1, high);
res += left * right;
}
memo[low][high] = res;
return res;
}
}给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。返回对应的根节点，只需要在返回处稍微修改即可。
public class UniqueBinarySearchTrees2 {
public List<TreeNode> generateTrees(int n) {
return build(1, n);
}
public List<TreeNode> build(int low, int high) {
List<TreeNode> res = new ArrayList<>();
if (low > high) {
res.add(null);
return res;
}
for (int i = low; i <= high; i++) {
List<TreeNode> leftTree = build(low, i - 1);
List<TreeNode> rightTree = build(i + 1, high);
for (TreeNode left : leftTree) {
for (TreeNode right : rightTree) {
TreeNode root = new TreeNode(i);
root.left = left;
root.right = right;
res.add(root);
}
}
}
return res;
}
}8.3 LCA
Lowest Common Ancestor，最近公共祖先问题。这也是 git rebase 的原理。
8.3.1 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]。
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。通过分析可以得知如果 val1 < root.val1 < val2，那么 root 就是最近公共祖先。如果不是就需要在左子树或者右子树进行查找。其他 root.val == val1 || root.val == val2 的情况也可以算作公共祖先。
public class LowestCommonAncestorOfABinarySearchTree {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int val1 = Math.min(p.val, q.val);
int val2 = Math.max(p.val, q.val);
return find(root, val1, val2);
}
public TreeNode find(TreeNode root, int val1, int val2) {
if (root == null) {
return null;
}
if (root.val > val2) {
return find(root.left, val1, val2);
}
if (root.val < val1) {
return find(root.right, val1, val2);
}
return root;
}
}8.3.2 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。对于普通二叉树，需要通过不断探索左右子树找到对应的祖先。在先序中如果 root.val = val1 || val2，此时的 root 必定是某个情况的祖先，可以直接返回（因为题目有说两个节点都在二叉树内，如果不行就不能使用这个技巧）。在后序中，判断是否左右子树中含有需要查找的数字。
class LowestCommonAncestorOfABinaryTree {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return find(root, p.val, q.val);
}
public TreeNode find(TreeNode root, int val1, int val2) {
if (root == null) {
return null;
}
if (root.val == val1 || root.val == val2) {
return root;
}
TreeNode left = find(root.left, val1, val2);
TreeNode right = find(root.right, val1, val2);
// 得知该节点左右子树都存在目标值
if (right != null && left != null) {
return root;
}
// 如果左子树没有找到，返回右子树
return left != null ? left : right;
}
}给定一棵二叉树的根节点 root 和 TreeNode 类对象的数组（列表） nodes，返回 nodes 中所有节点的最近公共祖先（LCA）。数组（列表）中所有节点都存在于该二叉树中，且二叉树中所有节点的值都是互不相同的。
我们扩展二叉树的最近公共祖先节点在维基百科上的定义：“对于任意合理的 i 值， n 个节点 p1 、 p2、…、 pn 在二叉树 T 中的最近公共祖先节点是后代中包含所有节点 pi 的最深节点（我们允许一个节点是其自身的后代）”。一个节点 x 的后代节点是节点 x 到某一叶节点间的路径中的节点 y。
输入: root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [7,6,2,4]
输出: 5
解释: 节点 7、6、2 和 4 的最近公共祖先节点是 5。这次需要查找的 node 变成了数组的形式，这不影响代码，题目依然指定所有节点都位于二叉树内。
public class LowestCommonAncestorOfABinaryTree4 {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
return find(root, nodes);
}
public TreeNode find(TreeNode root, TreeNode[] nodes) {
if (root == null) {
return null;
}
for (TreeNode node : nodes) {
if (root == node) {
return root;
}
}
TreeNode left = find(root.left, nodes);
TreeNode right = find(root.right, nodes);
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}如果题目允许将节点不存在，就不能在前序位置直接判断操作。需要使用一个标记记录二叉树中是否存在对应节点，在后序判断（要遍历完整个树）。
public class LowestCommonAncestorOfABinaryTree2 {
private boolean foundP = false, foundQ = false;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode res = find(root, p.val, q.val);
if (foundP && foundQ) {
return res;
}
return null;
}
public TreeNode find(TreeNode root, int val1, int val2) {
if (root == null) {
return null;
}
TreeNode left = find(root.left, val1, val2);
TreeNode right = find(root.right, val1, val2);
if (root.val == val1) {
foundP = true;
return root;
}
if (root.val == val2) {
foundQ = true;
return root;
}
if (left != null && right != null) {
return root;
}
return left != null ? left : right;
}
}二叉树转链表
给定一棵二叉树中的两个节点 p 和 q，返回它们的最近公共祖先节点（LCA）。
每个节点都包含其父节点的引用（指针）。Node 的定义如下：
class Node {
public int val;
public Node left;
public Node right;
public Node parent;
}分析可以知，新树的数据结构新添加了一个 parent 节点。本题使用之前的思路依然可以得出结果，但是这里可以转化为链表相交节点问题。二叉树可以作为特殊的链表，公共祖先即相交节点。
public class LowestCommonAncestorOfABinaryTree3 {
public Node lowestCommonAncestor(Node p, Node q) {
Node a = p, b = q;
while (a != b) {
if (a == null) {
a = q;
} else {
a = a.parent;
}
if (b == null) {
b = p;
} else {
b = b.parent;
}
}
return a;
}
}9. 队列
9.1 单调队列
单调队列，主要是为了解决下面这个场景：
给你一个数组 window，已知其最值为 A，如果给 window 中添加一个数 B，那么比较一下 A 和 B 就可以立即算出新的最值；但如果要从 window 数组中减少一个数，就不能直接得到最值了，因为如果减少的这个数恰好是 A，就需要遍历 window 中的所有元素重新寻找新的最值。
9.1.1 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7对于数据的存储，可以定义一个单调队列。每次存储时只存储最值，在窗口移动如果时最值，再寻找新的最值。
public class SlidingWindowMaximum {
public int[] maxSlidingWindow(int[] nums, int k) {
WindowQueue queue = new WindowQueue();
List<Integer> res = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (i < k - 1) {
queue.push(nums[i]);
} else {
queue.push(nums[i]);
res.add(queue.max());
queue.pop(nums[i - k + 1]);
}
}
int m = n - k + 1;
int[] temp = new int[m];
for (int i = 0; i < m; i++) {
temp[i] = res.get(i);
}
return temp;
}
}
class WindowQueue {
private final LinkedList<Integer> mq = new LinkedList<>();
public void push(int i) {
while (!mq.isEmpty() && mq.getLast() < i) {
mq.pollLast();
}
mq.addLast(i);
}
public int max() {
return mq.getFirst();
}
public void pop(int n) {
if (n == mq.getFirst()) {
mq.pollFirst();
}
}
}9.1.2 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1。
输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]同理，可以使用两个队列，一个队列用于存储原先顺序的数据流，另一个队列作为单调队列。只对每次的最值进行更新（每次都对队列尾进行更新）。
public class MaxQueue {
private final Queue<Integer> q;
private final Deque<Integer> d;
public MaxQueue() {
q = new LinkedList<>();
d = new LinkedList<>();
}
public int max_value() {
return d.isEmpty() ? -1 : d.getFirst();
}
public void push_back(int value) {
while (!d.isEmpty() && value > d.getLast()) {
d.pollLast();
}
q.offer(value);
d.offer(value);
}
public int pop_front() {
if (q.isEmpty()) {
return -1;
}
int temp = q.poll();
if (temp == d.getFirst()) {
d.pollFirst();
}
return temp;
}
}9.2 队列实现栈
9.2.1 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
- void push(int x) 将元素 x 推到队列的末尾；
- int pop() 从队列的开头移除并返回元素；
- int peek() 返回队列开头的元素；
- boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的；
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
队列的规则是先进先出，栈的规则是先进后出。如果使用两个栈，将第一个栈数据填入第二栈，那么就相当于是先进先出。每次都只在 stack2 为空时再将 stack1 的数据迁移过来。
public class MyStack {
private final Queue<Integer> q;
private int temp_x = 0;
public MyStack() {
q = new LinkedList<>();
}
public void push(int x) {
q.offer(x);
temp_x = x;
}
public int pop() {
int size = q.size();
while (size > 2) {
q.offer(q.poll());
size--;
}
temp_x = q.peek();
q.offer(q.poll());
return q.poll();
}
public int top() {
return temp_x;
}
public boolean empty() {
return q.isEmpty();
}
}9.2.2 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
- void push(int x) 将元素 x 压入栈顶；
- int pop() 移除并返回栈顶元素；
- int top() 返回栈顶元素；
- boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作；
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
通过使用 temp_x 保存最后一个进入队列的数字。之后在 pop 的过程中，将队列首部的数字添加到队列尾部，之后再更新 temp_x。
pub class MyStack {
private final Queue<Integer> q;
private int temp_x = 0;
public MyStack() {
q = new LinkedList<>();
}
public void push(int x) {
q.offer(x);
temp_x = x;
}
public int pop() {
int size = q.size();
while (size > 2) {
q.offer(q.poll());
size--;
}
// 将 temp_x 更新到倒数第二个数
temp_x = q.peek();
q.offer(q.poll());
return q.poll();
}
public int top() {
return temp_x;
}
public boolean empty() {
return q.isEmpty();
}
}9.3 数据流问题
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如 arr = [2,3,4] 的中位数是 3；
- 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
- MedianFinder() 初始化 MedianFinder 对象；
- void addNum(int num) 将数据流中的整数 num 添加到数据结构中；
- double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
解释
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1); // arr = [1]
medianFinder.addNum(2); // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3); // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0对于数组中求中位数为排序求中间值，但是题目中是数据流，反复排序每次会消耗大量时间。对于中位数，我们只关心的中间的一位/两位数。可以考虑使用单调队列将”小值“和”大值“部分的数据流分开。
small 部分使用大顶堆，大数在上；large 部分使用小顶堆，小数在上。但如果直接通过 size 堆将数据添加进队列，会出现问题。不仅要维护large和small的元素个数之差不超过 1，还要维护large堆的堆顶元素要大于等于small堆的堆顶元素。
public void addNum(int num) {
if (small.size() >= large.size()) {
large.offer(num);
} else {
small.offer(num);
}
}
简单说，想要往large里添加元素，不能直接添加，而是要先往small里添加，然后再把small的堆顶元素加到large中；向small中添加元素同理。
class MedianFinder {
private final PriorityQueue<Integer> small;
private final PriorityQueue<Integer> large;
public MedianFinder() {
// 大顶堆
small = new PriorityQueue<>((o1, o2) -> o2 - o1);
// 小顶堆
large = new PriorityQueue<>();
}
public void addNum(int num) {
// large 堆的堆顶元素要大于等于 small 堆的堆顶元素
if (small.size() >= large.size()) {
small.offer(num);
large.offer(small.poll());
} else {
large.offer(num);
small.offer(large.poll());
}
}
public double findMedian() {
// 奇数返回数目队列顶数字
if (large.size() < small.size()) {
return small.peek();
} else if (large.size() > small.size()){
return large.peek();
}
// 如果是偶数取平均值
return (large.peek() + small.peek()) / 2.0;
}
}10. 图
邻接表很直观，我把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表关联起来，这样就可以通过一个节点 x 找到它的所有相邻节点。
邻接矩阵则是一个二维布尔数组，权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的邻居，去扫一圈 matrix[x][..] 就行了。
10.1 dfs
图的 dfs 可以类比 N 叉树。一般题目给出邻接表或者邻接矩阵，通过这些进行遍历即可。
10.1.1 无环有向图
所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
题目保证输入为 有向无环图（DAG），在 dfs 中不需要使用 visited 数组来判断是否有重复节点。
public class AllPathsFromSourceToTarget {
private final List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
dfs(graph, new LinkedList<>(), 0);
return res;
}
public void dfs(int[][] graph, LinkedList<Integer> track, int index) {
track.addLast(index);
int n = graph.length;
// index 节点结束时候不立刻返回，因为需要返回其他路径
if (index == n - 1) {
res.add(new ArrayList<>(track));
}
for (int v : graph[index]) {
dfs(graph, track, v);
}
track.removeLast();
}
}10.1.2 检测环 & 拓扑排序
有些时候我们需要自己构造一个图，检测环就是在 dfs 的过程中使用 visited 检测是否出现环。除了使用 visited 之外，还需要使用 onPath 进行辅助。因为同一节点也可能因为其他节点遍历到，需要保证重复是在同一次遍历中。
课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。题目给出的是 nums[0] 依赖于 nums[1]，在构建图时可以反过来，方便时候 dfs 进行判断。
public class CourseSchedule {
private boolean[] visited;
private boolean[] onPath;
private boolean hasCycle = false;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = buildGraph(prerequisites, numCourses);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
// 需要遍历图中所有的节点
for (int i = 0; i < numCourses; i++) {
dfs(graph, i);
}
return !hasCycle;
}
public void dfs(List<List<Integer>> graph, int index) {
if (onPath[index]) {
hasCycle = true;
return;
}
if (visited[index]) {
return;
}
onPath[index] = true;
visited[index] = true;
for (int node : graph.get(index)) {
dfs(graph, node);
}
onPath[index] = false;
}
public List<List<Integer>> buildGraph(int[][] nodes, int n) {
List<List<Integer>> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int[] node : nodes) {
res.get(node[1]).add(node[0]);
}
return res;
}
}可以使用 BFS 做，BFS 算法借助 indegree 数组记录每个节点的「入度」
所谓「出度」和「入度」是「有向图」中的概念，很直观：如果一个节点 x 有 a 条边指向别的节点，同时被 b 条边所指，则称节点 x 的出度为 a，入度为 b。
public class CourseSchedule {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = buildGraph(prerequisites, numCourses);
int[] inDegree = new int[numCourses];
// 统计图中对应的入度
for (List<Integer> nodes : graph) {
for (int node : nodes) {
inDegree[node]++;
}
}
Queue<Integer> queue = new LinkedList<>();
// 从入读为 0 的节点开始遍历
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
count++;
for (int node : graph.get(cur)) {
inDegree[node]--;
if (inDegree[node] == 0) {
queue.offer(node);
}
}
}
// 直到遍历完所有节点
return count == numCourses;
}
public List<List<Integer>> buildGraph(int[][] nodes, int n) {
List<List<Integer>> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int[] node : nodes) {
res.get(node[1]).add(node[0]);
}
return res;
}
}现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
- 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
在一个有向图中，如果从节点 A 到节点 B 存在一条有向边，那么 A 就依赖于 B。拓扑排序的目的就是给这些节点排序，使得所有依赖于其他节点的节点都排在前面。
对图进行 DFS 遍历，记录后序遍历结果，最后把后序遍历结果反转就是拓扑排序。
把二叉树理解成一幅有向图，边的方向是由父节点指向子节点，那么就是下图：
public class CourseSchedule2 {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = buildGraph(prerequisites, numCourses);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
dfs(graph, i);
}
if (hasCycle) {
return new int[]{};
}
Collections.reverse(postOrder);
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = postOrder.get(i);
}
return res;
}
public void dfs(List<List<Integer>> graph, int index) {
if (onPath[index]) {
hasCycle = true;
return;
}
if (visited[index]) {
return;
}
onPath[index] = true;
visited[index] = true;
for (int node : graph.get(index)) {
dfs(graph, node);
}
postOrder.add(index);
onPath[index] = false;
}
public List<List<Integer>> buildGraph(int[][] nodes, int n) {
List<List<Integer>> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int[] node : nodes) {
res.get(node[1]).add(node[0]);
}
return res;
}
}拓扑排序的 BFS 版本就是根据入度对节点进行排序，之后输出结果。
public class CourseSchedule2 {
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<List<Integer>> graph = buildGraph(prerequisites, numCourses);
int[] inDegree = new int[numCourses];
for (List<Integer> nodes : graph) {
for (int node : nodes) {
inDegree[node]++;
}
}
int[] res = new int[numCourses];
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
queue.offer(i);
}
}
int count = 0;
while (!queue.isEmpty()) {
int cur = queue.poll();
res[count] = cur;
count++;
for (int node : graph.get(cur)) {
inDegree[node]--;
if (inDegree[node] == 0) {
queue.offer(node);
}
}
}
return count == numCourses? res :new int[]{};
}
public List<List<Integer>> buildGraph(int[][] nodes, int n) {
List<List<Integer>> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
for (int[] node : nodes) {
res.get(node[1]).add(node[0]);
}
return res;
}
}10.2 二分图
二分图的顶点集可分割为两个互不相交的子集，图中每条边依附的两个顶点都分属于这两个子集，且两个子集内的顶点不相邻。
可以将二分图进行简化，给你一幅「图」，请你用两种颜色将图中的所有顶点着色，且使得任意一条边的两个端点的颜色都不相同。
10.2.1 判断二分图
存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给你一个二维数组 graph ，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。该无向图同时具有以下属性：
- 不存在自环（graph[u] 不包含 u）；
- 不存在平行边（graph[u] 不包含重复值）；
- 如果 v 在 graph[u] 内，那么 u 也应该在 graph[v] 内（该图是无向图）；
- 这个图可能不是连通图，也就是说两个节点 u 和 v 之间可能不存在一条连通彼此的路径。
二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。
如果图是二分图，返回 true ；否则，返回 false 。
在判断二分图的过程中，使用 color 表示不同节点的颜色，使用 visited 记录是否有重复节点。在未遇到重复节点时，将节点填色。如果遇到重复节点，则判断节点颜色是否相等，如果不相等则出现冲突。
public class IsGraphBipartite {
private boolean[] isVisited;
private boolean[] color;
private boolean isRight = true;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
isVisited = new boolean[n];
color = new boolean[n];
for (int i = 0; i < n; i++) {
if (!isVisited[i]) {
dfs(graph, i);
}
}
return isRight;
}
public void dfs(int[][] graph, int index) {
// 如果已经不是二分图，直接结束
if (!isRight) {
return;
}
isVisited[index] = true;
for (int node : graph[index]) {
if (!isVisited[node]) {
color[node] = !color[index];
dfs(graph, node);
} else {
// 如果有冲突，则不是二分图
if (color[node] == color[index]) {
isRight = false;
}
}
}
}
}BFS 思路同 DFS，只不过使用 BFS 遍历每个节点。
public class IsGraphBipartite {
private boolean[] isVisited;
private boolean[] color;
private boolean isRight = true;
public boolean isBipartite(int[][] graph) {
int n = graph.length;
isVisited = new boolean[n];
color = new boolean[n];
for (int i = 0; i < n; i++) {
if (!isVisited[i]) {
bfs(graph, i);
}
}
return isRight;
}
public void bfs(int[][] graph, int index) {
Queue<Integer> q = new LinkedList<>();
q.offer(index);
while (!q.isEmpty() && isRight) {
int v = q.poll();
for (int node : graph[v]) {
if (!isVisited[node]) {
color[node] = !color[v];
isVisited[node] = true;
q.offer(node);
} else {
if (color[node] == color[v]) {
isRight = false;
return;
}
}
}
}
}
}10.2.2 可能的二分法
给定一组 n 人（编号为 1, 2, …, n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
题目中的要求已经符合二分图的定义，需要注意点是，这是一个无向图，无向图相当于双向图，在构建图的时候需要注意。
public List<List<Integer>> build(int[][] graph, int n) {
List<List<Integer>> res = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
res.add(new ArrayList<>());
}
// 无向图，即双向图
for (int[] nodes : graph) {
res.get(nodes[0] - 1).add(nodes[1] - 1);
res.get(nodes[1] - 1).add(nodes[0] - 1);
}
return res;
}10.3 并查集
并查集（Union-Find）算法是一个专门针对「动态连通性」的算法，也是最小生成树算法的前置知识。
首先要介绍连通分量。具体来说，连通分量是将一个无向图中所有的顶点划分为若干个互不相交的子集，每个子集中的顶点之间互相连通，而不同子集中的顶点则不连通。
如果有 10 个节点，连通分量为 10。如果将 0、1、2 进行连接，连通分量就变成 8。
设定树的每个节点有一个指针指向其父节点，如果是根节点的话，这个指针指向自己。如果某两个节点被连通，则让其中的（任意）一个节点的根节点接到另一个节点的根节点上。这样，如果节点 p 和 q 连通的话，它们一定拥有相同的根节点。
public int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}找寻根节点的方法已经通过递归进行了优化（如果直接构造树，会有导致树越来越大）。代码中的 parent[x] = find(parent[x]) 就是递归查找并压缩路径的过程。在查找根节点时，如果当前节点不是根节点，则递归查找当前节点的父节点的根节点，并将当前节点直接连接到根节点上，最终返回根节点。
public class UF {
private int count;
private final int[] parent;
private final int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) {
return;
}
// 节点数量小一些的树接到大一些的树下面，更平衡一些
if (size[rootP] >= size[rootQ]) {
parent[rootQ] = rootP;
} else {
parent[rootP] = rootQ;
}
if (size[rootP] == size[rootQ]) {
size[rootP]++;
}
count--;
}
public int find(int x) {
if (parent[x] == x) {
return x;
}
return parent[x] = find(parent[x]);
}
public boolean connect(int p, int q) {
return find(p) == find(q);
}
public int count() {
return count;
}
}10.3.1 无向图中连通分量的数目
你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。
返回 图中已连接分量的数目 。
这个题目可以使用 dfs 来做，根据遍历的次数来确定连通分量的数目。
public class NumberOfConnectedComponentsInAnUndirectedGraph {
private boolean[] visited;
public int countComponents(int n, int[][] edges) {
List<List<Integer>> graph = build(edges, n);
visited = new boolean[n];
int count = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(graph, i);
count++;
}
}
return count;
}
public void dfs(List<List<Integer>> graph, int index) {
if (visited[index] || graph.get(index).size() == 0) {
return;
}
visited[index] = true;
for (int node : graph.get(index)) {
dfs(graph, node);
}
}
public List<List<Integer>> build(int[][] edges, int n) {
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
return graph;
}
}这题也是标准的求取连通分量，可以直接调用 UF 模板。
public class NumberOfConnectedComponentsInAnUndirectedGraph {
public int countComponents(int n, int[][] edges) {
UF uf = new UF(n);
for (int[] edge : edges) {
uf.union(edge[0], edge[1]);
}
return uf.count();
}
}10.3.2 等式方程的可满足性
给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。先对所有 == 等式中的 a、b 进行连接，之后检查所有 != 等式，如果有冲突方程就有错误。
public class SatisfiabilityOfEqualityEquations {
public boolean equationsPossible(String[] equations) {
UF uf = new UF(26);
for (String s : equations) {
if (s.charAt(1) == '=') {
uf.union(s.charAt(0) - 'a', s.charAt(3) - 'a');
}
}
for (String s : equations) {
if (s.charAt(1) == '!' &&
uf.connect(s.charAt(0) - 'a', s.charAt(3) - 'a')) {
return false;
}
}
return true;
}
}10.3.3 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。乍一看是个岛屿问题，可以用 DFS 解决。题目已经定义所谓被围绕的区域即非周围的区域。将所有周围区域使用特殊符号进行标记，再将其余区域转为 X 即可解决问题。
public class SurroundedRegions {
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
dfs(board, 0, j);
}
if (board[m - 1][j] == 'O') {
dfs(board, m - 1, j);
}
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
dfs(board, i, 0);
}
if (board[i][n - 1] == 'O') {
dfs(board, i, n - 1);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == '#') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
public void dfs(char[][] board, int i, int j) {
int m = board.length, n = board[0].length;
if (i < 0 || j < 0 || i == m || j == n) {
return;
}
if (board[i][j] == '#' || board[i][j] == 'X') {
return;
}
board[i][j] = '#';
dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
}
}使用 UF 的思想是将所有的边界区域都放入同一个 dummy 中，之后将所有非 dummy 连通的节点进行转化。对于这题使用 UF 多少有些小题大作，因为都是同样进行标记。
public class SurroundedRegions {
public void solve(char[][] board) {
int m = board.length, n = board[0].length;
int dummy = m * n;
// 给 dummy 单独留一个位置
UF uf = new UF(dummy + 1);
// 将所有边界中含有 'O' 存入 dummy
for (int j = 0; j < n; j++) {
if (board[0][j] == 'O') {
uf.union(j, dummy);
}
if (board[m - 1][j] == 'O') {
uf.union((m - 1) * n + j, dummy);
}
}
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') {
uf.union(i * n, dummy);
}
if (board[i][n - 1] == 'O') {
uf.union(i * n + n - 1, dummy);
}
}
int[][] dp = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// 将与边界值相邻值传入 UF
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (board[i][j] == 'O') {
for (int k = 0; k < 4; k++) {
int x = i + dp[k][0];
int y = j + dp[k][1];
if (board[x][y] == 'O') {
uf.union(i * n + j, x * n + y);
}
}
}
}
}
for (int i = 1; i < m - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if (!uf.connect(dummy, i * n + j)) {
board[i][j] = 'X';
}
}
}
}
}10.3.4 以图判树
给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。
如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。
UF 模板题，判断是否存在重复连接情况即可。
public class GraphValidTree {
public boolean validTree(int n, int[][] edges) {
UF uf = new UF(n);
for (int[] edge : edges) {
int i = edge[0], j = edge[1];
if (uf.connect(i, j)) {
return false;
}
uf.union(i, j);
}
// 最后只会生成一个连通变量
return uf.count() == 1;
}
}10.4 最小生成树
图的最小生成树（Minimum Spanning Tree，简称 MST）是一棵包含图中所有顶点的生成树，并且权值之和最小的生成树。在一个带权无向连通图中，可能存在多个不同的生成树，但最小生成树的权值是唯一的。
求解图的最小生成树的常用算法有 Kruskal 算法和 Prim 算法，两者均采用贪心策略，但具体实现方式不同。Kruskal 算法通过按边权值排序，并从小到大加入不会产生环的边来构建最小生成树，而 Prim 算法通过从一个点开始，逐步加入与当前生成树相邻的权值最小的边来构建最小生成树。这两个算法在不同的场合下各有优缺点，具体使用哪个算法要看具体情况而定。
10.4.1 Kruskal 算法
Kruskal 算法是一种用来求解最小生成树的贪心算法，其基本思想是将边按照权值从小到大排序，依次加入到生成树中，如果加入某条边不会形成环，则将该边加入到生成树中。
具体来说，Kruskal 算法的步骤如下：
- 将图中所有的边按照权值从小到大排序；
- 初始化一个空的集合 S 作为生成树；
- 依次选择每一条边，如果该边的两个端点不在同一个连通分量中，则将该边加入到集合 S 中；
- 重复步骤 3 直到生成树包含了 n-1 条边（n 是图中顶点的个数），或者所有的边都被处理完了。
Kruskal 依赖于 UF，可以使用 UF 快速查看是否有形成环的情况。Kruskal 算法的时间复杂度是 O(E log E)，其中 E 是边的数量，主要由排序操作决定。因为 Kruskal 算法是基于贪心策略的，每次选择最小的边加入生成树中，并通过并查集来判断边的两个端点是否在同一个连通分量中，从而保证了生成树的最小性。
最低成本联通所有城市
想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。
给你整数 n 和一个数组 conections，其中 connections[i] = [xi, yi, costi] 表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。
返回连接所有城市的最低成本，每对城市之间至少有一条路径。如果无法连接所有 n 个城市，返回 -1。该 最小成本 应该是所用全部连接成本的总和。
使用 Kruskal 构建最小生成树，直接使用即可。
public class ConnectingCitiesWithMinimumCost {
public int minimumCost(int n, int[][] connections) {
UF uf = new UF(n);
// 将图中的权值进行排序
Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
int res = 0;
for (int[] edge : connections) {
int p = edge[0] - 1, q = edge[1] - 1;
if (uf.connect(p, q)) {
continue;
}
uf.union(p, q);
res += edge[2];
}
return uf.count() == 1 ? res : -1;
}
}连接所有点的最小费用
给你一个points 数组，表示 2D 平面上的一些点，其中 points[i] = [xi, yi] 。连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 ：|xi - xj| + |yi - yj| ，其中 |val| 表示 val 的绝对值。
请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时，才认为所有点都已连接。
输入：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
输出：20
解释：我们可以按照上图所示连接所有点得到最小总费用，总费用为 20。
注意到任意两个点之间只有唯一一条路径互相到达。
根据题目意思，需要构建每个节点到达其他节点的权重值。构建好之后，直接使用 UF 得出答案。
public class MinCostToConnectAllPoints {
public int minCostConnectPoints(int[][] points) {
List<int[]> edges = new ArrayList<>();
int n = points.length;
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
edges.add(new int[]{
i, j, Math.abs(x1 - x2) + Math.abs(y1 - y2)
});
}
}
edges.sort(Comparator.comparingInt(o -> o[2]));
UF uf = new UF(n);
int res = 0;
for (int[] edge : edges) {
int p = edge[0], q = edge[1];
if (uf.connect(p, q)) {
continue;
}
res += edge[2];
uf.union(p, q);
}
return res;
}
}10.4.2 Prim 算法
首先，Prim 算法也使用贪心思想来让生成树的权重尽可能小，也就是「切分定理」。
其次，Prim 算法使用 BFS 算法思想 和 visited 布尔数组避免成环，来保证选出来的边最终形成的一定是一棵树。
「切分」这个术语其实很好理解，就是将一幅图分为两个不重叠且非空的节点集合：
Prim 即先从一个节点开始，对当前节点的边进行切分。通过一个数组记录已经进入树中的节点，之后再进行切分，直到遍历完所有节点。
public class Prim {
private final PriorityQueue<int[]> queue;
private final boolean[] inMST;
private final List<int[]>[] graph;
private int weightSum = 0;
public Prim(List<int[]>[] graph) {
this.graph = graph;
// 根据边的权重进行排序
this.queue = new PriorityQueue<>(
Comparator.comparingInt(value -> value[2])
);
int n = graph.length;
this.inMST = new boolean[n];
// 先对第一个节点进行切分操作
inMST[0] = true;
cut(0);
while (!queue.isEmpty()) {
int[] edge = queue.poll();
int d = edge[1], w = edge[2];
if (inMST[d]) {
continue;
}
weightSum += w;
cut(d);
inMST[d] = true;
}
}
public void cut(int s) {
for (int[] edge : graph[s]) {
if (inMST[edge[1]]) {
continue;
}
queue.offer(edge);
}
}
public int getWeightSum() {
return weightSum;
}
public boolean isAllConnected() {
// 是否成功生成最小生成树
for (boolean in : inMST) {
if (!in) {
return false;
}
}
return true;
}
}在构建图时需要注意无向图需要构建两次连接。
最低成本联通所有城市
public class ConnectingCitiesWithMinimumCost {
public int minimumCost(int n, int[][] connections) {
Prim prim = new Prim(build(n, connections));
if (!prim.isAllConnected()) {
return -1;
}
return prim.getWeightSum();
}
public List<int[]>[] build(int n, int[][] connections) {
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] connection : connections) {
int p = connection[0] - 1, q = connection[1] - 1;
int w = connection[2];
graph[p].add(new int[]{p, q, w});
graph[q].add(new int[]{q, p, w});
}
return graph;
}
}连接所有点的最小费用
public class MinCostToConnectAllPoints {
public int minCostConnectPoints(int[][] points) {
Prim prim = new Prim(build(points));
return prim.getWeightSum();
}
public List<int[]>[] build(int[][] points) {
int n = points.length;
List<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
int distance = Math.abs(x1 - x2) + Math.abs(y1 - y2);
graph[i].add(new int[]{i, j, distance});
graph[j].add(new int[]{j, i, distance});
}
}
return graph;
}
}10.5 加权图
有些图在实际问题中边会存在权重，需要求出到达终点时的最小代价或者最大价值。在加权图中，不能将权重值默认为 1，在普通 BFS 中的步数统计就失去了意义。
10.5.1 Dijkstra 算法
Dijkstra 算法的基本思想是，先将起点到各个节点的距离初始化为无穷大，再逐步更新这些距离，直到找到最短路径。算法过程中需要维护两个集合：一个是已经找到最短路径的点的集合 S，一个是尚未确定最短路径的点的集合 Q。
具体实现过程如下：
- 将起点加入集合 S 中，将起点到其它节点的距离初始化为无穷大；
- 从集合 Q 中选取一个距离起点最近的节点 v，并将其加入集合 S 中；
- 对于 v 的每个邻居节点 u，如果通过 v 可以找到比起点更短的路径，就更新 u 的距离值；
- 重复步骤 2 和 3，直到所有的节点都加入了集合 S 中。
其次，需要一个 State 类来辅助算法的运行：
class State {
// 图节点的 id
int id;
// 从 start 节点到当前节点的距离
int distFromStart;
State(int id, int distFromStart) {
this.id = id;
this.distFromStart = distFromStart;
}
}Dijkstra 算法可以理解为带 dp table 的 BFS 算法：
int weight(int from, int to);
List<Integer> adj(int s);
int[] dijkstra(int start, List<Integer>[] graph) {
int V = graph.length;
int[] distTo = new int[V];
Arrays.fill(distTo, Integer.MAX_VALUE);
distTo[start] = 0;
Queue<State> pq = new PriorityQueue<>((a, b) -> {
return a.distFromStart - b.distFromStart;
});
pq.offer(new State(start, 0));
while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeID = curState.id;
int curDistFromStart = curState.distFromStart;
if (curDistFromStart > distTo[curNodeID]) {
continue;
}
for (int nextNodeID : adj(curNodeID)) {
int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
if (distTo[nextNodeID] > distToNextNode) {
distTo[nextNodeID] = distToNextNode;
pq.offer(new State(nextNodeID, distToNextNode));
}
}
}
return distTo;
}网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2通过 Dijkstra 算法，算出起点到达所有节点的代价，之后取最大值即可。
public class NetworkDelayTime {
public int networkDelayTime(int[][] times, int n, int k) {
List<int[]>[] graph = new LinkedList[n];
for (int i = 0; i < n; i++) {
graph[i] = new LinkedList<>();
}
for (int[] edge : times) {
int from = edge[0] - 1, to = edge[1] - 1, weight = edge[2];
graph[from].add(new int[]{to, weight});
}
int[] distTo = dijkstra(k - 1, graph);
int res = 0;
for (int i = 0; i < n; i++) {
if (distTo[i] == Integer.MAX_VALUE) {
return -1;
}
res = Math.max(res, distTo[i]);
}
return res;
}
public int[] dijkstra(int start, List<int[]>[] graph) {
int n = graph.length;
int[] distTo = new int[n];
Arrays.fill(distTo, Integer.MAX_VALUE);
distTo[start] = 0;
Queue<State> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a.distFromStart)
);
pq.offer(new State(start, 0));
while (!pq.isEmpty()) {
State curState = pq.poll();
int curNodeId = curState.id;
int curDistFromStart = curState.distFromStart;
if (curDistFromStart > distTo[curNodeId]) {
continue;
}
for (int[] nextNode : graph[curNodeId]) {
int nextNodeId = nextNode[0];
int distToNextNode = distTo[curNodeId] + nextNode[1];
if (distTo[nextNodeId] > distToNextNode) {
distTo[nextNodeId] = distToNextNode;
pq.offer(new State(nextNodeId, distToNextNode));
}
}
}
return distTo;
}
}
class State {
int id;
int distFromStart;
public State(int id, int distFromStart) {
this.id = id;
this.distFromStart = distFromStart;
}
}概率最大的路径
给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。
指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。
如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。
public class PathWithMaximumProbability {
public double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
List<double[]>[] graph = new LinkedList[n];
for (int i = 0; i < n; i++) {
graph[i] = new LinkedList<>();
}
int m = edges.length;
for (int i = 0; i < m; i++) {
// 无向图相对于双向图
int from = edges[i][0], to = edges[i][1];
double p = succProb[i];
graph[from].add(new double[]{to, p});
graph[to].add(new double[]{from, p});
}
return dijkstra(graph, start, end, n);
}
public double dijkstra(List<double[]>[] graph, int start, int end, int n) {
// 寻找最大概率
Queue<Path> pq = new PriorityQueue<>(
(a, b) -> Double.compare(b.possibility, a.possibility)
);
pq.offer(new Path(start, 1));
double[] distTo = new double[n];
Arrays.fill(distTo, -1);
distTo[start] = 1;
while (!pq.isEmpty()) {
Path node = pq.poll();
int currId = node.id;
double curPossibility = node.possibility;
if (currId == end) {
return curPossibility;
}
if (curPossibility < distTo[currId]) {
continue;
}
for (double[] neighbor : graph[currId]) {
int nid = (int) neighbor[0];
double np = distTo[currId] * neighbor[1];
if (np > distTo[nid]) {
distTo[nid] = np;
pq.offer(new Path(nid, np));
}
}
}
return 0.0;
}
}
class Path {
int id;
double possibility;
public Path(int id, double possibility) {
this.id = id;
this.possibility = possibility;
}
}最小体力消耗路径
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
输出：2
解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。这里注意题目答案为矩阵中的最小高度差，因为是二维矩阵，在构建图时也需要构建二维数组。
public class PathWithMinimumEffort {
public int minimumEffortPath(int[][] heights) {
int m = heights.length, n = heights[0].length;
int[][] distTo = new int[m][n];
for (int i = 0; i < m; i++) {
Arrays.fill(distTo[i], Integer.MAX_VALUE);
}
distTo[0][0] = 0;
Queue<Node> pq = new PriorityQueue<>(
Comparator.comparingInt(a -> a.effortFromStart)
);
pq.offer(new Node(0, 0, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int curX = node.x, curY = node.y;
int curEffort = node.effortFromStart;
if (curX == m - 1 && curY == n - 1) {
return curEffort;
}
if (curEffort > distTo[curX][curY]) {
continue;
}
for (int[] neighbor : adj(heights, curX, curY)) {
int nx = neighbor[0], ny = neighbor[1];
// 计算当前最大的高度差
int nextEffort = Math.max(
Math.abs(heights[nx][ny] - heights[curX][curY])
, distTo[curX][curY]
);
if (distTo[nx][ny] > nextEffort) {
distTo[nx][ny] = nextEffort;
pq.offer(new Node(nx, ny, nextEffort));
}
}
}
return -1;
}
public List<int[]> adj(int[][] matrix, int x, int y) {
int m = matrix.length, n = matrix[0].length;
int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
List<int[]> res = new LinkedList<>();
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) {
continue;
}
res.add(new int[]{nx, ny});
}
return res;
}
}
class Node {
int x, y;
int effortFromStart;
public Node(int x, int y, int effortFromStart) {
this.x = x;
this.y = y;
this.effortFromStart = effortFromStart;
}
}