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;
}
}