LeetCode 熱題 100：https://leetcode.cn/studyplan/top-100-liked/

---

---

一、哈希

1. 兩數(shù)之和

思路：設(shè)置一個(gè) map 容器，用于存儲(chǔ)當(dāng)前元素和索引。遍歷時(shí)一邊將數(shù)據(jù)存入 map，一邊比從map中查找滿足加和等于 target 的另一個(gè)元素。

class Solution {/*** 輸入：nums = [2,7,11,15], target = 9* 輸出：[0,1]* 解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。*/public int[] twoSum(int[] nums, int target) {Map<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[] {};}
}

---

49. 字母異位詞分組

思路：設(shè)置一個(gè) map 容器，key是排序后的字符組合，value是字母異位詞的集合。

class Solution {/*** 輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]* 輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]*/public List<List<String>> groupAnagrams(String[] strs) {Map<String, List<String>> map = new HashMap<>();for (String str : strs) {char[] chars = str.toCharArray();Arrays.sort(chars);String sortStr = Arrays.toString(chars);// 如果存在key，即：new String(chars)，那么返回對(duì)應(yīng)的 value；// 否則將執(zhí)行先初始化 key：new String(chars)，value: new ArrayList<>()，然后在返回value。map.computeIfAbsent(new String(chars), s -> new ArrayList<>()).add(str);}return new ArrayList<>(map.values());}
}

---

128. 最長(zhǎng)連續(xù)序列

思路：因?yàn)轭}目要求O(n)的時(shí)間復(fù)雜度，因此使用set對(duì)數(shù)組進(jìn)行轉(zhuǎn)存，并利用滑動(dòng)窗口一次遍歷即可得出連續(xù)序列的最長(zhǎng)長(zhǎng)度。

class Solution {/*** 輸入：nums = [100,4,200,1,3,2]* 輸出：4* 解釋：最長(zhǎng)數(shù)字連續(xù)序列是 [1, 2, 3, 4]。它的長(zhǎng)度為 4。*/public int longestConsecutive(int[] nums) {if (nums.length == 0) {return 0;}Set<Integer> set = new TreeSet<>();for (int num : nums) {set.add(num);}int co = 0;for (Integer num : set) {nums[co++] = num;}return sliderWindow(nums);}private int sliderWindow(int[] nums) {int left = 0;int len = nums.length;int max = 1;for (int right = 1; right < len; right++) {if (nums[right] - nums[right - 1] != 1) {left = right;}max = Math.max(right - left + 1, max);}return max;}
}

---

二、雙指針

283. 移動(dòng)零

class Solution {/*** 輸入: nums = [0,1,0,3,12]* 輸出: [1,3,12,0,0]*/public void moveZeroes(int[] nums) {int j = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {nums[j++] = nums[i];}}for (; j < nums.length; j++) {nums[j] = 0;}}
}

---

11. 盛水最多的容器

思路：定義雙指針，分別指向數(shù)組的最左邊和最右邊，每次往里移動(dòng)較短的元素的指針。這里解釋為什么要移動(dòng)短的？
根據(jù)木桶原理，整個(gè)木桶盛水的最大體積取決于小的那一段木板。如果移動(dòng)短的指針，體積可能變大，也可能不變，還有可能變小。但如果移動(dòng)長(zhǎng)的指針，體積一定會(huì)變小。因此在指針不斷往里移動(dòng)的同時(shí)，移動(dòng)指向較短元素的指針能得出盛水最大的容量。

