LeetCode 热题 100 指路：https://leetcode.cn/studyplan/top-100-liked/
其实已经是二刷了，不练就容易手生 =)
哈希#
数组、HashSet、HashMap。
1. 两数之和#
要返回数组下标，需要同时记录数字及其下标，使用 HashMap。
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[]{map.get(target - nums[i]), i};
}
map.put(nums[i], i);
}
return new int[0];
}
}
49. 字母异位词分组#
用一个 HashMap，key 是字母按顺序重新排序后的单词，value 是一个列表，放了所有该单词的字母异位词。
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map = new HashMap<>();
for(String str:strs) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
List<String> list = map.getOrDefault(key, new ArrayList<>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
128. 最长连续序列#
关键是找到连续序列的起点。
class Solution {
public int longestConsecutive(int[] nums) {
int max = 0;
int count = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
for(int num : set) {
if(!set.contains(num-1)) { // start point
count = 0;
while(set.contains(num)) {
num++;
count++;
}
max = max < count ? count : max;
}
}
return max;
}
}
双指针#
双指针主要有相向指针和快慢指针两种。
283. 移动零#
class Solution {
public void moveZeroes(int[] nums) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != 0) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
for(;slow<nums.length;slow++) { // fill 0
nums[slow] = 0;
}
}
}
11. 盛最多水的容器#
参考：扩展延伸
相向指针，从左右两侧向中间逼近，较矮的一侧向中间靠近，过程中记录最大值。
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int max = 0;
while (left < right) {
int v = Math.min(height[left], height[right]) * (right - left);
if (v > max) {
max = v;
}
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
15. 三数之和#
穷举，先确定第一个数字，就变成了两数之和的问题。
数组要使用双向指针，必须排序。
此题关键在于去重。
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // 必须先排序，才能保证遍历的准确性
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (nums[i] > 0)
break;
if (i >= 1 && nums[i - 1] == nums[i])
continue; // 第一个数nums[i]去重
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
List<Integer> ans = new ArrayList<>();
ans.add(nums[i]);
ans.add(nums[left]);
ans.add(nums[right]);
result.add(ans);
while (right > left && nums[right] == nums[right - 1])
right--; // nums[right]去重
while (right > left && nums[left] == nums[left + 1])
left++; // nums[left]去重
left++;
right--; // 要求出所有可能的组合，不能break
} else if (sum > 0)
right--;
else if (sum < 0)
left++;
}
}
return result;
}
}
42. 接雨水#
参考：如何高效解决接雨水问题
局部思想，仅仅对于一个位置能装多少水是如何决定的，取决于左侧的最高柱子高度和右侧的最高柱子高度的最小值。暴力算法就是遍历所有位置的左侧和右侧的柱子，优化点在于可以先计算一遍并进行记录，这样就不用每个位置都计算一遍了。
class Solution {
public int trap(int[] height) {
int[] lmax = new int[height.length]; // 每个位置的左侧最高柱子的高度
int[] rmax = new int[height.length]; // 每个位置的右侧最高柱子的高度
lmax[0] = height[0];
rmax[height.length-1] = height[height.length-1];
for(int i=1;i<height.length;i++) {
lmax[i] = Math.max(lmax[i-1], height[i]);
}
for(int i=height.length-2;i>=0;i--) {
rmax[i] = Math.max(rmax[i+1], height[i]);
}
int result = 0;
for(int i=0;i<height.length;i++) {
result = result + Math.min(lmax[i], rmax[i]) - height[i];
}
return result;
}
}
双指针解法，不用备忘录，边走边算，节省空间复杂度。lmax为 0 到 left 的最大高度，rmax为 right 到最右侧的最大高度。lmax更小就算 left 位置，反之亦然。
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int lmax = 0, rmax = 0;
int result = 0;
while (left < right) {
lmax = Math.max(height[left], lmax);
rmax = Math.max(height[right], rmax);
if(lmax < rmax) {
result = result + lmax - height[left];
left++;
} else {
result = result + rmax - height[right];
right--;
}
}
return result;
}
}
滑动窗口#
滑动窗口实质上是一种快慢指针的使用技巧。注意不变量，建议窗口区间为左闭右开。
3. 无重复字符的最长子串#
参考：四、最长无重复子串
class Solution {
public int lengthOfLongestSubstring(String s) {
HashSet<Character> window = new HashSet<>();
char[] chars = s.toCharArray();
int left = 0, right = 0; // 左闭右开
int max = 0;
while(right < chars.length) {
char c = chars[right];
while(window.contains(c)) { // 收缩窗口
window.remove(chars[left]);
left++;
}
window.add(c); // 扩大窗口
right++;
max = max >= (right - left) ? max : (right - left);
}
return max;
}
}
438. 找到字符串中所有字母异位词#
参考：三、找所有字母异位词
本题有两个关键点，一个在于收缩的条件，一个在于如何判断是否为字母异位词。
收缩条件可以是维护一个定长窗口，就是长度等于 p 的长度时，收缩一下，像毛毛虫一样蠕动。
判断字母异位词由两个因素决定，一个是上面说的定长窗口，另一个是记录个数相同的元素个数，只要元素个数相同一次valid就加 1，不用担心窗口中该字母个数再增加超过所需怎么办，因为定长窗口限制了这个字母超过了，其他字母就达不到valid+1 的要求，就不会是字母异位词。valid的减小在窗口收缩时实现。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character, Integer> need = new HashMap<>(); // <字母, 出现次数>
HashMap<Character, Integer> window = new HashMap<>();
for (char c : p.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
List<Integer> res = new ArrayList<>();
int left = 0, right = 0; // 左闭右开的区间
int valid = 0;
char[] chars = s.toCharArray();
while (right < chars.length) {
char c = chars[right];
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
right++;
while ((right - left) >= p.length()) {
if (valid == need.size()) { // 收缩前先判断是否为异位词
res.add(left);
}
char d = chars[left];
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) { // 移除前先判断
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
return res;
}
}
注意：在 Java 中，比较两个Integer对象的大小时，使用==运算符可能会导致意外的结果，因为==运算符比较的是对象引用，而不是对象的值。为了比较两个Integer对象的值，应该使用.equals()方法或将它们拆箱为原始类型int进行比较。
子串#
560. 和为 K 的子数组#
前缀和技巧。
参考：小而美的算法技巧：前缀和数组 day4_prefixSum2
class Solution {
public int subarraySum(int[] nums, int k) {
/**
* 通过计算前缀和，将问题转化为求解两个前缀和之差等于k的情况。
* 假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从[0,i]位置的元素之和。
* 那么对于任意的两个下标i和j（i<j），如果prefixSum[j] - prefixSum[i] =k，
* 即[i+1,j]位置的元素之和等于k。
* 通过遍历数组，计算每个位置的前缀和，并使用一个哈希表来存储每个前缀和出现的次数。
* 在遍历的过程中，我们检查是否存在prefixSum[j]-k的前缀和（当前游标为j）
* 如果存在，说明从某个位置到当前位置的连续子数组的和为k，我们将对应的次数累加到结果中。
* 这样，通过遍历一次数组，我们可以统计出和为k的连续子数组的个数，并且时间复杂度为O(n)，其中n为数组的长度。
*/
int count = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>(); // <前缀和, 出现次数>
map.put(0, 1); // 用于解决从下标 0 累加到下标 i 等于 k 的情况，方便统一处理
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
}
239. 滑动窗口最大值#
单调队列。
维护一个单调递减的队列，队首元素就是窗口中的最大值。注意实际实现过程中，队列里面应该存放下标，以便窗口右移时正确移除左侧应该移出的元素。
可以使用双端队列模拟单调队列，类似于栈。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>(); // 双端队列模拟单调队列
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
}
res[0] = nums[queue.peekFirst()];
for (int i = k; i < nums.length; i++) {
if (i - k == queue.peekFirst()) {
queue.pollFirst();
}
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
76. 最小覆盖子串#
典型的滑动窗口问题，解题思路和438. 找到字符串中所有字母异位词基本一致。
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>();
for(char c:t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0)+1);
}
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0;
int start = 0, len = s.length()+1; // 用于截取结果
while (right<s.length()) {
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))) {
valid++;
}
}
while (valid >= need.size()) {
char d = s.charAt(left);
if(right-left < len) { // 先保存一次
start = left;
len = right - left;
}
if(need.containsKey(d)) {
if(window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d)-1);
}
left++;
}
}
if(len == s.length()+1) {
return "";
}
return s.substring(start, start+len);
}
}
普通数组#
53. 最大子数组和#
参考：4. 最大子序和
贪心思想，直接进行一波模拟，sum 记录局部和是否小于 0，小于 0 就丢弃，res 记录最大值结果。
class Solution {
public int maxSubArray(int[] nums) {
int res = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
res = sum > res ? sum : res; // 取区间累计的最大值（相当于不断确定最大子序终止位置）
if (sum < 0) { // 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
sum = 0;
}
}
return res;
}
}
另一种贪心的实现，本质是一样的。
class Solution {
public int maxSubArray(int[] nums) {
int preSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++) {
if(preSum<=0) {
maxSum = Math.max(nums[i], maxSum);
preSum = nums[i];
} else {
maxSum = Math.max(nums[i] + preSum, maxSum);
preSum = nums[i]+preSum;
}
}
return maxSum;
}
}
动态规划实现：
class Solution {
public int maxSubArray(int[] nums) {
// dp[j] 为以nums[j]为末尾的连续子数组的最大和
// dp[i] = Math.max(dp[i], dp[i-1]+nums[i])
int[] dp = new int[nums.length];
// 初始值dp[i] = nums[i]
dp[0] = nums[0];
int res = dp[0];
for (int i = 1; i < nums.length; i++) {
dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]); // 要么继续，要么从头算
res = Math.max(res, dp[i]);
}
return res;
}
}
前缀和思想也很巧妙：
class Solution {
public int maxSubArray(int[] nums) {
int ans = Integer.MIN_VALUE;
int minPreSum = 0;
int preSum = 0;
for (int x : nums) {
preSum += x; // 当前的前缀和
ans = Math.max(ans, preSum - minPreSum); // 减去前缀和的最小值
minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值
}
return ans;
}
}
56. 合并区间#
参考：20. 合并区间
判断区间重叠，先排序再处理。算是贪心策略的一种吧。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (x, y) -> x[0] - y[0]); // 按左边界排序
List<int[]> res = new ArrayList<>();
int start = intervals[0][0]; // 左边界
int rightBound = intervals[0][1]; // 右边界
for(int i = 1;i<intervals.length;i++) {
if(intervals[i][0]<=rightBound) { // 区间重叠
rightBound = Math.max(intervals[i][1], rightBound);
} else {
res.add(new int[]{start, rightBound}); // 区间不重叠
start = intervals[i][0];
rightBound = intervals[i][1];
}
}
res.add(new int[]{start, rightBound});
return res.toArray(new int[res.size()][]);
}
}
189. 轮转数组#
纯技巧题，最简单的就是使用额外的数组，将原数组下标为 i 的元素放至新数组下标为 (i+k)modn 的位置。
class Solution {
public void rotate(int[] nums, int k) {
int n = nums.length;
int[] newArr = new int[n];
for (int i = 0; i < n; ++i) {
newArr[(i + k) % n] = nums[i];
}
System.arraycopy(newArr, 0, nums, 0, n);
}
}
找到规律的话可以使用 3 次数组翻转来实现：
class Solution {
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
238. 除自身以外数组的乘积#
先计算出前缀乘积数组和后缀乘积数组，再遍历一遍计算结果，前缀乘积 x 后缀乘积。
其实计算前缀和后缀数组的过程也可以看作是一种最简单的动态规划。
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] answer = new int[nums.length];
int[] prefix = new int[nums.length];
int[] suffix = new int[nums.length];
prefix[0] = 1;
suffix[nums.length - 1] = 1;
for (int i = 1; i < nums.length; i++) {
prefix[i] = prefix[i - 1] * nums[i - 1];
}
for (int i = nums.length - 2; i >= 0; i--) {
suffix[i] = suffix[i + 1] * nums[i + 1];
}
for (int i = 0; i < nums.length; i++) {
answer[i] = prefix[i] * suffix[i];
}
return answer;
}
}
41. 缺失的第一个正数#
参考：缺失的第一个正数
首先需要注意的就是抽屉原理。对于一个长度为 N 的数组，其中没有出现的最小的正整数一定在 [1, N+1] 范围内。
如果没有额外的时空复杂度要求，那么就很容易想到可以将数组所有的数放入哈希表，随后从 1 开始依次枚举正整数，并判断其是否在哈希表中，时间复杂度为 O(N)，空间复杂度为 O(N)。
为了减小空间复杂度，必须利用给定的数组来存储一些状态，将给定的数组改造为哈希表。
对数组进行遍历，对于遍历到的数 x，如果它在 [1,N] 的范围内，那么就将数组中的第 x−1 个位置（注意：数组下标从 0 开始）打上「标记」。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是 N+1，否则答案是最小的没有打上标记的位置加 1。
class Solution {
public int firstMissingPositive(int[] nums) {
// 首先排除非正整数
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= 0) {
nums[i] = Integer.MAX_VALUE;
}
}
// 遍历数组，对[1, n]范围内的数x做一个标记
// 将nums[x-1]置为负数
for (int i = 0; i < nums.length; i++) {
int num = Math.abs(nums[i]); // 取绝对值避免后面未遍历但被打上标记变负的数被跳过
if (num >= 1 && num <= nums.length) {
nums[num - 1] = -Math.abs(nums[num - 1]);
}
}
// 最后一次遍历，检查标记
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) { // 没有标记
return i + 1;
}
}
return nums.length + 1;
}
}
除了打标记外，还可以通过置换的方法实现，让数组的第 x−1 个元素为 x，每一个不对应的位置就代表一个缺失的正数。
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) { // 注意避免死循环
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
矩阵#
73. 矩阵置零#
空间复杂度 O (m+n) 的一种实现，用两个哈希表存放值为 0 位置的行号和列号，最后遍历置 0 即可。
class Solution {
public void setZeroes(int[][] matrix) {
HashSet<Integer> rows = new HashSet<>();
HashSet<Integer> columns = new HashSet<>();
for(int i=0;i<matrix.length;i++) {
for(int j=0;j<matrix[0].length;j++) {
if(matrix[i][j]==0) {
rows.add(i);
columns.add(j);
}
}
}
for(int i : rows) {
for(int j=0;j<matrix[0].length;j++) {
matrix[i][j] = 0;
}
}
for(int j:columns) {
for(int i=0;i<matrix.length;i++) {
matrix[i][j] = 0;
}
}
}
}
54. 螺旋矩阵#
解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
List<Integer> res = new ArrayList<>();
while (res.size() < m * n) { // 相等时遍历完毕
// 在顶部从左到右遍历，注意区间为左闭右闭
if (upper_bound <= lower_bound) { // 满足该条件才需要遍历这一行
for (int i = left_bound; i <= right_bound; i++) {
res.add(matrix[upper_bound][i]);
}
upper_bound++;
}
// 在右侧从上到下遍历
if (left_bound <= right_bound) {
for (int i = upper_bound; i <= lower_bound; i++) {
res.add(matrix[i][right_bound]);
}
right_bound--;
}
// 在底部从右到左遍历
if (upper_bound <= lower_bound) {
for (int i = right_bound; i >= left_bound; i--) {
res.add(matrix[lower_bound][i]);
}
lower_bound--;
}
// 在左侧从下到上遍历
if (left_bound <= right_bound) {
for (int i = lower_bound; i >= upper_bound; i--) {
res.add(matrix[i][left_bound]);
}
left_bound++;
}
}
return res;
}
}
48. 旋转图像#
纯技巧，用翻转代替旋转，先将矩阵沿对角线翻转，再将矩阵的每一行进行翻转即可。
class Solution {
public void rotate(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < i; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][matrix.length - j - 1];
matrix[i][matrix.length - j - 1] = tmp;
}
}
}
}
240. 搜索二维矩阵 II#
观察例子中的矩阵，如果从左上角开始搜索，如果目标值大于左上角的数，那么后续查询方向就有两个，左边或者下边。从右下角开始搜索也是同理。但是从另外两个角查起，就完全不同了。
线性查找，官解叫做 Z 字形查找：
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int i = m - 1, j = 0;
while (i >= 0 && j < n) {
if (matrix[i][j] == target) {
return true;
} else if (matrix[i][j] > target) {
i--;
} else {
j++;
}
}
return false;
}
}
也可以对每一行使用二分查找。
链表#
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
160. 相交链表#
参考：两个链表是否相交
解决这个问题的关键是，通过某些方式，让 p1 和 p2 能够同时到达相交节点 。
可以通过预先计算两条链表的长度来做到这一点，对齐尾部：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 先求出两个链表的长度
int lenA = 0, lenB = 0;
ListNode node = headA;
while(node!=null) {
lenA++;
node=node.next;
}
node = headB;
while(node!=null) {
lenB++;
node = node.next;
}
// 让ListA为更短的那个链表
if(lenA>lenB) {
node = headA;
headA = headB;
headB = node;
int tmp = lenA;
lenA = lenB;
lenB = tmp;
}
// 快慢指针启动,快指针先走几步
for(int i=0;i<lenB-lenA;i++) {
headB = headB.next;
}
while(headA!=null && headB!=null) {
if(headA==headB) {
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
更巧妙的方式是进行链表的拼接，让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。
(版本二) 合并链表实现同步移动
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// p1 指向 A 链表头结点，p2 指向 B 链表头结点
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
// p1 走一步，如果走到 A 链表末尾，转到 B 链表
if (p1 == null) p1 = headB;
else p1 = p1.next;
// p2 走一步，如果走到 B 链表末尾，转到 A 链表
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
}
206. 反转链表#
双指针法：
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while (cur!=null) {
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}
头插法，空间复杂度高：
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null)
return null;
ListNode resultList = new ListNode(head.val, null);
ListNode currentNode = head;
while(currentNode.next != null) {
currentNode = currentNode.next;
ListNode toAdd = new ListNode(currentNode.val, resultList);
resultList = toAdd;
}
return resultList;
}
}
递归法，参考：递归魔法：反转单链表
class Solution {
// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) { // 递归的base case
return head;
}
ListNode last = reverse(head.next);
head.next.next = head;
head.next = null;
return last;
}
}
234. 回文链表#
方法一：将值复制到数组中后用双指针法。没有技术含量。
方法二：快慢指针。将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。
方法三：使用递归实现链表的后序遍历，模拟双指针实现回文判断
class Solution {
ListNode left; // 从左往右移动的指针
public boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) {
return true;
}
if (traverse(right.next)) {
if (left.val == right.val) {
left = left.next;
return true;
}
}
return false;
}
}
141. 环形链表#
参考：判断链表是否包含环
快慢指针技巧，慢指针走一步，快指针走两步，如果快慢指针相遇，说明有环。
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
其实对于走两步的 fast 指针的判断条件，我理解的不是很清晰，什么时候用(fast != null && fast.next != null)，什么时候用(fast.next != null && fast.next.next != null)呢？
142. 环形链表 II#
同样是快慢指针，不过这次要返回入环的位置。只需要在 slow 和 fast 相遇时，将 slow 丢回 head，然后 slow 和 fast 以相同的步调出发，再次相遇的位置就是环的入口位置。
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
21. 合并两个有序链表#
参考：合并两个有序链表
本题很简单，迭代地进行尾插即可，注意使用虚拟头节点会更加方便，要善于使用它。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
while (list1 != null && list2 != null) {
if (list1.val <= list2.val) {
p.next = list1;
list1 = list1.next;
} else {
p.next = list2;
list2 = list2.next;
}
p = p.next; // p不断前进
}
if (list1 == null) {
p.next = list2;
}
if (list2 == null) {
p.next = list1;
}
return dummy.next;
}
}
2. 两数相加#
这道题和合并有序列表差不多的感觉，没啥好说的，就是注意最后还有进位的时候要多加一个节点。
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode();
ListNode p = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int val1 = l1 == null ? 0 : l1.val;
int val2 = l2 == null ? 0 : l2.val;
int sum = val1 + val2 + carry;
ListNode node = new ListNode(sum % 10);
carry = sum / 10;
p.next = node;
p = p.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry != 0) {
p.next = new ListNode(carry);
}
return dummy.next;
}
}
19. 删除链表的倒数第 N 个结点#
一眼快慢指针，和相交链表那道题以及回文链表那道题的快慢指针解法思想上都是一致的。
基本做法就是快指针先走几步，然后快慢指针一起走，这样两个指针间的距离是固定的，很方便寻找特定位置。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
注意，使用了虚拟头结点的技巧，是为了防止出现空指针的情况。
24. 两两交换链表中的节点#
这道题的思想和反转链表很相似，就是一个双指针。另外，一定要习惯使用虚拟头节点。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyHead = new ListNode(-1, head);
ListNode cur = dummyHead;
// 有两个节点才交换
while (cur.next != null && cur.next.next != null) {
ListNode tmp = cur.next;
cur.next = cur.next.next;
ListNode tmp1 = cur.next.next;
cur.next.next = tmp;
tmp.next = tmp1;
cur = cur.next.next;
}
return dummyHead.next;
}
}
也可以使用递归来实现，很好理解：
class Solution {
public ListNode swapPairs(ListNode head) {
// base case 不足两个节点
if (head == null || head.next == null) {
return head;
}
ListNode next1 = head.next;
ListNode next2 = swapPairs(head.next.next); // 递归
head.next = next2;
next1.next = head;
return next1;
}
}
25. K 个一组翻转链表#
参考：如何 K 个一组反转链表
这道题要和206. 反转链表相联系，用迭代实现翻转部分链表的功能，最后将链表拼接起来。用递归思想解这道题要显得优雅很多，迭代也无非一个 while 循环了事（还有虚拟头节点）。
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode a = head, b = head;
for (int i = 0; i < k; i++) {
if (b == null) {
return head; // base case: 节点总数<k
}
b = b.next;
}
ListNode newHead = reverse(a, b);
a.next = reverseKGroup(b, k); // a是区间[a, b)反转后的尾节点
return newHead;
}
// 反转区间[a, b)中的元素，注意左闭右开
ListNode reverse(ListNode a, ListNode b) {
ListNode pre = null, cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
}
138. 随机链表的复制#
参考：复制带随机指针的链表
第一种解法是回溯法 + 哈希表，使用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当拷贝完成，回溯到当前层时，即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，需要首先检查当前节点是否被拷贝过，如果已经拷贝过，可以直接从哈希表中取出拷贝后的节点的指针并返回即可。
class Solution {
HashMap<Node, Node> map = new HashMap<>();
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
if (map.containsKey(head)) {
return map.get(head);
}
Node newHead = new Node(head.val);
map.put(head, newHead);
newHead.next = copyRandomList(head.next);
newHead.random = copyRandomList(head.random);
return newHead;
}
}
其实上面一大段说的都复杂了，可以直接先对链表进行一次遍历，将节点和对应新节点放进哈希表中，再对链表进行一次遍历，对每个新节点的 next 域和 random 域进行赋值，指向的节点直接从哈希表中取即可。
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
Node cur = head;
HashMap<Node,Node> map = new HashMap<>();
while(cur!=null){
map.put(cur,new Node(cur.val));
cur = cur.next;
}
cur=head;
while(cur!=null){
map.get(cur).next=map.get(cur.next);
map.get(cur).random=map.get(cur.random);
cur=cur.next;
}
return map.get(head);
}
}
还有一种解法是迭代 + 节点拆分，我称呼为交织插入法。总共进行三次遍历：第一次遍历，创建新节点并将其插入到原节点后面；第二次遍历，复制 random 指针；第三次遍历，将新链表从原链表中分离出来。
148. 排序链表#
插入排序（147. 对链表进行插入排序）：
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(-1, head); // 便于在head前插入节点
ListNode last = head; // 维护已排序部分的最后一个节点
ListNode cur = head.next; // 待插入元素
while (cur != null) {
if (cur.val >= last.val) {
last = cur;
} else {
ListNode ptr = dummy;
while (ptr != last) {
if (cur.val <= ptr.next.val) {
last.next = cur.next;
cur.next = ptr.next;
ptr.next = cur;
break;
} else {
ptr = ptr.next;
}
}
}
cur = last.next;
}
return dummy.next;
}
}
自顶向下归并排序：
第一步，找中点拆分链表，使用快慢指针技巧；第二步，对两个子链表分别排序，递归调用；第三步，合并有序链表，使用21. 合并两个有序链表的做法。
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) { // base case
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode rightHead = slow.next;
slow.next = null; // 找到中点，拆分链表
ListNode left = sortList(head);
ListNode right = sortList(rightHead); // 递归排序
return merge(left, right);
}
ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
if (a == null) {
cur.next = b;
} else {
cur.next = a;
}
return dummy.next;
}
}
自顶向下归并排序的空间复杂度为O(logn)，如果采用自底向上归并排序的方法，则可以达到 O(1) 的空间复杂度。但其实没有太大的必要。
23. 合并 K 个升序链表#
参考：合并 k 个有序链表
类似于21. 合并两个有序链表，关键是如何在 K 个节点中快速找到值最小的一个节点，可以使用优先级队列进行优化。
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode head : lists) { // 将k个链表的头节点加入最小堆中
if (head != null) {
pq.add(head);
}
}
ListNode dummy = new ListNode(-1);
ListNode p = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
p.next = node;
p = node;
if (node.next != null) {
pq.add(node.next);
}
}
return dummy.next;
}
}
146. LRU 缓存#
哈希表映射 + 双链表 = 哈希链表 LinkedHashMap
class LRUCache {
HashMap<Integer, Node> map = new HashMap<>();
DoubleLinkedList linkedlist = new DoubleLinkedList();
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node node = map.get(key);
linkedlist.remove(node); // 将访问的节点移动到链表末尾
linkedlist.addLast(node);
return node.value;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
linkedlist.remove(node); // 将更新的节点移动到链表末尾
node.value = value; // 更新值
linkedlist.addLast(node);
} else {
Node node = new Node(key, value);
map.put(key, node);
linkedlist.addLast(node);
if (linkedlist.size() > capacity) {
Node removed = linkedlist.removeFirst();
map.remove(removed.key);
}
}
}
}
class Node {
int key, value;
Node next, prev;
public Node() {}
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
class DoubleLinkedList {
Node head, tail; // 虚拟头尾节点
int size;
public DoubleLinkedList() {
head = new Node();
tail = new Node();
head.next = tail;
tail.prev = head;
this.size = 0;
}
public Node addLast(Node node) {
node.prev = tail.prev;
node.next = tail;
tail.prev.next = node;
tail.prev = node;
size++;
return node;
}
public Node removeFirst() {
if (size == 0) {
return null;
}
Node node = head.next;
remove(node);
return node;
}
public void remove(Node node) {
node.next.prev = node.prev;
node.prev.next = node.next;
size--;
}
public int size() {
return this.size;
}
}
也可以用 Java 的内置类型 LinkedHashMap 来实现 LRU 算法。
二叉树#
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
94. 二叉树的中序遍历#
递归中序遍历：
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
traverse(root, res);
return res;
}
void traverse(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}
traverse(root.left, res);
res.add(root.val);
traverse(root.right, res);
}
}
104. 二叉树的最大深度#
递归的思想，分解问题，二叉树的最大深度为它左右子树最大深度的最大值加 1。
求最大深度要后序遍历。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
226. 翻转二叉树#
后序遍历，递归翻转左右子树。
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.right = left;
root.left = right;
return root;
}
}
101. 对称二叉树#
两棵树互为镜像需要满足的条件：1. 根节点的值相等；2. 每棵树的左子树与另一棵树的右子树镜像对称。
以前的做法，递归比较「左子树的左子树」与「右子树的右子树」，以及「左子树的右子树」和「右子树的左子树」。
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null) return false;
return compare(root.left,root.right);
}
boolean compare(TreeNode left, TreeNode right) {
if(left==null && right!=null) return false;
else if(left!=null && right==null) return false;
else if(left==null && right ==null) return true;
else if(left!=null && right!=null && left.val!=right.val) return false;
else {
if(compare(left.left,right.right)&&compare(left.right,right.left))
return true;
else return false;
}
}
}
优雅一点，同步移动两个指针来进行遍历，其实本质都是一样的。
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root);
}
boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) { // 只有一个为null
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
543. 二叉树的直径#
对于树的每一个节点而言，最大直径为「左子树的高度」+「右子树的高度」的最大值，使用后序递归遍历。
高度通常指的是从节点到叶子节点的最长路径，而深度通常指的是从根节点到某个节点的路径长度。（有时是节点数而非路径长度）
class Solution {
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxHeight(root);
return maxDiameter;
}
int maxHeight(TreeNode root) {
if (root == null) {
return 0;
}
int leftHeight = maxHeight(root.left);
int rightHeight = maxHeight(root.right);
// 更新最大直径
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
// 返回当前节点的最大高度
return Math.max(leftHeight, rightHeight) + 1;
}
}
102. 二叉树的层序遍历#
层序遍历其实就是图论中的广度优先遍历，需要借用辅助数据结构队列来实现。
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
// while循环，从上到下遍历树的每一层
while (!queue.isEmpty()) {
List<Integer> list = new ArrayList<>();
int size = queue.size();
// for循环，从左到右遍历每一层中的每一个节点
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
list.add(node.val);
}
res.add(list);
}
return res;
}
}
108. 将有序数组转换为二叉搜索树#
根据数组构造一棵二叉树，本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。有序数组构造二叉搜索树，分割点就是数组中间位置的节点。
构造二叉树使用前序遍历。
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return traverse(nums, 0, nums.length);
}
// [begin, end) 左闭右开
TreeNode traverse(int[] nums, int begin, int end) {
if (begin >= end) {
return null;
}
int mid = begin + (end - begin) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = traverse(nums, begin, mid);
root.right = traverse(nums, mid + 1, end);
return root;
}
}
98. 验证二叉搜索树#
参考：23. 验证二叉搜索树
一种比较直观的方法是中序遍历将值放进一个数组，判断数组是否有序，也可以在中序遍历过程中直接判断是否有序。
本题是道易错题，易错点在于不能简单的比较左节点小于中间节点、右节点大于中间节点就万事大吉，而是要比较左子树所有节点小于中间节点、右子树所有节点大于中间节点。这就需要使用一个全局变量存放当前的最大值，用来比较遍历的节点是否有序。
class Solution {
TreeNode max;
public boolean isValidBST(TreeNode root) {
if (root == null) {
return true;
}
if (!isValidBST(root.left)) {
return false;
}
if (max != null && max.val >= root.val) {
return false;
}
max = root;
return isValidBST(root.right);
}
}
230. 二叉搜索树中第 K 小的元素#
中序遍历，计数：
class Solution {
int count = 0;
int result = -1;
public int kthSmallest(TreeNode root, int k) {
inorderTravel(root, k);
return result;
}
void inorderTravel(TreeNode root, int k) {
if (root == null)
return;
inorderTravel(root.left, k);
count++;
if (count == k) {
result = root.val;
return;
}
inorderTravel(root.right, k);
}
}
如果需要频繁地查找第 k 小的值，可以记录子树的节点数：
class Solution {
// 存放以每个节点为根节点的子树的节点数
HashMap<TreeNode, Integer> map = new HashMap<>();
public int kthSmallest(TreeNode root, int k) {
count(root);
while (root != null) {
int left = map.getOrDefault(root.left, 0);
if (left > k - 1) {
root = root.left;
} else if (left < k - 1) {
root = root.right;
k = k - (left + 1);
} else {
break;
}
}
return root.val;
}
// 后序递归遍历统计以root为根节点的子树的节点数
int count(TreeNode root) {
if (root == null) {
return 0;
}
int left = count(root.left);
int right = count(root.right);
map.put(root, left + right + 1);
return left + right + 1;
}
}
199. 二叉树的右视图#
层序遍历，只取每一层的最右侧的一个元素：
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
if (i == size - 1) {
res.add(node.val);
}
}
}
return res;
}
}
114. 二叉树展开为链表#
变形的后序遍历（先访问右子树），用一个全局变量 pre 记录上一个遍历的节点，从链表的末尾开始接。pre 的用法与98. 验证二叉搜索树比较相似。
class Solution {
TreeNode pre = null; // pre记录上一个遍历的节点
public void flatten(TreeNode root) {
if (root == null) {
return;
}
flatten(root.right);
flatten(root.left);
root.right = pre;
root.left = null;
pre = root;
return;
}
}
105. 从前序与中序遍历序列构造二叉树#
前序遍历序列的第一个元素为根节点，也就是分割点，根据这个元素在中序遍历序列中的位置将其分割为中序遍历序列 (左) 和中序遍历序列 (右)，再根据左右两个中序子序列的大小，将前序遍历序列也分为左右两个子序列，这样就可以愉快地递归了。
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return construct(preorder, 0, preorder.length,
inorder, 0, inorder.length);
}
// [begin, end) 左闭右开
TreeNode construct(int[] preorder, int begin_pre, int end_pre,
int[] inorder, int begin_in, int end_in) {
if (begin_pre >= end_pre || begin_in >= end_in) {
return null;
}
int root_val = preorder[begin_pre];
int splitIndex = begin_in;
for (; splitIndex < end_in; splitIndex++) {
if (inorder[splitIndex] == root_val) {
break;
}
}
TreeNode root = new TreeNode(root_val);
root.left = construct(preorder, begin_pre + 1, begin_pre + 1 + splitIndex - begin_in,
inorder, begin_in, splitIndex);
root.right = construct(preorder, begin_pre + 1 + splitIndex - begin_in, end_pre,
inorder, splitIndex + 1, end_in);
return root;
}
}
可以用一个 Hash 表存放 inorder 数组中每个元素与索引的对应关系，便于查找分割点的位置。
437. 路径总和 III#
深度优先搜索，递归遍历每一个节点的所有可能的路径：
class Solution {
public int pathSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = rootSum(root, targetSum);
count += pathSum(root.left, targetSum);
count += pathSum(root.right, targetSum);
return count;
}
// 从根节点出发的路径数目
int rootSum(TreeNode root, long targetSum) {
if (root == null) {
return 0;
}
int count = 0;
if (root.val == targetSum) {
count++;
}
count += rootSum(root.left, targetSum - root.val);
count += rootSum(root.right, targetSum - root.val);
return count;
}
}
深度优先搜索的解法，对于二叉树的每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，时间复杂度最大为O(N)，对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(N2)。有很多重复运算。
前缀和思想，和560. 和为 K 的子数组十分类似，可以减少重复运算，只需要遍历一次二叉树，时间复杂度为O(N)。
定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。
递归回溯：
class Solution {
// <前缀和的值, 该值出现的次数>
HashMap<Long, Integer> prefix = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
prefix.put(0L, 1);
return backtrack(root, targetSum, 0);
}
int backtrack(TreeNode root, int targetSum, long cur) {
if (root == null) {
return 0;
}
int count = 0;
cur += root.val; // 当前节点的前缀和
count += prefix.getOrDefault(cur - targetSum, 0);
prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
count += backtrack(root.left, targetSum, cur);
count += backtrack(root.right, targetSum, cur);
prefix.put(cur, prefix.getOrDefault(cur, 0) - 1); // 回溯
return count;
}
}
236. 二叉树的最近公共祖先#
后序遍历，进行回溯，通过返回值判断公共祖先。
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) {
return null;
}
if (root == p || root == q) {
return root;
}
TreeNode leftReturn = lowestCommonAncestor(root.left, p, q);
TreeNode rightReturn = lowestCommonAncestor(root.right, p, q);
if (leftReturn != null && rightReturn != null) {
return root;
} else if (leftReturn != null && rightReturn == null) {
return leftReturn;
} else if (leftReturn == null && rightReturn != null) {
return rightReturn;
} else {
return null;
}
}
}
124. 二叉树中的最大路径和#
本题和543. 二叉树的直径很相似。
class Solution {
int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxGain(root);
return max;
}
int maxGain(TreeNode node) {
if (node == null) {
return 0;
}
// 递归计算左右子树最大值
int leftGain = maxGain(node.left);
int rightGain = maxGain(node.right);
// 当前节点路径最大和
int curMax = node.val + leftGain + rightGain;
// 更新全局路径最大和
max = Math.max(max, curMax);
// 返回节点node的最大路径贡献值，为负则取0
return Math.max(node.val + Math.max(leftGain, rightGain), 0);
}
}
注意，「当前节点的最大路径和」与「当前节点作为路径一部分的最大贡献值」有所区别。
图论#
图论部分在 hot100 中题目数量挺少的，而且没有涉及迪杰斯特拉、并查集等经典算法，需要额外补充学习。
200. 岛屿数量#
使用 FloodFill 算法，可以避免维护 visited 数组。
class Solution {
public int numIslands(char[][] grid) {
int res = 0;
for (int i = 0; i < grid.length; i++) { // 遍历 grid
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
res++; // 每发现一个岛屿，岛屿数量加一
dfs(grid, i, j); // 然后使用 DFS 将岛屿淹了
}
}
}
return res;
}
void dfs(char[][] grid, int x, int y) {
int m = grid.length;
int n = grid[0].length;
if (x < 0 || y < 0 || x >= m || y >= n) {
return;
}
if (grid[x][y] == '0') {
return;
}
// 将 (i, j) 变成海水
grid[x][y] = '0';
// 淹没上下左右的陆地
dfs(grid, x - 1, y); // up
dfs(grid, x, y + 1); // right
dfs(grid, x + 1, y); // down
dfs(grid, x, y - 1); // left
}
}
994. 腐烂的橘子#
多源广度优先遍历，简单的说，就是初始在队列中加入多个元素，而不是只有一个，其余和普通的广度优先遍历没有什么差别。
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
Queue<int[]> queue = new ArrayDeque<>();
// 遍历grid，将初始状态所有腐烂的橘子放入队列
int freshCount = 0; // 记录新鲜橘子的数量
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[] { i, j });
} else if (grid[i][j] == 1) {
freshCount++;
}
}
}
// 如果没有新鲜橘子，直接返回0
if (freshCount == 0) return 0;
int minutes = 0;
// BFS
while (!queue.isEmpty()) {
int size = queue.size();
boolean infected = false; // 标记是否有橘子被感染
for (int i = 0; i < size; i++) {
int[] location = queue.poll();
if (check(grid, queue, location[0] - 1, location[1])) infected = true; // up
if (check(grid, queue, location[0], location[1] + 1)) infected = true; // right
if (check(grid, queue, location[0] + 1, location[1])) infected = true; // down
if (check(grid, queue, location[0], location[1] - 1)) infected = true; // left
}
if (infected) minutes++; // 只有当感染发生时才增加分钟
}
// 检查还有没有新鲜橘子
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
return -1;
}
}
}
return minutes;
}
boolean check(int[][] grid, Queue<int[]> queue, int x, int y) {
int m = grid.length;
int n = grid[0].length;
if (x < 0 || y < 0 || x >= m || y >= n) {
return false;
}
if (grid[x][y] == 0 || grid[x][y] == 2) {
return false;
}
// 新鲜橘子
grid[x][y] = 2;
queue.offer(new int[] { x, y });
return true;
}
}
有两个容易出错的点：
分钟计数错误：如果每次 BFS 层遍历结束后，都将 minutes 增加 1 的话，即使队列中没有新鲜橘子被感染，minutes 仍然会增加。所以，当整个传播过程结束时，minutes 会比实际的腐烂时间多 1 分钟。需要调整代码，使得只有在确实有橘子被感染时才增加 minutes。
返回时间逻辑错误：如果没有任何新鲜橘子存在（即一开始所有橘子都已经腐烂或者没有橘子），minutes 会在遍历完队列之后直接变成 1，而这是不应该的。也就是说，minutes 可能会比实际情况多 1。
其实简单点可以使用两个全局变量 time 和 result，time 在每次 BFS 层遍历时增加，result 则只在遇到新鲜橘子时用 time 进行更新。
207. 课程表#
参考：环检测及拓扑排序算法 图结构基础及通用代码实现 图结构的 DFS/BFS 遍历
深度优先遍历所有路径，检测有没有环。
class Solution {
boolean[] onPath; // 记录正在使用中的节点
boolean[] visited; // 记录遍历过的节点，减少冗余计算
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 建图，邻接表
List<Integer>[] graph = new ArrayList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new ArrayList<>();
}
for (int[] edge : prerequisites) {
graph[edge[1]].add(edge[0]); // 修完from才能修to
}
onPath = new boolean[numCourses];
visited = new boolean[numCourses];
// 遍历每个节点
for (int i = 0; i < numCourses; i++) {
if (visited[i] == false) {
if (traverse(graph, i) == false) {
return false;
}
}
}
return true;
}
// 深度优先遍历以start为起点的所有路径
boolean traverse(List<Integer>[] graph, int start) {
if (onPath[start] == true) { // 有环
return false;
}
if (visited[start] == true) {
return true;
}
onPath[start] = true;
visited[start] = true;
for (int neighbor : graph[start]) {
if (!traverse(graph, neighbor)) {
return false;
}
}
onPath[start] = false;
return true;
}
}
210. 课程表 II要得到课程的拓扑排序。
首先，判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，可以复用本题的逻辑。
然后，在本题环检测的代码基础上添加记录后序遍历结果的逻辑，把图结构后序遍历的结果进行反转，就是拓扑排序的结果。
BFS 算法借助 indegree 数组记录每个节点的「入度」，也可以实现这两个算法。（个人感觉有点反直觉，没仔细钻研）
208. 实现 Trie (前缀树)#
参考：前缀树算法模板秒杀 5 道算法题 实现 Trie (前缀树)
Trie，又称前缀树或字典树，是一棵有根树，其每个节点包含两个字段，分别是指向子节点的指针数组 children、布尔字段 isEnd。
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
this.children = new Trie[26];
this.isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a'; // 子节点索引
if (node.children[index] == null) { // 子节点不存在
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return (node != null) && (node.isEnd == true);
}
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String prefix) { // 查找前缀
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
int index = prefix.charAt(i) - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
回溯#
46. 全排列#
class Solution {
boolean[] visited;
List<List<Integer>> res;
List<Integer> track;
public List<List<Integer>> permute(int[] nums) {
visited = new boolean[nums.length];
res = new ArrayList<>();
track = new ArrayList<>();
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
if (track.size() == nums.length) {
res.add(new ArrayList<>(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i] == true) {
continue;
}
visited[i] = true;
track.add(nums[i]);
backtrack(nums);
visited[i] = false; // 回溯
track.removeLast();
}
}
}
78. 子集#
参考：子集（元素无重不可复选）
class Solution {
boolean[] visited;
List<List<Integer>> res;
List<Integer> track;
public List<List<Integer>> subsets(int[] nums) {
visited = new boolean[nums.length];
res = new ArrayList<>();
track = new ArrayList<>();
backtrack(nums, 0);
return res;
}
void backtrack(int[] nums, int startIndex) {
res.add(new ArrayList<>(track));
// if (track.size() == nums.length) {
// return;
// }
for (int i = startIndex; i < nums.length; i++) {
if (visited[i] == true) {
continue;
}
visited[i] = true;
track.add(nums[i]);
backtrack(nums, i + 1);
visited[i] = false;
track.removeLast();
}
}
}
17. 电话号码的字母组合#
参考：5. 电话号码的字母组合
class Solution {
// 建立映射
String[] board = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
StringBuilder builder = new StringBuilder();
List<String> res = new ArrayList<>();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return res;
}
backtrack(digits, 0);
return res;
}
void backtrack(String digits, int startIndex) {
if (builder.length() == digits.length()) {
res.add(builder.toString());
return;
}
String obj = board[digits.charAt(startIndex) - '0'];
for (char ch : obj.toCharArray()) {
builder.append(ch);
backtrack(digits, startIndex + 1);
builder.deleteCharAt(builder.length() - 1); // 回溯
}
}
}
39. 组合总和#
难点在于如何去重，关键是活用 startIndex，不吃回头草，要吃就一口气吃干净。
class Solution {
List<List<Integer>> res;
List<Integer> track;
int sum;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList<>();
track = new ArrayList<>();
sum = 0;
backtrack(candidates, target, 0);
return res;
}
void backtrack(int[] candidates, int target, int startIndex) {
if (sum > target) {
return;
}
if (sum == target) {
res.add(new ArrayList<>(track));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
sum = sum + candidates[i];
track.add(candidates[i]);
backtrack(candidates, target, i);
sum = sum - candidates[i]; // 回溯
track.removeLast();
}
}
}
22. 括号生成#
参考：回溯算法实践：括号生成
class Solution {
List<String> result = new ArrayList<>();
StringBuilder sb = new StringBuilder();
public List<String> generateParenthesis(int n) {
backtracking(n, 0, 0);
return result;
}
void backtracking(int n, int leftCount, int rightCount) {
if (leftCount < rightCount) { // 保证左右括号配对
return;
}
if (leftCount > n || rightCount > n)
return;
if (leftCount == n && rightCount == n) {
result.add(sb.toString());
return;
}
sb.append('('); // for choice in ["(", ")"] 拆开
backtracking(n, leftCount + 1, rightCount);
sb.deleteCharAt(sb.length() - 1);
sb.append(')');
backtracking(n, leftCount, rightCount + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
79. 单词搜索#
这道题既可以说是回溯，也可以说是深度优先搜索，其实没什么太大的区别。
class Solution {
boolean[][] visited;
int m, n;
boolean res;
public boolean exist(char[][] board, String word) {
m = board.length;
n = board[0].length;
visited = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
backtrack(board, i, j, word, 0);
if (res == true) {
return true;
}
}
}
return false;
}
void backtrack(char[][] board, int x, int y, String word, int index) {
if (res == true) {
return;
}
if (x < 0 || y < 0 || x >= m || y >= n) {
return;
}
if (visited[x][y] == true) {
return;
}
if (board[x][y] != word.charAt(index)) {
return;
}
if (index == word.length() - 1) {
res = true;
return;
}
visited[x][y] = true;
backtrack(board, x - 1, y, word, index + 1); // up
backtrack(board, x, y + 1, word, index + 1); // right
backtrack(board, x + 1, y, word, index + 1); // down
backtrack(board, x, y - 1, word, index + 1); // left
visited[x][y] = false;
}
}
131. 分割回文串#
参考：9. 分割回文串
动态规划计算回文串，合理设置切割的区间。
class Solution {
boolean[][] isPalindrome;
List<String> list = new ArrayList<>();
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
isPalindrome = new boolean[s.length()][s.length()];
computePalindrome(s);
backtrack(s, 0);
return res;
}
// [startIndex, i]，区间左闭右闭
void backtrack(String s, int startIndex) {
if (startIndex >= s.length()) {
res.add(new ArrayList<>(list));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome[startIndex][i] == true) {
list.add(s.substring(startIndex, i + 1));
backtrack(s, i + 1);
list.removeLast();
}
}
}
void computePalindrome(String s) {
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = i; j < s.length(); j++) {
if (j == i) {
isPalindrome[i][j] = true;
} else if (j - i == 1) {
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j));
} else {
isPalindrome[i][j] = (s.charAt(i) == s.charAt(j)) &&
isPalindrome[i + 1][j - 1];
}
}
}
}
}
51. N 皇后#
递归的深度为棋盘的行数，横向 for 循环选择的是棋盘的列数。
class Solution {
char[][] board;
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
board = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = '.';
}
}
backtrack(n, 0);
return res;
}
void backtrack(int n, int depth) {
if (depth >= n) {
List<String> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
list.add(new String(board[i]));
}
res.add(list);
return;
}
for (int i = 0; i < n; i++) {
if (isValid(n, depth, i) == true) {
board[depth][i] = 'Q';
backtrack(n, depth + 1);
board[depth][i] = '.';
}
}
}
boolean isValid(int n, int x, int y) {
// 垂直方向
for (int i = 0; i < x; i++) {
if (board[i][y] != '.') {
return false;
}
}
// 反斜线方向
for (int i = x, j = y; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] != '.') {
return false;
}
}
// 斜线方向
for (int i = x, j = y; i >= 0 && j < n; i--, j++) {
if (board[i][j] != '.') {
return false;
}
}
return true;
}
}
二分查找#
35. 搜索插入位置#
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length; // 左闭右开
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
left = mid;
break;
} else if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
74. 搜索二维矩阵#
将二维矩阵视为一个展平的有序一维数组，并在这个虚拟的数组上进行二分查找。虽然矩阵实际上是二维的，但可以通过计算行列索引来实现对矩阵元素的访问。
对于一个 m x n 的矩阵，可以将其视为长度为 m * n 的一维数组，其中每个元素的索引 k 可以通过以下公式映射到二维矩阵的行和列：
- 行索引：
row = k / n - 列索引：
col = k % n
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int m = matrix.length; // 行数
int n = matrix[0].length; // 列数
int left = 0;
int right = m * n - 1; // 虚拟一维数组的长度
while (left <= right) {
int mid = left + (right - left) / 2; // 中间索引
int midValue = matrix[mid / n][mid % n]; // 将一维索引转换为二维索引
if (midValue == target) {
return true; // 找到目标值
} else if (midValue < target) {
left = mid + 1; // 搜索右半部分
} else {
right = mid - 1; // 搜索左半部分
}
}
return false; // 未找到目标值
}
}
34. 在排序数组中查找元素的第一个和最后一个位置#
class Solution {
public int[] searchRange(int[] nums, int target) {
int left_bound = binarySearchLeft(nums, target);
int right_bound = binarySearchRight(nums, target);
if (left_bound >= right_bound) {
return new int[] { -1, -1 };
}
return new int[] { left_bound, right_bound - 1 };
}
// 寻找左边界
int binarySearchLeft(int[] nums, int target) {
int left = 0, right = nums.length; // 左闭右开
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return right;
}
// 寻找右边界
int binarySearchRight(int[] nums, int target) {
int left = 0, right = nums.length; // 左闭右开
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
33. 搜索旋转排序数组#
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length; // 左闭右开
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] >= nums[left]) {
// 左侧有序
if (nums[left] <= target && target < nums[mid]) {
right = mid;
} else {
left = mid + 1;
}
} else {
// 右侧有序
if (nums[mid] < target && target <= nums[right - 1]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return -1;
}
}
和普通的二分查找的区别在于判断 target 在哪个区间的方式，普通的二分查找只需要简单地比较一下 nums [mid] 和 target 的大小即可判断 target 在 mid 左侧还是右侧，本题则需要根据有序的一侧进行判断，如果 target 的值在有序的一侧的范围内，那就搜索这一侧，否则搜索另一侧。总结一下就是判断搜索左侧还是右侧的方式不同。
153. 寻找旋转排序数组中的最小值#
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length; // 左闭右开
int min = nums[left];
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] >= nums[left]) {
// 左侧有序
min = Math.min(min, nums[left]);
left = mid + 1;
} else {
// 右侧有序
min = Math.min(min, nums[mid]);
right = mid;
}
}
return min;
}
}
4. 寻找两个正序数组的中位数#
划分数组：
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length, n = nums2.length;
if (m > n) {
return findMedianSortedArrays(nums2, nums1); // ensure m<=n
}
int left = 0, right = m; // 左闭右闭，二分[0, m]
while (left <= right) {
int i = (left + right) / 2;
int j = (m + n + 1) / 2 - i;
int maxLeft1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
int minRight1 = i == m ? Integer.MAX_VALUE : nums1[i];
int maxLeft2 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
int minRight2 = j == n ? Integer.MAX_VALUE : nums2[j];
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
if ((m + n) % 2 == 0) {
return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2.0;
} else {
return Math.max(maxLeft1, maxLeft2);
}
} else if (maxLeft1 > minRight2) {
right = i - 1;
} else if (maxLeft2 > minRight1) {
left = i + 1;
}
}
return -0.0;
}
}
边界值的处理：
maxLeft1 和 minRight1：
maxLeft1是nums1左侧部分的最大值。这个值通过i来确定，即nums1[i-1]。minRight1是nums1右侧部分的最小值。这个值通过i来确定，即nums1[i]。- 边界情况：
- 当
i=0时，意味着nums1的左侧部分没有元素。因此，maxLeft1设为Integer.MIN_VALUE，表示没有左边的最大值。 - 当
i=m时，意味着nums1的右侧部分没有元素。因此，minRight1设为Integer.MAX_VALUE，表示没有右边的最小值。
- 当
maxLeft2 和 minRight2：
maxLeft2是nums2左侧部分的最大值，计算方式同样是通过j来确定，即nums2[j-1]。minRight2是nums2右侧部分的最小值，计算方式为nums2[j]。- 边界情况：
- 当
j=0时，意味着nums2的左侧部分没有元素。因此，maxLeft2设为Integer.MIN_VALUE，表示没有左边的最大值。 - 当
j=n时，意味着nums2的右侧部分没有元素。因此，minRight2设为Integer.MAX_VALUE，表示没有右边的最小值。
- 当
合理的划分条件：
为了找到正确的划分，我们需要确保：
maxLeft1 <= minRight2且maxLeft2 <= minRight1。
如果满足这个条件，说明划分是合理的，此时可以根据总元素个数的奇偶性来计算中位数：
- 如果总个数是偶数，那么中位数就是左侧最大值与右侧最小值的平均值。
- 如果总个数是奇数，那么中位数就是左侧部分的最大值。
边界条件下的调整：
- 如果
maxLeft1 > minRight2，说明nums1的左侧部分划分得太大，需要缩小i，即right = i - 1。 - 如果
maxLeft2 > minRight1，说明nums2的左侧部分划分得太大，需要增大i，即left = i + 1。
通过这些边界值的判断和调整，可以确保最终找到正确的划分。
栈#
20. 有效的括号#
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
char[] ch = s.toCharArray();
for (int i = 0; i < ch.length; ++i) {
if (ch[i] == '(' || ch[i] == '{' || ch[i] == '[') {
stack.push(ch[i]);
} else {
if (stack.isEmpty())
return false;
if (ch[i] == ')') {
if (stack.pop() != '(')
return false;
} else if (ch[i] == ']') {
if (stack.pop() != '[')
return false;
} else if (ch[i] == '}') {
if (stack.pop() != '{')
return false;
}
}
}
return stack.isEmpty();
}
}
155. 最小栈#
辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
stack = new ArrayDeque<>();
minStack = new ArrayDeque<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty()) {
minStack.push(val);
} else {
minStack.push(Math.min(minStack.peek(), val));
}
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
链表模拟实现：
class MinStack {
// it just likes dp[i]=min(i.val, dp[i-1])
private Node head;
public MinStack() {
head = null;
}
public void push(int val) {
if (head == null) {
head = new Node(val);
} else {
// head is actually the top element
// maintains the min value
head = new Node(val, head);
}
}
public void pop() {
// top to bottom is an linkList
head = head.next;
}
public int top() {
return head.val;
}
public int getMin() {
return head.min;
}
private class Node {
int val;
int min;
Node next;
Node(int val) { // stack bottom node
this.val = val;
this.min = val;
next = null;
}
Node(int val, Node node) {
this.val = val;
this.min = Math.min(val, node.min);
next = node;
}
}
}
看一种脱裤子放屁的写法：
class MinStack {
private int minValue;
private Stack<Integer> stack;
public MinStack() {
stack = new Stack<>();
minValue = -1;
}
public void push(int x) {
if (stack.isEmpty()) {
stack.push(0);
minValue = x;
} else {
int diff = x - minValue;
stack.push(diff);
if (diff < 0) {
minValue = x;
}
}
}
public void pop() {
if (!stack.isEmpty()) {
int diff = stack.pop();
if (diff < 0) {
minValue = minValue - diff;
}
}
}
public int top() {
int diff = stack.peek();
return diff < 0 ? minValue : minValue + diff;
}
public int getMin() {
return stack.isEmpty() ? -1 : minValue;
}
}
394. 字符串解码#
我的写法，跑得太慢了：
class Solution {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<Character> stack = new ArrayDeque<>();
public String decodeString(String s) {
int ptr = 0;
while (ptr < s.length()) {
if (s.charAt(ptr) >= '0' && s.charAt(ptr) <= '9') {
int num = 0;
while (s.charAt(ptr) != '[') {
num = num * 10 + (s.charAt(ptr) - '0');
ptr++;
}
numStack.push(num);
continue;
} else if (s.charAt(ptr) == ']') {
int num = numStack.pop();
List<Character> list = new ArrayList<>();
while (stack.peek() != '[') {
list.add(stack.pop());
}
stack.pop();
for (int i = 0; i < num; i++) {
for (int j = list.size() - 1; j >= 0; j--) {
stack.push(list.get(j));
}
}
} else {
stack.push(s.charAt(ptr));
}
ptr++;
}
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
return sb.reverse().toString();
}
}
chatgpt 的写法，非常好优化：
class Solution {
Deque<Integer> numStack = new ArrayDeque<>();
Deque<StringBuilder> stack = new ArrayDeque<>();
public String decodeString(String s) {
int ptr = 0;
stack.push(new StringBuilder());
while (ptr < s.length()) {
char currentChar = s.charAt(ptr);
if (Character.isDigit(currentChar)) {
int num = 0;
while (Character.isDigit(s.charAt(ptr))) {
num = num * 10 + (s.charAt(ptr) - '0');
ptr++;
}
numStack.push(num);
continue; // 跳过 '['
} else if (currentChar == ']') {
int repeatTimes = numStack.pop();
StringBuilder decodedString = stack.pop();
StringBuilder parent = stack.peek();
for (int i = 0; i < repeatTimes; i++) {
parent.append(decodedString);
}
} else if (currentChar == '[') {
stack.push(new StringBuilder());
} else {
stack.peek().append(currentChar);
}
ptr++;
}
return stack.pop().toString();
}
}
739. 每日温度#
参考：1. 每日温度
单调栈。要找一个元素右边第一个比自己大的元素，需要维护一个单调递增栈（从栈顶到栈底单调递增）。
栈顶 是栈的唯一入口和出口。所有元素的 入栈（push） 和 出栈（pop） 操作都发生在栈顶。
栈底 是栈中最先放入的元素所在的位置，但它并没有直接的访问途径。如果要访问栈底的元素，必须通过多次出栈操作逐一移除栈顶的元素，直到到达栈底。
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
if (temperatures.length == 1) {
return new int[] { 0 };
}
Deque<Integer> stack = new ArrayDeque<>(); // 单调栈，存下标
stack.push(0);
int[] answer = new int[temperatures.length];
for (int i = 1; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
// 当前遍历的温度大于栈顶温度
int j = stack.pop();
answer[j] = i - j;
}
stack.push(i);
}
return answer;
}
}
84. 柱状图中最大的矩形#
参考：5. 柱状图中最大的矩形
class Solution {
// 对于每一根柱子，左右延展找到所有连续的高度不小于该柱子高度的柱子
// 也就是找到该柱子左右两侧第一个高度小于该柱子高度的柱子的下标
// 这样绘制的矩形，高度是该柱子的高度，宽度是左右延展的宽度
// 要找到左侧和右侧第一个高度小于该柱子高度的两根柱子，需要维护一个单调栈，栈顶到栈底是单调递减的
// 这样对于栈顶元素，如果当前遍历元素小于栈顶元素，那么栈顶元素左侧第一根更矮的柱子是栈顶元素-1，右侧第一根更矮的柱子是当前遍历元素
public int largestRectangleArea(int[] heights) {
Deque<Integer> stack = new ArrayDeque<>(); // 单调栈，存下标
int res = 0;
for (int i = 0; i <= heights.length; i++) {
// 到最后一个元素时，设为0确保处理完所有栈中的元素
int currentHeight = (i == heights.length) ? 0 : heights[i];
while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
int height = heights[stack.pop()];
// 栈为空说明左侧没有比currentHeight更矮的了，宽度为i
int width = stack.isEmpty() ? i : i - stack.peek() - 1;
res = Math.max(res, height * width);
}
stack.push(i);
}
return res;
}
}
下面这种做法在细节的处理上更好理解一点，将给定的数组 heights 首尾加上一个 0，在首部加 0 是为了始终能够得到 left（其实就是 width = i 的处理）；在末尾加 0 就是为了解决栈中剩余的元素，剩下的元素从左到右是单调递增的，右侧没有更矮的柱子，我们就人为添加一根高度为 0 的柱子来统一计算逻辑。
class Solution {
public int largestRectangleArea(int[] heights) {
// 遍历高度，找宽度
int[] h = new int[heights.length+2];
for(int i=1;i<h.length-1;i++) {
h[i]=heights[i-1];
}
Deque<Integer> stack = new LinkedList<>();
stack.push(0);
int maxSquare = 0;
for(int i=1;i<h.length;i++) {
if(h[i]>h[stack.peek()]) {
stack.push(i);
}
else if(h[i]==h[stack.peek()]){
stack.pop();
stack.push(i);
}
else {
while(!stack.isEmpty() && h[i]<h[stack.peek()]) {
int mid = stack.pop();
int left = stack.peek();
maxSquare = Math.max(maxSquare, h[mid] * (i-left-1));
}
stack.push(i);
}
}
return maxSquare;
}
}
堆#
215. 数组中的第 K 个最大元素#
堆排序，可以不用排完，排到倒数第 k 个元素 - 1 即可。
class Solution {
int heap_size;
public int findKthLargest(int[] nums, int k) {
HEAP_SORT(nums);
return nums[nums.length - k];
}
void MAX_HEAPIFY(int[] nums, int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < heap_size && nums[largest] < nums[left]) {
largest = left;
}
if (right < heap_size && nums[largest] < nums[right]) {
largest = right;
}
if (largest != i) {
exchange(nums, i, largest);
MAX_HEAPIFY(nums, largest);
}
}
void BUILD_MAX_HEAP(int[] nums) {
heap_size = nums.length;
for (int i = nums.length / 2 - 1; i >= 0; i--) {
MAX_HEAPIFY(nums, i);
}
}
void HEAP_SORT(int[] nums) {
BUILD_MAX_HEAP(nums);
for (int i = nums.length - 1; i > 0; i--) {
exchange(nums, 0, i);
heap_size--;
MAX_HEAPIFY(nums, 0);
}
}
void exchange(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
直接使用 Java 优先级队列容器，没啥技术含量：
class Solution {
public int findKthLargest(int[] nums, int k) {
// 大顶堆，降序
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((e1, e2) -> e2 - e1);
for (int i = 0; i < nums.length; i++) {
priorityQueue.offer(nums[i]);
}
for (int i = 0; i < k - 1; i++) {
priorityQueue.poll();
}
return priorityQueue.poll();
}
}
347. 前 K 个高频元素#
手写最大堆，堆排序：
class Solution {
int heap_size;
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
if (list.size() <= k) {
int[] res = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
res[i] = list.get(i).getKey();
}
return res;
}
HEAP_SORT(list);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = list.get(list.size() - i - 1).getKey();
}
return res;
}
void MAX_HEAPIFY(List<Map.Entry<Integer, Integer>> list, int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
if (l < heap_size && list.get(largest).getValue() < list.get(l).getValue()) {
largest = l;
}
if (r < heap_size && list.get(largest).getValue() < list.get(r).getValue()) {
largest = r;
}
if (largest != i) {
Collections.swap(list, i, largest);
MAX_HEAPIFY(list, largest);
}
}
void BUILD_MAX_HEAP(List<Map.Entry<Integer, Integer>> list) {
heap_size = list.size();
for (int i = list.size() / 2 - 1; i >= 0; i--) {
MAX_HEAPIFY(list, i);
}
}
void HEAP_SORT(List<Map.Entry<Integer, Integer>> list) {
BUILD_MAX_HEAP(list);
for (int i = list.size() - 1; i > 0; i--) {
Collections.swap(list, 0, i);
heap_size--;
MAX_HEAPIFY(list, 0);
}
}
}
优化：
void HEAP_SORT(List<Map.Entry<Integer, Integer>> list, int k) {
BUILD_MAX_HEAP(list);
for (int i = list.size() - 1; i >= list.size() - k; i--) {
Collections.swap(list, 0, i);
heap_size--;
MAX_HEAPIFY(list, 0);
}
}
直接用容器：
class Solution {
public int[] topKFrequent(int[] nums, int k) {
HashMap<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 小顶堆
PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((e1,e2)->e1[1]-e2[1]); // map entry = int[2]
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(priorityQueue.size()<k) {
priorityQueue.offer(new int[]{entry.getKey(), entry.getValue()});
}
else{
if(entry.getValue()>priorityQueue.peek()[1]){
priorityQueue.poll();
priorityQueue.offer(new int[]{entry.getKey(), entry.getValue()});
}
}
}
int[] res =new int[k];
for(int i=k-1;i>=0;--i){
res[i]=priorityQueue.poll()[0];
}
return res;
}
}
295. 数据流的中位数#
双堆：
class MedianFinder {
private PriorityQueue<Integer> maxHeap; // 最大堆，存储较小的一半
private PriorityQueue<Integer> minHeap; // 最小堆，存储较大的一半
public MedianFinder() {
// 最大堆使用自定义比较器来实现倒序
maxHeap = new PriorityQueue<>(Collections.reverseOrder());
minHeap = new PriorityQueue<>();
}
public void addNum(int num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
// 保持两个堆的平衡
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
} else if (minHeap.size() > maxHeap.size()) {
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
}
}
}
中位数是有序数据集合中的中间值。通过将数据一分为二，最大堆保存较小的那一半数据，最小堆保存较大的那一半数据，我们可以直接通过两个堆顶的值来确定中位数。
通过最大堆的堆顶元素和最小堆的堆顶元素，我们可以在 O (1) 时间内计算出中位数。相比之下，如果使用其他方法（如直接排序），获取中位数的时间复杂度会更高，特别是在频繁插入数据时。
贪心算法#
121. 买卖股票的最佳时机#
当前股价与历史最低股价的差值的最大值就是所求最大利润。
class Solution {
public int maxProfit(int[] prices) {
int min = prices[0]; // 记录股票价格的最小值
int res = 0; // 记录获取利润的最大值
for (int i = 1; i < prices.length; i++) {
if (prices[i] <= min) {
min = prices[i];
} else {
res = Math.max(res, prices[i] - min);
}
}
return res;
}
}
55. 跳跃游戏#
class Solution {
public boolean canJump(int[] nums) {
// 维护一个范围，观察范围内的元素，如果元素下标与元素值之和大于等于最后一个下标，返回true
// 双指针（类似于滑动窗口）
int left = 0, right = 0;
while (left <= right) {
right = Math.max(right, left + nums[left]);
if (right >= nums.length - 1) {
return true;
}
left++;
}
return false;
}
}
45. 跳跃游戏 II#
说实话，第一时间想到的解法是 BFS：
class Solution {
public int jump(int[] nums) {
if (nums.length == 1)
return 0; // 如果数组长度为1，意味着不需要跳跃
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
int right = 0; // 当前可以跳到的最远位置
int jumps = 0; // 跳跃次数
while (!queue.isEmpty()) {
int size = queue.size();
jumps++; // 每进入下一层 BFS 增加一次跳跃次数
for (int i = 0; i < size; i++) {
int index = queue.poll();
right = Math.max(right, nums[index] + index);
// 如果能跳到或者超过最后一个位置，返回跳跃次数
if (right >= nums.length - 1) {
return jumps;
}
// 将下一层次的下标加入队列
for (int j = index + 1; j <= right && j < nums.length; j++) {
if (queue.contains(j))
continue; // 避免重复加入队列
queue.offer(j);
}
}
}
return -1; // 若无法到达最后位置返回 -1
}
}
不出意料，超时了。还是用贪心算法搞一搞吧。
其实这道题的贪心也是一种类似” 分层 “的实现，不过它不显式地使用队列，而是通过不断更新范围来达到同样地效果。关键就是使用currentEnd 表示当前跳跃能够到达的最远位置，每次遍历数组时，当我们走到 currentEnd 时，就意味着我们需要做一次跳跃来进入下一层。
class Solution {
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
int jumps = 0; // 记录跳跃次数
int currentEnd = 0; // 当前能跳到的最远位置
int farthest = 0; // 能跳到的最远位置
for (int i = 0; i < nums.length - 1; i++) {
farthest = Math.max(farthest, i + nums[i]); // 更新最远能到达的位置
// 如果到达了当前能跳到的最远位置，就增加跳跃次数，并更新当前能跳到的最远位置
if (i == currentEnd) {
jumps++;
currentEnd = farthest;
// 如果当前能跳到的最远位置已经到达或超过终点，就可以返回跳跃次数
if (currentEnd >= nums.length - 1) {
break;
}
}
}
return jumps;
}
}
763. 划分字母区间#
class Solution {
public List<Integer> partitionLabels(String s) {
Map<Character, Integer> map = new HashMap<>(); // 记录每个字母最后出现的下标
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), i);
}
List<Integer> res = new ArrayList<>();
// 维护一个范围
int left = 0, right = 0;
while (left < s.length()) {
right = map.get(s.charAt(left));
for (int i = left; i <= right; i++) {
right = Math.max(right, map.get(s.charAt(i)));
}
res.add(right - left + 1);
left = right + 1;
}
return res;
}
}
由于字符串 s 中的字符都是小写英文字母，可以用长度为 26 的数组代替 Map 来记录每个字符的最后出现位置。这可以减少 HashMap 操作的开销。给出另一种实现的代码：
class Solution {
public List<Integer> partitionLabels(String s) {
List<Integer> res = new ArrayList<>();
// 记录每个字符最后出现的位置
int[] position = new int[26];
char[] arr = s.toCharArray();
for (int i = 0; i < arr.length; i++) {
position[arr[i] - 'a'] = i;
}
int start = 0;
int end = 0;
for (int i = 0; i < arr.length; i++) {
end = Math.max(end, position[arr[i] - 'a']);
if (i == end) { // 当前位置是当前划分的结束位置
res.add(end - start + 1); // 添加划分长度
start = end + 1; // 更新下一个划分的起始位置
}
}
return res;
}
}
动态规划#
参考：动态规划理论基础
70. 爬楼梯#
class Solution {
public int climbStairs(int n) {
// dp[i]表示i+1阶的方法数
// dp[i] = dp[i-1] + dp[i-2];
// dp[0] = 1, dp[1] = 2
// 滚动数组的技巧，减少空间复杂度
int[] dp = new int[2];
dp[0] = 1;
dp[1] = 2;
if (n <= 2) {
return dp[n - 1];
}
int sum = 0;
for (int i = 2; i < n; i++) {
sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
}
118. 杨辉三角#
class Solution {
public List<List<Integer>> generate(int numRows) {
// dp[i][j]表示第i行第j个数（start 0）
// dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
// dp[i][0] = 1, dp[i][i] = 1
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
row.add(1);
continue;
}
row.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
}
res.add(row);
}
return res;
}
}
198. 打家劫舍#
class Solution {
public int rob(int[] nums) {
/**
* dp[j]表示偷到第j号房间能偷到的最高金额
* dp[j] = Math.max(dp[j-1], dp[j-2]+nums[j])
*/
int[] dp = new int[nums.length + 1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
}
return dp[nums.length];
}
}
279. 完全平方数#
参考：0-1 背包理论基础 (一) 0-1 背包理论基础 (二) 完全背包理论基础
class Solution {
public int numSquares(int n) {
// 完全背包，将完全平方数看作可以无限使用的物品，背包容量为整数n
// 求当背包被刚好放满时，最小的物品个数
// dp[j]表示容量为j的背包的最小个数
int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 1; i * i <= n; i++) { // 遍历物品
for (int j = 0; j <= n; j++) {
if (j >= i * i) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
}
return dp[n];
}
}
322. 零钱兑换#
class Solution {
public int coinChange(int[] coins, int amount) {
// 完全背包，思路同完全平方数基本一致
// 将硬币看作可以无限使用的物品，背包容量为总金额，求达到总金额的最小的硬币个数
// dp[j]表示凑成总金额为j需要的最小硬币数目
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < coins.length; i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历容量
if (dp[j - coins[i]] != Integer.MAX_VALUE) { // 等于初始值则跳过！！！
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
if (dp[amount] == Integer.MAX_VALUE) { // 不能凑成总金额
return -1;
}
return dp[amount];
}
}
139. 单词拆分#
参考：26. 单词拆分
背包问题关键是把握遍历顺序。
首先是遍历背包容量的顺序。01 背包需要从大到小倒序遍历背包容量，这是为了保证每个物品只能被放入一次；与 01 背包相对应，完全背包就需要从小到大遍历背包容量，因为每个物品可以多次放入。
其次是两层 for 循环的遍历方式。01 背包必须外层遍历物品，内层遍历容量，这是因为 01 背包容量需要倒序遍历，如果外层遍历容量，会导致每一个容量只能至多放入一个物品。完全背包需要看是否考虑物品放入的顺序，如果是求排列数，顺序敏感，则必须外层遍历容量，内层遍历物品，求出所有的组合；如果是求组合数，顺序不敏感，只要集合相同即可，先遍历物品即可。
给出一个求排列数的完全背包的例子：
假设你有 2 种物品，物品1 和 物品2，背包容量为 3，你想计算排列数。
- 外层循环：遍历容量
首先，外层循环从容量1开始，逐步增加到容量3。在每个容量上，我们尝试通过选择物品来填充背包。 - 内层循环：遍历物品
- 当容量为
1时，我们依次尝试放入物品1和物品2，两种方案：(1)和(2)。 - 当容量为
2时，依次尝试放入物品1或物品2，在此基础上，我们可以再次选择所有物品，形成新的方案，比如1+1、2+1、1+2和2+2。 - 当容量为
3时，我们尝试放入物品1或物品2，并在此基础上构建出所有可能的排列，例如1+1+1、1+2、2+1、2+2。
- 当容量为
每次放入物品时，都会基于当前容量和之前计算的可能方案生成新的排列。由于排列数对顺序敏感，我们需要确保每次都考虑到不同顺序下的所有可能情况。
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// wordDict表示物品，s表示背包，是强调物品顺序的完全背包问题
// dp[j]表示字符串长度为j且dp[j]==true时能拆分为一个或多个单词
// dp[j] = dp[j-i.len] && sub(j-i.len, j).equals(i)
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
// 求排列数，必须先遍历容量，再遍历物品
for (int j = 1; j <= s.length(); j++) {
for (int i = 0; i < wordDict.size(); i++) {
String word = wordDict.get(i);
if (j >= word.length() && dp[j - word.length()] &&
s.substring(j - word.length(), j).equals(word)) {
dp[j] = true;
}
}
}
return dp[s.length()];
}
}
300. 最长递增子序列#
参考：41. 最长上升子序列
动态规划经典的子序列问题，关键是确定 dp 数组的含义。
class Solution {
public int lengthOfLIS(int[] nums) {
// dp[i]表示以nums[i]结尾的最长子序列的长度
// dp[i] = max(dp[j]+1) j from 0 to i-1
int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
dp[i] = 1;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[j] + 1, dp[i]); // 求dp[i]的最大值
}
}
res = Math.max(dp[i], res); // 求res的最大值
}
return res;
}
}
152. 乘积最大子数组#
注意递推式dp[i] = max(dp[i-1]*nums[i], nums[i])不满足最优子结构，一旦出现两个负数就歇菜了，和最长递增子序列的思路是有区别的。
class Solution {
public int maxProduct(int[] nums) {
// 子数组必须是连续的，子序列可以不连续
// dp_min[i]表示以nums[i]为结尾的子数组的最小乘积
// dp_max[i]表示以nums[i]为结尾的子数组的最大乘积
// dp_min[i] = min(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i], nums[i])
// dp_max[i] = max(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i], nums[i])
// 可以使用滚动数组的技巧压缩空间复杂度
int dp_max = nums[0], dp_min = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
int oldmax = dp_max, oldmin = dp_min;
dp_max = Math.max(Math.max(oldmax * nums[i], oldmin * nums[i]), nums[i]);
dp_min = Math.min(Math.min(oldmax * nums[i], oldmin * nums[i]), nums[i]);
res = Math.max(dp_max, res);
}
return res;
}
}
更简单的方法是不用动态规划，直接从前往后求一遍前缀积，再从后往前求一遍后缀积，取最大值即可。
416. 分割等和子集#
class Solution {
public boolean canPartition(int[] nums) {
// 01背包问题，容量为sum/2，价值与重量相等，每个数只能放一次
// 最后看价值最大是不是等于sum/2
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 != 0) {
return false;
}
int[] dp = new int[sum / 2 + 1];
for (int i = 0; i < nums.length; i++) { // 遍历物品
for (int j = sum / 2; j >= nums[i]; j--) { // 遍历容量
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
if (dp[sum / 2] != sum / 2) {
return false;
}
return true;
}
}
32. 最长有效括号#
class Solution {
public int longestValidParentheses(String s) {
// 类似于子数组，dp[i]表示以charAt(i)结尾的最长有效括号子串的长度
// charAt(i) == '(', dp[i] = 0
// charAt(i) == ')' -> charAt(i-1) == '(' || ')'
if (s.length() <= 1) {
return 0;
}
int[] dp = new int[s.length()];
int res = 0;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')' && s.charAt(i - 1) == '(') {
if (i < 2) {
dp[i] = 2;
} else {
dp[i] = dp[i - 2] + 2;
}
} else if (s.charAt(i) == ')' && s.charAt(i - 1) == ')' &&
i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
if (i - dp[i - 1] < 2) { // 前面只剩一个左括号
dp[i] = dp[i - 1] + 2;
} else {
dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
}
} else {
continue;
}
res = Math.max(dp[i], res);
}
return res;
}
}
逻辑写的有点乱，能看懂就行。
多维动态规划#
62. 不同路径#
class Solution {
public int uniquePaths(int m, int n) {
// dp[i][j]表示走到matrix[i][j]的路径数
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) { // 最左方拓展一列
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) { // 最上方拓展一行
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
64. 最小路径和#
class Solution {
public static int minPathSum(int[][] grid) {
// dp[i][j]表示到grid[i][j]的最小数字总和
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
// 初始化
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
}
}
return dp[m - 1][n - 1];
}
}
5. 最长回文子串#
class Solution {
public String longestPalindrome(String s) {
// dp[i][j]表示子串[i, j]是回文串，左闭右闭
char[] chars = s.toCharArray();
int n = chars.length;
boolean[][] dp = new boolean[n][n];
// 初始化
int maxLen = 1;
int left = 0, right = 0;
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 开始递推
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (chars[i] == chars[j] && (dp[i + 1][j - 1] || j == i + 1)) { // 左下方
dp[i][j] = true;
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
left = i;
right = j;
}
}
}
return s.substring(left, right + 1);
}
}
注意根据递推式确定正确的遍历顺序。
1143. 最长公共子序列#
class Solution {
public static int longestCommonSubsequence(String text1, String text2) {
// 两个维度分别对应两个字符串
// dp[i][j]表示字符串text1[0, i]与字符串test2[0, j]的最长公共子序列的长度
char[] text1_arr = text1.toCharArray();
char[] text2_arr = text2.toCharArray();
int m = text1_arr.length;
int n = text2_arr.length;
int[][] dp = new int[m][n];
// 递推初始化
dp[0][0] = (text1_arr[0] == text2_arr[0]) ? 1 : 0;
for (int i = 1; i < n; i++) { // 第一行
dp[0][i] = (text1_arr[0] == text2_arr[i]) ? 1 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) { // 第一列
dp[i][0] = (text1_arr[i] == text2_arr[0]) ? 1 : dp[i - 1][0];
}
// 从前往后递推
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
if (text1_arr[i] == text2_arr[j]) {
dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
}
}
}
return dp[m - 1][n - 1];
}
}
将 dp 数组的大小定义为 m+1 * n+1更方便，可以免去初始化的麻烦。
注意因为是求子序列，初始化的时候就得利用递推式进行初始化。
72. 编辑距离#
class Solution {
public static int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j]表示word1[0, i-1]转换成word2[0, j-1]的最少操作数
int[][] dp = new int[m + 1][n + 1];
// 初始化
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
// 递推
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
int a = dp[i - 1][j - 1];
int b = dp[i - 1][j] + 1;
int c = dp[i][j - 1] + 1;
if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
a = a + 1;
}
dp[i][j] = Math.min(a, Math.min(b, c));
}
}
return dp[m][n];
}
}
技巧#
136. 只出现一次的数字#
class Solution {
public int singleNumber(int[] nums) {
// a ^ a = 0
// 0 ^ a = a
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
res = res ^ nums[i];
}
return res;
}
}
在 java 中，进行异或运算（XOR）只需要使用 ^ 运算符即可。
169. 多数元素#
class Solution {
public int majorityElement(int[] nums) {
int candidate = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
}
if (candidate == nums[i]) {
count++;
} else {
count--;
}
}
return candidate;
}
}
参考：多数投票算法
75. 颜色分类#
先复习一下堆排序：
class Solution {
public void sortColors(int[] nums) {
HEAP_SORT(nums);
}
static int HEAP_SIZE;
public static void MAX_HEAPIFY(int[] nums, int i) {
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left >= HEAP_SIZE) {
left = i;
}
if (right >= HEAP_SIZE) {
right = i;
}
int max_index = (nums[i] > nums[left]) ? i : left;
max_index = (nums[max_index] > nums[right]) ? max_index : right;
if (max_index != i) {
int tmp = nums[i];
nums[i] = nums[max_index];
nums[max_index] = tmp;
MAX_HEAPIFY(nums, max_index);
}
}
public static void HEAP_BUILD(int[] nums) {
HEAP_SIZE = nums.length;
int leaf_count = (HEAP_SIZE + 1) / 2;
// 从第一个非叶子节点倒序遍历
for (int i = HEAP_SIZE - leaf_count - 1; i >= 0; i--) {
MAX_HEAPIFY(nums, i);
}
}
public static void HEAP_SORT(int[] nums) {
HEAP_BUILD(nums);
while (HEAP_SIZE > 0) {
int tmp = nums[0];
nums[0] = nums[HEAP_SIZE - 1];
nums[HEAP_SIZE - 1] = tmp;
HEAP_SIZE--;
MAX_HEAPIFY(nums, 0);
}
}
}
堆排序的时间复杂度：
- MAX-HEAPIFY 过程：其时间复杂度为 O (lgn), 它是维护最大堆性质的关键。
- BUILD-MAX-HEAP 过程：具有线性时间复杂度，功能是从无序的输入数据数组中构造一个最大堆。
- HEAPSORT 过程：其时间复杂度为 O (nlgn), 功能是对一个数组进行原址排序。
- MAX-HEAP-INSERT、 HEAP-EXTRACT-MAX、 HEAP-INCREASE-KEY 和 HEAP-MAXIMUM 过程：时间复杂度为 O (lgn), 功能是利用堆实现一个优先队列。
单指针法，用指针指示头部（左侧已排好序的部分），进行两次遍历，第一次将所有 0 移到左侧，第二次将所有 1 移到 0 的后面。
双指针法，一次遍历，两个指针，分别用来交换 0 和 1，注意模拟，其实真的感觉没啥必要 =）
31. 下一个排列#
class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2;
// Step 1: 从右往左找到第一个递减的元素
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// Step 2: 如果找到了这样的i，找到第一个比nums[i]大的元素
if (i >= 0) {
int j = n - 1;
while (nums[j] <= nums[i]) {
j--;
}
// Step 3: 交换nums[i]和nums[j]
swap(nums, i, j);
}
// Step 4: 将i之后的元素反转
reverse(nums, i + 1, n - 1);
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}
思路：
- 从右往左找到第一个位置
i，使得nums[i] < nums[i+1]。如果不存在这样的i，则说明当前是最后一个排列，直接将数组反转，得到最小的排列。 - 找到这个位置
i后，再从右往左找到第一个j，使得nums[j] > nums[i]，然后交换nums[i]和nums[j]。 - 最后，将
i+1之后的元素反转，使得这一段变为升序排列。(因为交换之后右侧元素仍然且必然是递减的)
例如： 0, 1, 4, 3, 2
又例如： 2, 3, 1 -> 3, 1, 2
来个力扣官解的说明：
我们需要将一个左边的「较小数」与一个右边的「较大数」交换，以能够让当前排列变大，从而得到下一个排列。
同时我们要让这个「较小数」尽量靠右，而「较大数」尽可能小。当交换完成后，「较大数」右边的数需要按照升序重新排列。这样可以在保证新排列大于原来排列的情况下，使变大的幅度尽可能小。
287. 寻找重复数#
使用解环形链表的思路解题，快慢指针法：
class Solution {
public int findDuplicate(int[] nums) {
// 使用Floyd判圈算法
int slow = 0;
int fast = 0;
// 第一次相遇：寻找环的相遇点
do {
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
// 第二次相遇：从头开始，寻找环的入口（重复的数字）
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
// 返回重复的数字
return slow;
}
}
思路：
- 使用快慢指针（Floyd 判圈算法）来找到环的交点。
- 当两个指针相遇后，将其中一个指针重新指向数组开头，继续同时移动两个指针，每次移动一步，直到它们再次相遇。相遇点即为重复的数字。
End =)