前置说明，刷题采用语言为 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;
}
}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 棋盘类问题
2.2 集合类问题
组合总和
给你一个无重复元素的整数数组 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();
}
}
}3. 哈希表
3.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;
}
}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 接雨水
给定 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 旋转图像
给定一个 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;
}
}
}
}7. 动态规划
动态规划问题的一般形式就是求最值。求解动态规划的核心问题是穷举。只有列出正确的「状态转移方程」，才能正确地穷举。而且，需要判断算法问题是否具备「最优子结构」，是否能够通过子问题的最值得到原问题的最值。另外，动态规划问题存在「重叠子问题」，如果暴力穷举的话效率会很低，所以需要使用「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
通过递归自顶向上/通过线性表达式自底向上。
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
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;
while (i < j) {
int mid = (j - i) / 2 + i;
if (tails[mid] < num) {
i = mid + 1;
} else {
j = mid;
}
}
tails[i] = num;
if (i == res) {
res++;
}
}
return res;
}
}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.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];
}7.3.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 压缩成一维数组：
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.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][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，状态方程类似第四题。
// 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};
}
}8. 树
二叉树解题的思维模式分两类：
- 是否可以通过遍历一遍二叉树得到答案？如果可以，用一个
traverse函数配合外部变量来实现，这叫「遍历」的思维模式； - 是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
8.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.2 层序遍历
很多题目都可以用到层序遍历思想。
8.2.1 二叉树的最大深度
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
这个题目可以通过层序遍历来做，每一层对结果加一直到叶子节点。
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;
}
}8.2.2 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
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);
}
}8.2.3 翻转二叉树
给你一棵二叉树的根节点 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;
}
}8.3 二叉树展开为链表
给你二叉树的根结点 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;
}
// 将yua
p.right = right;
}
}8.4 构造问题
这种题目只要掌握遍历的特性，之后通过递归计算出正确答案即可。
8.4.1 构造最大二叉树
给定一个不重复的整数数组 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;
}
}8.4.2 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;
}
}