class Solution {public int maxArea(int[] height) {int len = height.length;int left = 0;int right = len - 1;int maxArea = 0;// 面積 = 短板 * 底邊// 向內(nèi)移動(dòng)短板，水槽短板 min(h[i], h[j]) 可能變大，下個(gè)水槽面積可能增大// 向內(nèi)移動(dòng)長(zhǎng)板，水槽短板 min(h[i], h[j]) 可能變小或不變，下個(gè)水槽面積一定減小（因?yàn)榈走呴L(zhǎng)變小）while (left < right) {maxArea = Math.max(Math.min(height[left], height[right]) * (right - left), maxArea);if (height[left] < height[right]) {left++;} else {right--;}}return maxArea;}
}

---

15. 三數(shù)之和

思路：將數(shù)組排完序后進(jìn)行遍歷，遍歷時(shí)選取當(dāng)前元素的后一個(gè)元素和數(shù)組的最后一個(gè)元素為雙指針。（注意對(duì)重復(fù)元素進(jìn)行去重）

class Solution {/*** 輸入：nums = [-1,0,1,2,-1,-4]* 輸出：[[-1,-1,2],[-1,0,1]]* 解釋：* nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。* nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。* nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。* 不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。* 注意，輸出的順序和三元組的順序并不重要。*/public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = nums.length;Arrays.sort(nums);for (int i = 0; i < len; i++) {if (nums[i] > 0) {break;}if (i != 0 && nums[i] == nums[i - 1]) { // 去除重復(fù)元素continue;}int left = i + 1;int right = len - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum == 0) {res.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) { // 去除重復(fù)元素left++;}while (left < right && nums[right - 1] == nums[right]) {right--;}left++;right--;} else if (sum > 0) {right--;} else {left++;}}}return res;}
}

42. 接雨水（待完成）

---

三、滑動(dòng)窗口

3. 無(wú)重復(fù)字符的最長(zhǎng)子串

思路：定義一個(gè) map 容器， key 存儲(chǔ)字符，value 存儲(chǔ)當(dāng)前字符索引。使用滑動(dòng)窗口計(jì)算最長(zhǎng)字串，當(dāng)窗口內(nèi)存在重復(fù)字符時(shí)，調(diào)整窗口的左邊界，調(diào)整為重復(fù)元素索引的下一位，并且注意左邊界不能向左移動(dòng)。

class Solution {/*** 輸入: s = "abcabcbb"* 輸出: 3 * 解釋: 因?yàn)闊o(wú)重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。*/public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>(); // key：字符，value：當(dāng)前字符索引int len = s.length();int start = 0;int max = 0;for (int end = 0; end < len; end++) {char ch = s.charAt(end);if (map.containsKey(ch)) {start = Math.max(map.get(ch) + 1, start); // 處理 'abba'，如果不用max比較當(dāng)遍歷到最后一個(gè)a時(shí)，start將會(huì)指向第一個(gè)b，即start-end范圍是 bba}map.put(ch, end);max = Math.max(end - start + 1, max);}return max;}
}

---

438. 找到字符串中所有字母異位詞

思路：使用數(shù)組統(tǒng)計(jì)字符串中26個(gè)字符的出現(xiàn)次數(shù)，固定滑動(dòng)窗口大小，并使用 Arrays.equals(...) 方法一邊遍歷一邊比較。

class Solution {/*** 輸入: s = "cbaebabacd", p = "abc"* 輸出: [0,6]* 解釋:* 起始索引等于 0 的子串是 "cba", 它是 "abc" 的異位詞。* 起始索引等于 6 的子串是 "bac", 它是 "abc" 的異位詞。*/public List<Integer> findAnagrams(String s, String p) {List<Integer> res = new ArrayList<>();int sLen = s.length();int pLen = p.length();if (sLen < pLen) {return res;}int[] sWin = new int[26];int[] pWin = new int[26];for (int i = 0; i < pLen; i++) {sWin[s.charAt(i) - 'a']++;pWin[p.charAt(i) - 'a']++;}if (Arrays.equals(sWin, pWin)) {res.add(0);}for (int i = pLen; i < sLen; i++) {sWin[s.charAt(i - pLen) - 'a']--;sWin[s.charAt(i) - 'a']++;if (Arrays.equals(sWin, pWin)) {res.add(i - pLen + 1);}}return res;}
}

---

四、子串

560. 和為 K 的子數(shù)組

思路：首先計(jì)算前綴和，利用前綴和的差值確定子數(shù)組的和是否等于K。
如：下面數(shù)組求子數(shù)組和為 6，pre[4] - pre[1] == 6 就代表：num[1:3] 加和等于 6。

ind	0	1	2	3	4	5	6	7
value	4	1	2	3	0	6	2	4
前綴和 pre	0	4	5	7	10	10	16	18	22

注：這里我們預(yù)留第一個(gè)位置為0，代表索引為 0 的元素前綴和為 0。

class Solution {/*** 輸入：nums = [1,2,3], k = 3* 輸出：2*/public int subarraySum(int[] nums, int k) {int res = 0;int len = nums.length;int[] pre = new int[len + 1];// 計(jì)算前綴和for (int i = 0; i < len; i++) {pre[i + 1] = pre[i] + nums[i];}for (int left = 0; left < len; left++) {for (int right = left; right < len; right++) {if (pre[right + 1] - pre[left] == k) {res++;}}}return res;}
}

上面做法的時(shí)間復(fù)雜度為 $O(n^2)$，因此用哈希表進(jìn)行優(yōu)化。

思路：設(shè)置一個(gè) map 容器用于存儲(chǔ)前綴和以及前綴和的個(gè)數(shù)，當(dāng)計(jì)算前綴和的同時(shí)來(lái)查找是否存在 前綴和 - 目標(biāo)和，如果存在則說(shuō)明存在子數(shù)組和等于 k。如：上述例子中，求子數(shù)組和為 6，當(dāng)遍歷到索引 4 時(shí)前綴和為 10， map 中存在鍵 key=“10-6”=4 {key=4,value=1}，說(shuō)明當(dāng)前元素存在前綴和為 4 的情況。

ind	0	1	2	3	4	5	6	7
value	4	1	2	3	0	6	2	4
累加的前綴和	4	5	7	10	10	16	18	22

class Solution {/*** 輸入：nums = [1,2,3], k = 3* 輸出：2*/public int subarraySum(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<>(); // key：前綴和，value: 前綴和的個(gè)數(shù)int res = 0;map.put(0, 1); // 前綴和為 0 的個(gè)數(shù)有一個(gè)int sum = 0; // 記錄前綴和for (int num : nums) {sum += num;if (map.containsKey(sum - k)) {res += map.get(sum - k);}map.put(sum, map.getOrDefault(sum, 0) + 1);}return res;}
}

---

239. 滑動(dòng)窗口最大值

思路：設(shè)置一個(gè)大頂堆，固定窗口大小，遍歷時(shí)首先清除過(guò)期元素，然后將元素入堆。
值得注意的是，有些比較小的元素由于不在堆頂，不會(huì)立即刪除。但是在后面如果到了堆頂，也會(huì)刪除。

class Solution {/*** 輸入：nums = [1,3,-1,-3,5,3,6,7], k = 3* 輸出：[3,3,5,5,6,7]* 解釋：* 滑動(dòng)窗口的位置                最大值* ---------------               -----* [1  3  -1] -3  5  3  6  7       3*  1 [3  -1  -3] 5  3  6  7       3*  1  3 [-1  -3  5] 3  6  7       5*  1  3  -1 [-3  5  3] 6  7       5*  1  3  -1  -3 [5  3  6] 7       6*  1  3  -1  -3  5 [3  6  7]      7*/public int[] maxSlidingWindow(int[] nums, int k) {PriorityQueue<Elem> heap = new PriorityQueue<>((elem1, elem2) -> elem2.value - elem1.value);// 初始化大頂堆int len = nums.length;int[] res = new int[len - k + 1];for (int i = 0; i < k; i++) {heap.add(new Elem(nums[i], i));}res[0] = heap.element().value;int co = 1;for (int i = k; i < len; i++) {while (!heap.isEmpty() && heap.element().index <= i - k) { // 處理不在窗口的元素// 有些比較小的元素由于不在堆頂，不會(huì)立即刪除。但是在后面如果到了堆頂，也會(huì)刪除// 如：nums = [5,6,-1,-2,3], k = 3// 當(dāng)窗口在[6,-1,-2]時(shí)，5還在堆內(nèi)，但是當(dāng)窗口在[-1,-2,3]時(shí)，會(huì)在堆頂被刪除heap.remove();}heap.add(new Elem(nums[i], i));res[co++] = heap.element().value;}return res;}class Elem {int value;int index;public Elem() {}public Elem(int value, int index) {this.value = value;this.index = index;}}
}

---

76. 最小覆蓋子串

思路：分別設(shè)置兩個(gè)數(shù)組用來(lái)存儲(chǔ)字符的出現(xiàn)次數(shù)，利用滑動(dòng)窗口邊一邊右移一邊檢查模式串是否被覆蓋。

 class Solution {/*** 輸入：s = "ADOBECODEBANC", t = "ABC"* 輸出："BANC"* 解釋：最小覆蓋子串 "BANC" 包含來(lái)自字符串 t 的 'A'、'B' 和 'C'。*/public String minWindow(String s, String t) {if (s.length() < t.length()) {return "";}int[] sChars = new int[128];int[] tChars = new int[128];for (char ch : t.toCharArray()) {tChars[ch]++;}int left = 0;int sLen = s.length();int resLeft = -1;int resRight = sLen;for (int right = 0; right < sLen; right++) {sChars[s.charAt(right)]++;while (left <= right && isCovered(sChars, tChars)) {if (right - left < resRight - resLeft) {resLeft = left;resRight = right;}sChars[s.charAt(left)]--;left++;}}return resLeft == -1 ? "" : s.substring(resLeft, resRight + 1);}private boolean isCovered(int[] sChars, int[] tChars) {for (int i = 'A'; i <= 'Z'; i++) {if (sChars[i] < tChars[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (sChars[i] < tChars[i]) {return false;}}return true;}
}

上面代碼在每次遍歷的時(shí)候都需要檢查子串是否被覆蓋，因此可以考慮設(shè)置兩個(gè)變量 sNum 和 tNum。tNum 用于記錄 t 中不同字符的數(shù)量， sNum 用于記錄 s 指定字符達(dá)到覆蓋 t 的程度數(shù)量。如：當(dāng) s 的子串中如果 ‘a(chǎn)’ 的數(shù)量等于 t 中 ‘a(chǎn)’ 字符的數(shù)量時(shí) sNum + 1，否則不變。

class Solution {/*** 輸入：s = "ADOBECODEBANC", t = "ABC"* 輸出："BANC"* 解釋：最小覆蓋子串 "BANC" 包含來(lái)自字符串 t 的 'A'、'B' 和 'C'。*/public String minWindow(String s, String t) {int[] sChars = new int[128];int[] tChars = new int[128];int sNum = 0; // 記錄 s 中的指定字符數(shù)量達(dá)到覆蓋 t 程度的數(shù)量int tNum = 0; // 記錄 t 中有多少不同字符for (char ch : t.toCharArray()) {if (tChars[ch]++ == 0) {tNum++;}}int len = s.length();int resLeft = -1;int resRight = len;int left = 0;for (int right = 0; right < len; right++) {if (++sChars[s.charAt(right)] == tChars[s.charAt(right)]) {sNum++; // s中的該字符數(shù)量達(dá)到覆蓋 t 中該字符的程度}while (left <= right && sNum == tNum) {if (right - left < resRight - resLeft) { // 更新結(jié)果左右邊界resLeft = left;resRight = right;}if (sChars[s.charAt(left)]-- == tChars[s.charAt(left)]) {sNum--;}left++;}}return resLeft == -1 ? "" : s.substring(resLeft, resRight + 1);}
}

補(bǔ)充：209. 長(zhǎng)度最小的子數(shù)組

最小覆蓋子串題目類似：209. 長(zhǎng)度最小的子數(shù)組

class Solution {/*** 輸入：target = 7, nums = [2,3,1,2,4,3]* 輸出：2* 解釋：子數(shù)組 [4,3] 是長(zhǎng)度最小且總和大于等于 target 的子數(shù)組。*/public int minSubArrayLen(int target, int[] nums) {int len = nums.length;int sum = 0;int left = 0;int res = len + 1;for (int right = 0; right < len; right++) {sum += nums[right];while (left <= right && sum >= target) {res = Math.min(right - left + 1, res);sum -= nums[left++];}}return res == len + 1 ? 0 : res;}
}

---

五、普通數(shù)組

53. 最大子數(shù)組和

思路：設(shè)置變量 curr 用于記錄子數(shù)組和，遍歷數(shù)組時(shí)，當(dāng)子數(shù)組和大于零時(shí)累加當(dāng)前元素，否則令子數(shù)組和等于當(dāng)前數(shù)組元素。

class Solution {/*** 輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]* 輸出：6* 解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 。*/public int maxSubArray(int[] nums) {int curr = 0;int max = nums[0];for (int i = 0; i < nums.length; i++) {if (curr >= 0) {curr += nums[i];} else {curr = nums[i];}max = Math.max(curr, max);}return max;}
}

---

56. 合并區(qū)間

思路：定義內(nèi)部類用于記錄區(qū)間的左右端點(diǎn)，對(duì)二維數(shù)組按照左端點(diǎn)遞增，左端點(diǎn)相同時(shí)右端點(diǎn)遞增的規(guī)則排序。將數(shù)組第一個(gè)元素加入集合后進(jìn)行遍歷，若發(fā)現(xiàn)當(dāng)前 數(shù)組元素左端點(diǎn)和集合最后一個(gè)元素的左端點(diǎn)相同 或者 集合最后一個(gè)元素的右端點(diǎn)大于數(shù)組的左端點(diǎn)，則將集合的最后一個(gè)元素的右端點(diǎn)進(jìn)行取大處理，否則將數(shù)組元素加入集合。

class Solution {/*** 輸入：intervals = [[1,3],[2,6],[8,10],[15,18]]* 輸出：[[1,6],[8,10],[15,18]]* 解釋：區(qū)間 [1,3] 和 [2,6] 重疊, 將它們合并為 [1,6].*/public int[][] merge(int[][] intervals) {int len = intervals.length;List<Range> list = new ArrayList<>();Arrays.sort(intervals,(range1, range2) -> range1[0] != range2[0] ? range1[0] - range2[0] : range1[1] - range2[1]);list.add(new Range(intervals[0][0], intervals[0][1]));for (int i = 1; i < len; i++) {Range range = list.get(list.size() - 1);if (range.begin == intervals[i][0] || range.end >= intervals[i][0]) {range.end = Math.max(intervals[i][1], range.end); // Max比較大小是為了處理這種情況 [[1,4],[2,3]]} else {list.add(new Range(intervals[i][0], intervals[i][1]));}}int size = list.size();int[][] res = new int[size][2];for (int i = 0; i < size; i++) {res[i][0] = list.get(i).begin;res[i][1] = list.get(i).end;}return res;}class Range {int begin;int end;public Range() {}public Range(int begin, int end) {this.begin = begin;this.end = end;}}
}

---

189. 輪轉(zhuǎn)數(shù)組

思路：先將數(shù)組全部翻轉(zhuǎn)，然后對(duì)前 k 個(gè)元素和其余的元素分別做翻轉(zhuǎn)。

class Solution {/*** 輸入: nums = [1,2,3,4,5,6,7], k = 3* 輸出: [5,6,7,1,2,3,4]* 解釋:* 向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]* 向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]* 向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]*/public void rotate(int[] nums, int k) {int len = nums.length;k %= len;reverseArr(nums, 0, len - 1);reverseArr(nums, 0, k - 1);reverseArr(nums, k, len - 1);}private void reverseArr(int[] nums, int begin, int end) {while (begin < end) {int temp = nums[begin];nums[begin] = nums[end];nums[end] = temp;begin++;end--;}}
}

---

238. 除自身以外數(shù)組的乘積

思路：將數(shù)組元素累乘以后逐個(gè)相除可能會(huì)存在除零異常。因此，考慮分別求當(dāng)前元素的左側(cè)累乘積和右側(cè)累乘積，最后再將兩側(cè)數(shù)組做累乘。

class Solution {/*** 輸入: nums = [1,2,3,4]* 輸出: [24,12,8,6]*/public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];int[] right = new int[len];int[] res = new int[len];left[0] = 1;right[len - 1] = 1;// nums: [1, 2, 3, 4]// left: [1, 1, 2, 6]// right: [24,12,4, 1]for (int i = 1; i < len; i++) {left[i] = nums[i - 1] * left[i - 1];}for (int i = len - 2; i >= 0; i--) {right[i] = nums[i + 1] * right[i + 1];}for (int i = 0; i < len; i++) {res[i] = left[i] * right[i];}return res;}
}

---

41. 缺失的第一個(gè)正數(shù)（待完成）

---

六、矩陣

73. 矩陣置零

思路：設(shè)置矩陣行列大小的兩個(gè)數(shù)組，用于對(duì)矩陣元素為零的行列進(jìn)行標(biāo)記。再次遍歷矩陣，然后將標(biāo)記過(guò)的行和列進(jìn)行置零。

class Solution {public void setZeroes(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;int[] rows = new int[m];int[] columns = new int[n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (matrix[i][j] == 0) {rows[i] = 1;columns[j] = 1;}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (rows[i] == 1 || columns[j] == 1) {matrix[i][j] = 0;}}}}
}

---

54. 螺旋矩陣

思路：初始化矩陣的上下左右四個(gè)邊界，按照 “從左向右、從上向下、從右向左、從下向上” 四個(gè)方向循環(huán)打印，每次都需要更新邊界，并判斷結(jié)束條件。

class Solution {public List<Integer> spiralOrder(int[][] matrix) {List<Integer> res = new ArrayList<>();int left = 0;int right = matrix[0].length - 1;int up = 0;int down = matrix.length - 1;while (true) {for (int i = left; i <= right; i++) {res.add(matrix[up][i]);}if (++up > down) {break;}for (int i = up; i <= down; i++) {res.add(matrix[i][right]);}if (left > --right) {break;}for (int i = right; i >= left; i--) {res.add(matrix[down][i]);}if (up > --down) {break;}for (int i = down; i >= up; i--) {res.add(matrix[i][left]);}if (++left > right) {break;}}return res;}
}

---

48. 旋轉(zhuǎn)圖像

思路：先將矩陣轉(zhuǎn)置，然后將左右對(duì)稱的兩列互換元素，即可達(dá)到順時(shí)針旋轉(zhuǎn) 90 度的效果。

class Solution {public void rotate(int[][] matrix) {int n = matrix.length;for (int i = 0; i < n; i++) { // 矩陣轉(zhuǎn)置for (int j = i + 1; j < n; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}for (int i = 0; i < n; i++) { // 左右對(duì)稱的兩列互換for (int j = 0; j < n / 2; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[i][n - 1 - j];matrix[i][n - 1 - j] = temp;}}}
}

---

240. 搜索二維矩陣 II

思路：利用 “每行的所有元素從左到右升序排列，每列的所有元素從上到下升序排列” 這個(gè)特點(diǎn)，從右上角開(kāi)始向左下角的方向查找，當(dāng)元素大于目標(biāo)元素，這一列下面的元素都大于目標(biāo)元素；當(dāng)元素小于目標(biāo)元素，這一行前面的元素都小于目標(biāo)元素。

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int x = 0; // 右上角int y = n - 1;while (x < m && y >= 0) {if (matrix[x][y] > target) { // 當(dāng)前元素大于target，這一列下面的元素都大于targety--;} else if (matrix[x][y] < target) { // 當(dāng)前元素小于target，這一行前面的元素都小于targetx++;} else {return true;}}return false;}
}

也可以從左下角開(kāi)始查找，代碼如下：

class Solution {public boolean searchMatrix(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int x = m - 1; // 左下角int y = 0;while (x >= 0 && y < n) {if (matrix[x][y] > target) { // 當(dāng)前元素大于target，這一行后面的元素都大于targetx--;} else if (matrix[x][y] < target) { // 當(dāng)前元素小于target，這一列上面的元素都小于targety++;} else {return true;}}return false;}
}

---

七、鏈表

160. 相交鏈表

思路：利用乘法交換律，設(shè)兩個(gè)鏈表相交前分別有 A B 個(gè)節(jié)點(diǎn)，相交部分有 C 個(gè)節(jié)點(diǎn)，那么 A+C+B=B+C+A。設(shè)置兩個(gè)指針?lè)謩e指向兩個(gè)鏈表的頭部，同時(shí)向后移動(dòng)。當(dāng)其中一個(gè)指針移動(dòng)到結(jié)尾時(shí)，則轉(zhuǎn)向指向另一個(gè)鏈表的頭部，另一個(gè)指針步驟同上，最終兩個(gè)指針會(huì)在相交處會(huì)面。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pa = headA;ListNode pb = headB;while (pa != pb) {pa = pa == null ? headB : pa.next;pb = pb == null ? headA : pb.next;}return pa;}
}

注：如果兩個(gè)鏈表不相交，也適合以上規(guī)律，最終兩個(gè)指針都會(huì)指向空，也會(huì)跳出循環(huán)。

---

206. 反轉(zhuǎn)鏈表

思路：鏈表頭插法。

/*** 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; }* }*/
class Solution {public ListNode reverseList(ListNode head) {ListNode pre = new ListNode();ListNode p;p = head;pre.next = null;while(p != null){ListNode temp = p.next;p.next = pre.next;pre.next = p;p = temp;}return pre.next;}
}

---

234. 回文鏈表

思路：本地的實(shí)現(xiàn)很多，這里采用棧進(jìn)行輔助判斷回文。

/*** 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; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {Deque<ListNode> stack = new LinkedList<>();ListNode p = head;while (p != null) {stack.push(p);p = p.next;}while (head != null) {p = stack.pop();if (p.val != head.val) {return false;}head = head.next;}return true;}
}

---

141. 環(huán)形鏈表

思路1：使用 hash 表進(jìn)行輔助判斷是否存在環(huán)。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode p = head;while (p != null) {if (set.contains(p)) {return true;}set.add(p);p = p.next;}return false;}
}

思路2：使用快慢指針，slow 每次向前走一步，fast 每次向前走兩步。
① 當(dāng)存在環(huán)時(shí)，fast 由于走得快，會(huì)發(fā)生扣圈的情況，且最終與 slow 相遇。
② 當(dāng)不存在環(huán)時(shí)，fast 可能在某次循環(huán)后，發(fā)生當(dāng)前位置為空，或下一位置為空的兩種情況，當(dāng)然由于走的快，最終會(huì)返回 false。
總之，循環(huán)的結(jié)束條件，要么出現(xiàn)環(huán) slow == fast，要么 fast 先一步為空。下面列舉兩種實(shí)現(xiàn)方式：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while (true) {if (fast == null || fast.next == null) {return false;}slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}}
}// 推薦
public class Solution {public boolean hasCycle(ListNode head) {if (head == null) {return false;}ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {return true;}}return false;}
}

---

142. 環(huán)形鏈表 II

思路1：使用 hash 表。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> set = new HashSet<>();ListNode p = head;while (p != null) {if (set.contains(p)) {return p;}set.add(p);p = p.next;}return null;}
}

思路2：使用快慢指針，思路如下：

• 設(shè) fast 每次走兩個(gè)節(jié)點(diǎn)， slow 每次走一個(gè)節(jié)點(diǎn)。環(huán)外有 a 個(gè)結(jié)點(diǎn)，環(huán)內(nèi)有 b 個(gè)結(jié)點(diǎn)。
• 第一次相遇時(shí)，fast 走了 f 步，slow 走了 s 步。
  ① f = 2s
  ② f = s + nb 表示 f 比 s 多走了 n*b 步，即 n 圈。這樣表示的原因在于扣圈。
  化簡(jiǎn)得：f = 2nb, s = nb，n 代表扣圈的次數(shù)，可能等于1,2,3,…
• 設(shè)剛開(kāi)始 slow 指針從開(kāi)始到環(huán)的入口要走 k 步：k = a + tb，t 代表在環(huán)中循環(huán)的次數(shù)，可能等于0,1,2,3,…。因此當(dāng)發(fā)生第一次相遇時(shí)，再走 a 步即可重新回到入環(huán)的起點(diǎn)。

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if (head == null) {return null;}ListNode slow = head;ListNode fast = head;while (fast.next != null && fast.next.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast) {fast = head; // 令 fast 指針指向鏈表頭部break;}}if (fast.next == null || fast.next.next == null) {return null;}while (slow != fast) {slow = slow.next;fast = fast.next;}return fast;}
}

---

21. 合并兩個(gè)有序鏈表

思路：設(shè)置兩個(gè)指針，分別指向鏈表頭部，逐個(gè)比較向后迭代即可。

/*** 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; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 = list1;ListNode p2 = list2;ListNode pre = new ListNode();ListNode p = pre;while (p1 != null && p2 != null) {if (p1.val < p2.val) {p.next = p1;p = p1;p1 = p1.next;} else {p.next = p2;p = p2;p2 = p2.next;}}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return pre.next;}
}

---

2. 兩數(shù)相加

思路：設(shè)置兩個(gè)指針和進(jìn)位標(biāo)志，逐個(gè)向后相加迭代即可。

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807

/*** 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; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode pre = new ListNode();ListNode p = pre;ListNode p1 = l1;ListNode p2 = l2;int sign = 0;int sum;while (p1 != null || p2 != null) {if (p1 != null && p2 != null) {sum = p1.val + p2.val + sign;p1 = p1.next;p2 = p2.next;} else if (p1 != null) {sum = p1.val + sign;p1 = p1.next;} else {sum = p2.val + sign;p2 = p2.next;}p.next = new ListNode(sum % 10);p = p.next;sign = sum / 10;}if (sign != 0) {p.next = new ListNode(sign);}return pre.next;}
}

---

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

思路：讓前面的指針先移動(dòng) n 步，之后前后指針共同移動(dòng)直到前面的指針到尾部為止。

/*** 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; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre = new ListNode();pre.next = head;ListNode p = pre;ListNode q = pre;int co = 0;while (p.next != null) {if (++co > n) {q = q.next;}p = p.next;}q.next = q.next.next;return pre.next;}
}

---

24. 兩兩交換鏈表中的節(jié)點(diǎn)

思路：鏈表節(jié)點(diǎn)兩兩交換位置，逐個(gè)向后迭代。

/*** 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; }* }*/
class Solution {public ListNode swapPairs(ListNode head) {ListNode pre = new ListNode(0);pre.next = head;ListNode p = head;ListNode q = pre;while (p != null && p.next != null) {ListNode temp = p.next.next;q.next = p.next;q.next.next = p;p.next = null;q = p;p = temp;}if (p != null) {q.next = p;}return pre.next;}
}

---

25. K 個(gè)一組翻轉(zhuǎn)鏈表（待完成）

---

138. 隨機(jī)鏈表的復(fù)制

思路：題意是讓我們把下面的隨機(jī)鏈表做整體復(fù)制，這里我們?cè)O(shè)置一個(gè) map 容器，用于對(duì)應(yīng)原始節(jié)點(diǎn)和復(fù)制的節(jié)點(diǎn)，存儲(chǔ)以后再處理 next 指針和 random 指針。

/*
class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}
}
*/
class Solution {public Node copyRandomList(Node head) {if (head == null) {return null;}Map<Node, Node> map = new HashMap<>();Node p = head;while (p != null) {Node copyNode = new Node(p.val);map.put(p, copyNode);p = p.next;}p = head;while (p != null) {Node copyNode = map.get(p);if (p.random != null) {copyNode.random = map.get(p.random);}if (p.next != null) {copyNode.next = map.get(p.next);}p = p.next;}return map.get(head);}
}

---

148. 排序鏈表

思路：這里我們采用堆結(jié)構(gòu)輔助鏈表排序，將大頂堆構(gòu)造好以后，一邊出堆一邊利用頭插法對(duì)鏈表結(jié)構(gòu)進(jìn)行重塑。

/*** 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; }* }*/
class Solution {public ListNode sortList(ListNode head) {PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> b.val-a.val); // 大頂堆while(head != null){queue.offer(head); // 從堆底插入head = head.next;}ListNode pre = new ListNode(0);while(!queue.isEmpty()){ListNode p = queue.poll(); // 出隊(duì)列并調(diào)整堆p.next = pre.next; // 頭插法倒序pre.next = p;}return pre.next;}
}

---

23. 合并 K 個(gè)升序鏈表

思路：K 個(gè)有序鏈表重復(fù)調(diào)用兩個(gè)有序鏈表的算法。

/*** 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; }* }*/
class Solution {/*** 輸入：lists = [[1,4,5],[1,3,4],[2,6]]* 輸出：[1,1,2,3,4,4,5,6]*/public ListNode mergeKLists(ListNode[] lists) {int len = lists.length;ListNode pre = null;      for (int i = 0; i < len; i++) {pre = mergeTwoLists(pre, lists[i]);}return pre;}private ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode p1 = list1;ListNode p2 = list2;ListNode pre = new ListNode();ListNode p = pre;while (p1 != null && p2 != null) {if (p1.val < p2.val) {p.next = p1;p = p1;p1 = p1.next;} else {p.next = p2;p = p2;p2 = p2.next;}}if (p1 != null) {p.next = p1;}if (p2 != null) {p.next = p2;}return pre.next;}
}

---

146. LRU 緩存

輸入：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出：
[null, null, null, 1, null, -1, null, -1, 3, 4]
解釋：

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); ?// 緩存是 {1=1}
lRUCache.put(2, 2); ?// 緩存是 {1=1, 2=2}
lRUCache.get(1); ??// 返回 1
lRUCache.put(3, 3); ?// 該操作會(huì)使得關(guān)鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2); ??// 返回 -1 (未找到)
lRUCache.put(4, 4); ?// 該操作會(huì)使得關(guān)鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1); ??// 返回 -1 (未找到)
lRUCache.get(3); ??// 返回 3
lRUCache.get(4); ??// 返回 4

思路：參考靈神的思路，想象有一摞書(shū)。
get：時(shí)將一本書(shū)(key) 抽出來(lái)，放在最上面。
put：放入一本新書(shū)，如果已經(jīng)有這本書(shū)(key)，把他抽出來(lái)放在最上面，并替換它的 value。如果沒(méi)有這本書(shū)(key)，就放在最上面。如果超出了 capacity 本書(shū)，就把最下面的書(shū)移除。

題目要求 get 和 put 都是 O(1) 的時(shí)間復(fù)雜度，因此考慮雙向鏈表實(shí)現(xiàn)。

class LRUCache {class Node {int key, value;Node prev, next;public Node(int key, int value) {this.key = key;this.value = value;}}Map<Integer, Node> map;Node dummy;int capacity;public LRUCache(int capacity) {map = new HashMap<>();dummy = new Node(0, 0); // 頭結(jié)點(diǎn)this.capacity = capacity;dummy.next = dummy;dummy.prev = dummy;}public int get(int key) {Node node = getNode(key);return node != null ? node.value : -1;}public void put(int key, int value) {Node node = getNode(key);if (node != null) {node.value = value; // 如果存在，則在getRoot方法里面已經(jīng)放到了頭部return;}node = new Node(key, value);map.put(key, node);pushFirst(node); // 放在鏈表頭部if (map.size() > capacity) {map.remove(dummy.prev.key);remove(dummy.prev);}}private Node getNode(int key) {if (!map.containsKey(key)) {return null;}Node node = map.get(key);remove(node); // 刪除舊節(jié)點(diǎn)pushFirst(node); // 將新節(jié)點(diǎn)加到鏈表頭部return node;}private void pushFirst(Node node) {node.next = dummy.next;node.prev = dummy;dummy.next.prev = node;dummy.next = node;}private void remove(Node node) {node.prev.next = node.next;node.next.prev = node.prev;}
}
/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/