CodeTop:
頻率50+網上的都窮啊一邊
1.反轉連結清單(遞歸)
給你單連結清單的頭節點 head ，請你反轉連結清單，并傳回反轉後的連結清單。
示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
leetcode版本:
class Solution{
public ListNode rerverseListNode(ListNode head){
if(head ==null&& head.next == null){
return head;
}
ListNode p = rerverseListNode(head.next);
head.next.next = head;
head.next = null;
}
return p;
} 面試(位元組跳動):
實作一個大的倆單連結清單的減法:
單連結清單自己定義自己寫
:
//singly-linked list.
//{1,ListNode1} -> {2,ListNode2}
public class ListNode(ListNode node){
int val;
ListNode node;
public ListNode(){}
public ListNode(int val){
this.val = val;
}
public ListNode(int val,ListNode next){
this.val = val;
this.next = next;
}
}
/**
* 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; }
* }
*/ 2. 無重複字元的最長子串
(滑動視窗模闆)畫圖
給定一個字元串 s ，請你找出其中不含有重複字元的 最長子串 的長度。
示例 1:
輸入: s = "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。
示例 2:
輸入: s = "bbbbb"
輸出: 1
解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。
示例 3:
輸入: s = "pwwkew"
輸出: 3
解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。
請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。
示例 4:
輸入: s = ""
輸出: 0
package test;
import com.sun.xml.internal.fastinfoset.tools.XML_SAX_StAX_FI;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
/**
* Created with IntelliJ IDEA.
*
* @Author: 張馳
* @Date: 2021/09/08/14:19
* @Description: 三尺秋水塵不染
*/
public class Main {
static int max ,start,left;
static HashMap<Character,Integer> hashMap = new HashMap<Character,Integer>();
public static int lengthOfLongestSubstring(String s){
if (s.length() == 0){
return 0;
}
for (int i = 0;i < s.length(); i++){
if(hashMap.containsKey(s.charAt(i))){
left = Math.max(left,hashMap.get(s.charAt(i)));
}
hashMap.put(s.charAt(i),i);
max = Math.max(max,i-left);
}
return max;
}
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
String s = bufferedReader.readLine();
StringBuilder sb = new StringBuilder(s);
String str1 = sb.substring(1,s.length()-1);
// String s1 = bufferedReader.readLine();
// StringBuilder sb1 = new StringBuilder(s);
// String str2 = sb.substring(1,s.length()-1);
System.out.println(str1);
System.out.println(lengthOfLongestSubstring(str1));
}
}
215. 數組中的第K個最大元素
快排,堆排
難度中等1285
給定整數數組
nums
和整數
k
，請傳回數組中第
**k**
個最大的元素。
請注意，你需要找的是數組排序後的第
k
個最大的元素，而不是第
k
個不同的元素。
輸入: [3,2,1,5,6,4] 和 k = 2
輸出: 5 輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4
輸出: 4 25. K 個一組翻轉連結清單
重點在優化長度直接模拟就好
難度困難1297
給你一個連結清單，每 k 個節點一組進行翻轉，請你傳回翻轉後的連結清單。
k 是一個正整數，它的值小于或等于連結清單的長度。
如果節點總數不是 k 的整數倍，那麼請将最後剩餘的節點保持原有順序。
進階：
- 你可以設計一個隻使用常數額外空間的算法來解決此問題嗎？
- 你不能隻是單純的改變節點内部的值，而是需要實際進行節點交換。
輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5] 
輸入：head = [1,2,3,4,5], k = 3輸出：[3,2,1,4,5] 輸入：head = [1,2,3,4,5], k = 1輸出：[1,2,3,4,5] 示例 4：
輸入：head = [1], k = 1輸出：[1] 提示：
- 清單中節點的數量在範圍
sz
-
1 <= sz <= 5000
-
0 <= Node.val <= 1000
-
1 <= k <= sz
143. 重排連結清單
難度中等669
給定一個單連結清單
L
的頭節點
head
，單連結清單
L
表示為：
L0 → L1 → … → Ln-1 → Ln
請将其重新排列後變為：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。
輸入: head = [1,2,3,4]輸出: [1,4,2,3] 輸入: head = [1,2,3,4,5]輸出: [1,5,2,4,3] //方法1 arraylist 模拟法:/** * 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 void reorderList(ListNode head) { List<Interger> list = new ArrayList<>(); ListNode node = head; while(node != null){ list.add(node); node = node.next; } int left = 0,right = list.size() - 1; while(left < right){ //最後的加入 list.get(left).next = list.get(right); //縮小界限 left++; if(left == right ){ break; } // 縮小界限後的加入 list.get(right).next = list.get(left); right--; } list.get(left).next = null; }} /** * 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; } * } *///方法2:連結清單二分在街上:class Solution { public void reorderList(ListNode head) { if (head == null || head.next == null || head.next.next == null) { return; } //找中點，連結清單分成兩個 ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode newHead = slow.next; slow.next = null; //第二個連結清單倒置 newHead = reverseList(newHead); //連結清單節點依次連接配接 while (newHead != null) { ListNode temp = newHead.next; newHead.next = head.next; head.next = newHead; head = newHead.next; newHead = temp; }}private ListNode reverseList(ListNode head) { if (head == null) { return null; } ListNode tail = head; head = head.next; tail.next = null; while (head != null) { ListNode temp = head.next; head.next = tail; tail = head; head = temp; } return tail;}} 5. 最長回文子串
難度中等4109
給你一個字元串
s
，找到
s
中最長的回文子串。
輸入：s = "babad"輸出："bab"解釋："aba" 同樣是符合題意的答案。 輸入：s = "cbbd"輸出："bb" 輸入：s = "a"輸出："a" 輸入：s = "ac"輸出："a" //中心擴散法:public class Solution { public String longestPalindrome(String s) { int len = s.length(); if(len < 2){ return s; } //長度和下表就是最長的 int maxLen = 1, int start = 0; char[] array = s.toCharrArray(); }} 15. 三數之和
難度中等3805
給你一個包含
n
個整數的數組
nums
，判斷
nums
中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為
且不重複的三元組。
注意：答案中不可以包含重複的三元組。
輸入：nums = [-1,0,1,2,-1,-4]輸出：[[-1,-1,2],[-1,0,1]] 輸入：nums = []輸出：[] 輸入：nums = [0]輸出：[] 排序加雙指針class Solution { public List<List<Integer>> threeSum(int[] nums) { int length = nums.length; Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); //便利 for (int i = 0; i < length; i++) { //特殊條件這個已經有序了,就不要主元後面的 if(nums[i] > 0){ break; } //去重和前一個一樣嗎???i代表主元pivot其他左右指針都要去重 if(i > 0 && nums[i] == nums[i-1]){ continue; } //左右移動指針 //left在pivot後, right是右邊界 int left = i+1,right = length-1; while(left < right){ int sum = nums[i]+ nums[left] +nums[right]; //全部區間大于小于等于 if(sum ==0){ ans.add(Arrays.asList(nums[i],nums[left],nums[right])); //避免重複,政策不同left是忘右走看右邊+1 while (left < right && nums[left] == nums[left+1]) left++; //right往左走-1 while (left < right && nums[right] == nums[right-1]) right--; left++; right--; } else if(sum < 0){ left++;} else if(sum > 0){ right--;} } } return ans;}} 時間複雜度為o(n^2);
141. 環形連結清單
難度簡單1214
給定一個連結清單，判斷連結清單中是否有環。
如果連結清單中有某個節點，可以通過連續跟蹤
next
指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，我們使用整數
pos
來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果
pos
是
-1
，則在該連結清單中沒有環。注意：
pos
不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。
如果連結清單中存在環，則傳回
true
。 否則，傳回
false
。
你能用 O(1)（即，常量）記憶體解決此問題嗎？
輸入：head = [3,2,0,-4], pos = 1輸出：true解釋：連結清單中有一個環，其尾部連接配接到第二個節點。 輸入：head = [1,2], pos = 0輸出：true解釋：連結清單中有一個環，其尾部連接配接到第一個節點。 輸入：head = [1], pos = -1輸出：false解釋：連結清單中沒有環。 21. 合并兩個有序連結清單
難度簡單1931
将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。
輸入：l1 = [1,2,4], l2 = [1,3,4]輸出：[1,1,2,3,4,4] 輸入：l1 = [], l2 = []輸出：[] 輸入：l1 = [], l2 = [0]輸出：[0] package DiGui;/** * Created with IntelliJ IDEA. * * @Author: 張馳 * @Date: 2021/09/26/16:58 * @Description: 三尺秋水塵不染 */public class mergeTwoLists { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; }else if(l2 == null){ return l1; } if(l1.val < l2.val){ l1.next = mergeTwoLists(l1.next,l2); return l1; }else{ l2.next = mergeTwoLists(l1,l2.next); return l2; } } public static void main(String[] args) { } } class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } 102. 二叉樹的層序周遊
難度中等1028
給你一個二叉樹，請你傳回其按 層序周遊 得到的節點值。 （即逐層地，從左到右通路所有節點）。
示例：
二叉樹：
[3,9,20,null,null,15,7]
,
3 / \ 9 20 / \ 15 7 傳回其層序周遊結果：
[ [3], [9,20], [15,7]] package DFSandBFS.TreeNode;import java.util.ArrayList;import java.util.List;/** * Created with IntelliJ IDEA. * * @Author: 張馳 * @Date: 2021/09/26/17:09 * @Description: 三尺秋水塵不染 */public class levelOrder { //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; } } class Solution { public List<List<Integer>> levelOrder(TreeNode root) { //終止條件 if(root == null){ return new ArrayList<List<Integer>>(); } //結果集 List<List<Integer>> ans = new ArrayList(); //層 int index = 0; dfs(index,ans,root); return ans; } public void dfs(int index, List<List<Integer>>ans, TreeNode root){ //終止條件 輸出的數組大小要小于 目前索引的大小+1 if(ans.size() < index + 1 ){ ans.add(new ArrayList<Integer>()) ; } ans.get(index).add(root.val); if(!(root.left == null)){ dfs(index+1,ans,root.left); } if(root.right != null){ dfs(index+1,ans,root.right); } } }} 1162. 地圖分析
難度中等218
你現在手裡有一份大小為 N x N 的 網格
grid
，上面的每個 單元格 都用
和
1
标記好了。其中
代表海洋，
1
代表陸地，請你找出一個海洋單元格，這個海洋單元格到離它最近的陸地單元格的距離是最大的。
我們這裡說的距離是「曼哈頓距離」（ Manhattan Distance）：
(x0, y0)
(x1, y1)
這兩個單元格之間的距離是
|x0 - x1| + |y0 - y1|
如果網格上隻有陸地或者海洋，請傳回
-1
輸入：[[1,0,1],[0,0,0],[1,0,1]]輸出：2解釋： 海洋單元格 (1, 1) 和所有陸地單元格之間的距離都達到最大，最大距離為 2。 輸入：[[1,0,0],[0,0,0],[0,0,0]]輸出：4解釋： 海洋單元格 (2, 2) 和所有陸地單元格之間的距離都達到最大，最大距離為 4。 相信對于Tree的BFS大家都已經輕車熟路了：
要把root節點先入隊，然後再一層一層的無腦周遊就行了。
對于圖的BFS也是一樣滴～ 與Tree的BFS差別如下：
1、tree隻有1個root，而圖可以有多個源點，是以首先需要把多個源點都入隊。
2、tree是有向的是以不需要标志是否通路過，而對于無向圖來說，必須得标志是否通路過！
并且為了防止某個節點多次入隊，需要在入隊之前就将其設定成已通路！
這是一道典型的BFS基礎應用，為什麼這麼說呢？
因為我們隻要先把所有的陸地都入隊，然後從各個陸地同時開始一層一層的向海洋擴散，那麼最後擴散到的海洋就是最遠的海洋！
并且這個海洋肯定是被離他最近的陸地給擴散到的！
下面是擴散的圖示，1表示陸地，0表示海洋。每次擴散的時候會标記相鄰的4個位置的海洋：
你可以想象成你從每個陸地上派了很多支船去踏上偉大航道，踏遍所有的海洋。每當船到了新的海洋，就會分裂成4條新的船，向新的未知海洋前進（通路過的海洋就不去了）。如果船到達了某個未通路過的海洋，那他們是第一個到這片海洋的。很明顯，這麼多船最後通路到的海洋，肯定是離陸地最遠的海洋。
二、代碼實作
自己跑一下就懂了（靠後縮進的都是便于了解的）
package DFSandBFS.GraphBFS;import java.util.ArrayDeque;import java.util.Arrays;/** * Created with IntelliJ IDEA. * * @Author: 張馳 * @Date: 2021/09/26/20:03 * @Description: 三尺秋水塵不染 *//*你現在手裡有一份大小為N x N 的 網格 grid，上面的每個 單元格 都用0和1标記好了。其中0代表海洋，1代表陸地，請你找出一個海洋單元格，這個海洋單元格到離它最近的陸地單元格的距離是最大的。 我們這裡說的距離是「曼哈頓距離」（Manhattan Distance）：(x0, y0) 和(x1, y1)這兩個單元格之間的距離是|x0 - x1| + |y0 - y1|。 如果網格上隻有陸地或者海洋，請傳回-1。 示例 1： 輸入：[[1,0,1],[0,0,0],[1,0,1]] 輸出：2 解釋： 海洋單元格 (1, 1) 和所有陸地單元格之間的距離都達到最大，最大距離為 2。 示例 2： 輸入：[[1,0,0],[0,0,0],[0,0,0]] 輸出：4 解釋： 海洋單元格 (2, 2) 和所有陸地單元格之間的距離都達到最大，最大距離為 4。 */public class maxDistance { public static int maxDistance(int[][] grid) {// 左 右 下 上 int[] dx = {0, 0, -1, 1}; int[] dy = {1, -1, 0, 0}; ArrayDeque<int[]> queue = new ArrayDeque<>(); int m = grid.length, n = grid[0].length ; // 先把所有的陸地都入隊。 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if(grid[i][j] == 1){ //拷貝防止丢失 queue.offer(new int[] {i,j}); } } } // 從各個陸地開始，一圈一圈的周遊海洋，最後周遊到的海洋就是離陸地最遠的海洋。 boolean hasOcean = false; int[] point = null; while(!queue.isEmpty()){ point = queue.poll(); int x = point[0]; int y = point[1]; System.out.println("出隊元素為：X="+x+"Y="+y); System.out.println(); //上下左右便利 （擴散） for (int i = 0; i < 4; i++) { System.out.println("擴散中:...."); System.out.println("0,1,2,3對應左 右 下 上"); System.out.println("第"+i+"次"); System.out.println(); int newX = x + dx[i]; int newY = y + dy[i]; //邊界情況 (越界或者 裡面不是海洋） if(newX < 0 || newX >= m || newY < 0|| newY >= n || grid[newX][newY] != 0){ continue; } grid[newX][newY] = grid[x][y] + 1; hasOcean = true; queue.offer(new int[] {newX,newY}); System.out.println("如對元素為:"+newX+"和"+newY); System.out.println("第 "+i+"次操作原數組為"); for (int[] data:grid ) { System.out.println(Arrays.toString(data)); } System.out.println(); } } if(point == null || !hasOcean){ return -1; } System.out.println("隊列中現在還有"); System.out.println(point[0]+""+point[1]); return grid[point[0]][point[1]] - 1; } public static void main(String[] args) { int[][] grid = {{1,0,1}, {0,0,0}, {1,0,1}}; System.out.println(maxDistance(grid)); }} fucking -算法
樹部分:
1.根據前序周遊和中序周遊的結果還原一棵二叉樹
class Solution { private Map<Integer, Integer> indexMap; public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; } // 前序周遊中的第一個節點就是根節點 int preorder_root = preorder_left; // 在中序周遊中定位根節點 int inorder_root = indexMap.get(preorder[preorder_root]); // 先把根節點建立出來 TreeNode root = new TreeNode(preorder[preorder_root]); // 得到左子樹中的節點數目 int size_left_subtree = inorder_root - inorder_left; // 遞歸地構造左子樹，并連接配接到根節點 // 先序周遊中「從 左邊界+1 開始的 size_left_subtree」個元素就對應了中序周遊中「從 左邊界 開始到 根節點定位-1」的元素 root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); // 遞歸地構造右子樹，并連接配接到根節點 // 先序周遊中「從 左邊界+1+左子樹節點數目 開始到 右邊界」的元素就對應了中序周遊中「從 根節點定位+1 到 右邊界」的元素 root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right); return root; } public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 構造哈希映射，幫助我們快速定位根節點 indexMap = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); }} 2.LeetCode 124 題，難度 Hard，讓你求二叉樹中最大路徑和:
class Solution { int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } public int maxGain(TreeNode node) { if (node == null) { return 0; } // 遞歸計算左右子節點的最大貢獻值 // 隻有在最大貢獻值大于 0 時，才會選取對應子節點 int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); // 節點的最大路徑和取決于該節點的值與該節點的左右子節點的最大貢獻值 int priceNewpath = node.val + leftGain + rightGain; // 更新答案 maxSum = Math.max(maxSum, priceNewpath); // 傳回節點的最大貢獻值 return node.val + Math.max(leftGain, rightGain); }} 修改BTS使之有序:
class Solution { public void recoverTree(TreeNode root) { List<Integer> nums = new ArrayList<Integer>(); inorder(root, nums); int[] swapped = findTwoSwapped(nums); recover(root, 2, swapped[0], swapped[1]); } public void inorder(TreeNode root, List<Integer> nums) { if (root == null) { return; } inorder(root.left, nums); nums.add(root.val); inorder(root.right, nums); } public int[] findTwoSwapped(List<Integer> nums) { int n = nums.size(); int index1 = -1, index2 = -1; for (int i = 0; i < n - 1; ++i) { if (nums.get(i + 1) < nums.get(i)) { index2 = i + 1; if (index1 == -1) { index1 = i; } else { break; } } } int x = nums.get(index1), y = nums.get(index2); return new int[]{x, y}; } public void recover(TreeNode root, int count, int x, int y) { if (root != null) { if (root.val == x || root.val == y) { root.val = root.val == x ? y : x; if (--count == 0) { return; } } recover(root.right, count, x, y); recover(root.left, count, x, y); } }}作者：LeetCode-Solution連結：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 方法二:
class Solution { public void recoverTree(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); TreeNode x = null, y = null, pred = null; while (!stack.isEmpty() || root != null) { while (root != null) { stack.push(root); root = root.left; } root = stack.pop(); if (pred != null && root.val < pred.val) { y = root; if (x == null) { x = pred; } else { break; } } pred = root; root = root.right; } swap(x, y); } public void swap(TreeNode x, TreeNode y) { int tmp = x.val; x.val = y.val; y.val = tmp; }}作者：LeetCode-Solution連結：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 方法3:
class Solution { public void recoverTree(TreeNode root) { TreeNode x = null, y = null, pred = null, predecessor = null; while (root != null) { if (root.left != null) { // predecessor 節點就是目前 root 節點向左走一步，然後一直向右走至無法走為止 predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } // 讓 predecessor 的右指針指向 root，繼續周遊左子樹 if (predecessor.right == null) { predecessor.right = root; root = root.left; } // 說明左子樹已經通路完了，我們需要斷開連結 else { if (pred != null && root.val < pred.val) { y = root; if (x == null) { x = pred; } } pred = root; predecessor.right = null; root = root.right; } } // 如果沒有左孩子，則直接通路右孩子 else { if (pred != null && root.val < pred.val) { y = root; if (x == null) { x = pred; } } pred = root; root = root.right; } } swap(x, y); } public void swap(TreeNode x, TreeNode y) { int tmp = x.val; x.val = y.val; y.val = tmp; }}作者：LeetCode-Solution連結：https://leetcode-cn.com/problems/recover-binary-search-tree/solution/hui-fu-er-cha-sou-suo-shu-by-leetcode-solution/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 二叉樹的便利：
199. 二叉樹的右視圖
難度中等542
給定一個二叉樹的 根節點
root
，想象自己站在它的右側，按照從頂部到底部的順序，傳回從右側所能看到的節點值。
輸入: [1,2,3,null,5,null,4]輸出: [1,3,4] 輸入: [1,null,3]輸出: [1,3] 輸入: []輸出: [] /** * 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; * } * } */class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { int index = 0; dfs(root,index); return ans; } public void dfs(TreeNode root,int index){ //條件 if(root == null){ return; } //添加ans動态的 if(index == ans.size()){ ans.add(root.val); } index += 1; dfs(root.right,index); dfs(root.left,index); }} 層序周遊：
方法1：dfs（）
package DFSandBFS.TreeNode;import java.util.ArrayList;import java.util.List;/** * Created with IntelliJ IDEA. * * @Author: 張馳 * @Date: 2021/09/26/17:09 * @Description: 三尺秋水塵不染 *///二叉樹的層序便利public class levelOrder { //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; } } class Solution { public List<List<Integer>> levelOrder(TreeNode root) { //終止條件 if(root == null){ return new ArrayList<List<Integer>>(); } //結果集 List<List<Integer>> ans = new ArrayList(); //層 int index = 0; dfs(index,ans,root); return ans; } /* * @Method: dfs * @Description: 三尺秋水塵不染 * * @param index * @param ans * @param root * @paramType: [int, java.util.List<java.util.List<java.lang.Integer>>, DFSandBFS.TreeNode.levelOrder.TreeNode] * @return：void * @Author: HaRiJi * @Date: 2021/9/26 */ public void dfs(int index, List<List<Integer>>ans, TreeNode root){ //終止條件 輸出的數組大小要小于 目前索引的大小+1 if(ans.size() < index + 1 ){ ans.add(new ArrayList<Integer>()) ; } //第零層的更節電直接加入 ans.get(index).add(root.val); if(!(root.left == null)){ dfs(index+1,ans,root.left); } if(root.right != null){ dfs(index+1,ans,root.right); } } }} 方法二:bfs(借助隊列實作)
package DFSandBFS.TreeNode;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Deque;import java.util.List;// Created with IntelliJ IDEA.//// @Author: 張馳// @Date: 2021/09/27/9:15// @Description: 三尺秋水塵不染// //*給定一棵二叉樹的根節點root ，請找出該二叉樹中每一層的最大值。 示例1： 輸入: root = [1,3,2,5,3,null,9] 輸出: [1,3,9] 解釋: 1 / \ 3 2 / \ \ 5 3 9 示例2： 輸入: root = [1,2,3] 輸出: [1,3] 解釋: 1 / \ 2 3 示例3： 輸入: root = [1] 輸出: [1] 示例4： 輸入: root = [1,null,2] 輸出: [1,2] 解釋: 1 \ 2 示例5： 輸入: root = [] 輸出: [] */public class largestValues { // 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; } } class Solution{ public List<Integer> largestValues(TreeNode root) { //需要列印結果 List<Integer> ans = new ArrayList<>(); if(root == null){ return new ArrayList<>(); } //隊列是為了 添加 Tree Node ArrayDeque<TreeNode> deque = new ArrayDeque<>(); //将根節點加入deque deque.offer(root); int index = 0; while(!deque.isEmpty()){ //size 為 目前的動态隊列的大小 int size = deque.size(); //維護 最大值 在每次周遊的時候 int max = Integer.MIN_VALUE; for (int i = 0; i < size; i++) { TreeNode node = deque.poll(); max = Math.max(max, node.val); //添加下一層的節點 if( node.left != null){ deque.offer(node.left); } if(node.right != null){ deque.offer(node.right); } } ans.add(max); } return ans; } } } 103. 二叉樹的鋸齒形層序周遊
難度中等526
給定一個二叉樹，傳回其節點值的鋸齒形層序周遊。（即先從左往右，再從右往左進行下一層周遊，以此類推，層與層之間交替進行）。
例如：
給定二叉樹
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7 傳回鋸齒形層序周遊如下：
[ [3], [20,9], [15,7]] shhi用方法二:
/** * 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; * } * } */class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { LinkedList<List<Integer>> result = new LinkedList<>(); if (root == null) { return result; } Queue<TreeNode> q = new LinkedList<>(); q.offer(root); // 開始層序周遊 while (!q.isEmpty()) { int sz = q.size(); LinkedList<Integer> level = new LinkedList<>(); // 存儲每一層的資料 // 周遊每一層中的元素 for (int i = 0; i < sz; i++) { TreeNode cur = q.poll(); if (result.size() % 2 == 0) { level.addLast(cur.val); } else { level.addFirst(cur.val); } // 添加下一層的元素 if (cur.left != null) { q.offer(cur.left); } if (cur.right != null) { q.offer(cur.right); } } // 将每一層添加到結果變量中 result.addLast(level); } return result; }} DP:
72. 編輯距離
難度困難1826
給你兩個單詞
word1
word2
，請你計算出将
word1
轉換成
word2
所使用的最少操作數 。
你可以對一個單詞進行如下三種操作：
- 插入一個字元
- 删除一個字元
- 替換一個字元
輸入：word1 = "horse", word2 = "ros"輸出：3解釋：horse -> rorse (将 'h' 替換為 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e') 輸入：word1 = "intention", word2 = "execution"輸出：5解釋：intention -> inention (删除 't')inention -> enention (将 'i' 替換為 'e')enention -> exention (将 'n' 替換為 'x')exention -> exection (将 'n' 替換為 'c')exection -> execution (插入 'u') 53. 最大子序和
難度簡單3760
給定一個整數數組
nums
，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。
輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]輸出：6解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。 輸入：nums = [1]輸出：1 輸入：nums = [0]輸出：0 輸入：nums = [-1]輸出：-1 示例 5：
輸入：nums = [-100000]輸出：-100000 class Solution { public int maxSubArray(int[] nums) { int ans = nums[0], sum = 0; for(int i : nums){ if(sum > 0){ sum+=i; }else{ sum = i; } //判斷最大 ans = Math.max(sum,ans); } return ans; }} BFS
适合找最短,資料結構就是個數組就可以了或者清單連結清單
我覺得就是dfs(比較優秀,主要是對于結構做判斷的剪枝台費腦子了)(遞歸yyds>?)
我不要你覺得我要我覺得
?/??/???(等差問号疑惑)
模闆
啦啦啦啦啦啦lalalal for 選擇 in 選擇清單: # 做選擇 将該選擇從選擇清單移除 路徑.add(選擇) backtrack(路徑, 選擇清單) # 撤銷選擇 路徑.remove(選擇) 将該選擇再加入選擇清單 重複的
1方法:排序 Arrays.sort(傳入的);2方法: //一樣的話寫一樣的條件 if((i > 0&& nums[i] == nums[i-1]) || nums[i] == 100){ //走就完事不影響 continue; 40. 組合總和 II 46. 全排列 47. 全排列 II 77.組合 78. 子集 90. 子集 II
難度中等1554
給定一個不含重複數字的數組
nums
，傳回其 所有可能的全排列 。你可以 按任意順序 傳回答案。
輸入：nums = [1,2,3]輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 輸入：nums = [0,1]輸出：[[0,1],[1,0]] 輸入：nums = [1]輸出：[[1]] class Solution{ public List<List<Integer>> permute (int[] nums){//1.儲存結果 List<List<Integer>> res = new ArrayList<>(); List<Integer> output = new ArrayList<>(); //将輸入保留在output for(int num : nums){ output.add(num); } int n = nums.length; //參數解讀:有 //長度 輸入數組, 結果結合 起始位置 backtrack(n, output, res, 0); return res; } public void backtrack(int n,List<Integer> output, List<List<Integer>> res,int first){ //首先終止條件 if( first == n){ res.add(new ArratList<Integer>(output)); } for(int i = first; i < n; i++){ Collections.swap(output, first, i); backtrack(n, output,res,first + 1); Collections.swap(output,first,i); } } } (重複的):
難度中等805
給定一個可包含重複數字的序列
nums
，按任意順序 傳回所有不重複的全排列。
輸入：nums = [1,1,2]輸出：[[1,1,2], [1,2,1], [2,1,1]] 輸入：nums = [1,2,3]輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 奇淫技巧:(适用于三位數多了gg)
class Solution{ public List<List<Integer>> permuteUnique(int[] nums){//排序使其有序幫助後續連續看看一樣嗎會不會重複 Arrays.sort(nums); //lists作為結果儲存 List<List<Integer>> Lists = new ArrayList<>(); //調用dfs;(什麼都可以dfs什麼都可以???) dfs(lists , new ArrayList<>(),nums,0); //傳回結果集合 return lists; } //有什麼參數放就行 private void dfs(List<List<Integer>> lists, List<Integer> list, int[] nums, int index){ //遞歸條件為索引到了最後 if(index == nums.length){ //拷貝一份list放入lists; lists.add(new ArrayList<>(list)); return; } for(int i = 0;i < nums.length; i++){ //一樣的話 if((i > 0&& nums[i] == nums[i-1]) || nums[i] == 100){ //走就完事不影響 continue; }else{ int temp = nums[i]; list.add(temp); //省略了标記數組這裡是适合三位的奇淫技巧 nums[i] = 100; dfs(lists,list,nums,index + 1); nums[i] = temp; list.remove(list.size() - 1); } } }} 套路版
class Solution { //标記 boolean[] vis; public List<List<Integer>> permuteUnique(int[] nums) { //結果集合 List<List<Integer>> ans = new ArrayList<List<Integer>>(); //輸入結合 List<Integer> perm = new ArrayList<Integer>(); vis = new boolean[nums.length]; Arrays.sort(nums); backtrack(nums, ans, 0, perm); return ans; } public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) { if (idx == nums.length) { ans.add(new ArrayList<Integer>(perm)); return; } for (int i = 0; i < nums.length; ++i) { //最後是核心代碼 //個人了解為 : //判斷前一個 是否被用過 用過标記為true 最後回溯标記為false 取反 if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) //等價替換為 //if(prem == nums[i] || visited[i]) //如果目前下标已經加入了路徑 或 本次選擇的值和前一次相同，那麼就再選擇一個值 continue; { continue; } perm.add(nums[i]); vis[i] = true; backtrack(nums, ans, idx + 1, perm); vis[i] = false; perm.remove(idx); } }} 39. 組合總和
難度中等1546收藏分享切換為英文接收動态回報
給定一個無重複元素的正整數數組
candidates
和一個正整數
target
，找出
candidates
中所有可以使數字和為目标數
target
的唯一組合。
candidates
中的數字可以無限制重複被選取。如果至少一個所選數字數量不同，則兩種組合是唯一的。
對于給定的輸入，保證和為
target
的唯一組合數少于
150
個。
輸入: candidates = [2,3,6,7], target = 7輸出: [[7],[2,2,3]] 輸入: candidates = [2,3,5], target = 8輸出: [[2,2,2,2],[2,3,3],[3,5]] 輸入: candidates = [2], target = 1輸出: [] class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { //1 List<List<Integer>> ans = new ArrayList<List<Integer>>(); //2 List<Integer> combine = new ArrayList<Integer>(); //3 dfs(candidates, target, ans, combine, 0); //4 return ans; } //dfs public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) { //終止 if (idx == candidates.length) { return; } if (target == 0) { ans.add(new ArrayList<Integer>(combine)); return; } // 直接跳過 dfs(candidates, target, ans, combine, idx + 1); // 選擇目前數 if (target - candidates[idx] >= 0) { //加進來 combine.add(candidates[idx]); //遞歸 dfs(candidates, target - candidates[idx], ans, combine, idx); //禽畜 combine.remove(combine.size() - 1); } }} (重複的)**
難度中等689收藏分享切換為英文接收動态回報
給定一個數組
candidates
和一個目标數
target
candidates
中所有可以使數字和為
target
的組合。
candidates
中的每個數字在每個組合中隻能使用一次。
注意：解集不能包含重複的組合。
輸入: candidates = [10,1,2,7,6,1,5], target = 8,輸出:[[1,1,6],[1,2,5],[1,7],[2,6]] 輸入: candidates = [2,5,2,1,2], target = 5,輸出:[[1,2,2],[5]] class Solution {// List<List<Integer>> ans = new List<List<Integer>>(); List<List<Integer>> ans = new ArrayList<List<Integer>>();// List<int[]> freq = new List<int[]>(); List<int[]> freq = new ArrayList<int[]>(); List<Integer> seq = new ArrayList<Integer>();// List<Integer> seq = new List<Integer>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { //亂序必須先排序 Arrays.sort(candidates); for(int i : candidates){ int size = freq.size(); if(freq.isEmpty() || i != freq.get(size-1)[0]){ freq.add(new int[] {i,1}); } else{ ++freq.get(size-1)[1]; } } dfs(0,target); return ans; } public void dfs(int pos,int rest){ //遞歸條件 if(rest == 0){ ans.add(new ArrayList<Integer>(seq)); return; } if(pos == freq.size() ||rest < freq.get(pos)[0]){ return; } dfs(pos+1,rest); int most = Math.min(rest/freq.get(pos)[0],freq.get(pos)[1]); for(int i = 1;i < most; i++){ seq.add(freq.get(pos)[0]); dfs(pos + 1, rest - 1 *freq.get(pos)[0]); } for (int i = 1; i < most; i++) { seq.remove(seq.size() - 1); } } } 難度中等713收藏分享切換為英文接收動态回報
給定兩個整數
n
k
，傳回範圍
[1, n]
中所有可能的
k
個數的組合。
你可以按 任何順序 傳回答案。
輸入：n = 4, k = 2輸出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4],] 輸入：n = 1, k = 1輸出：[[1]] 多種方法任您
最簡單的:
1.畫圖法:
奇淫技巧:(三個的是以深度為3)
class Solution { private List<List<Integer>> ans = new ArrayList<>(); public List<List<Integer>> combine(int n, int k) { getCombine(n, k, 1, new ArrayList<>()); return ans; } public void getCombine(int n, int k, int start, List<Integer> list) { if(k == 0) { ans.add(new ArrayList<>(list)); return; } for(int i = start;i <= n - k + 1;i++) { list.add(i); getCombine(n, k - 1, i+1, list); list.remove(list.size() - 1); } }} 正常解法:(太熟了都要背下來了)
import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Deque;import java.util.List;public class Solution { public List<List<Integer>> combine(int n, int k) { //1.結果集 List<List<Integer>> res = new ArrayList<>(); //2.傳入的放進來(路徑集合) Deque<Integer> path = new ArrayDeque<>(); //3.邊界情況 if (k <= 0 || n < k) { return res; } // 從 1 開始是題目的設定 //調用dfs dfs(n, k, 1, path, res); //傳回結果集合 return res; } private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) { // 遞歸終止條件是：path 的長度等于 k if (path.size() == k) { res.add(new ArrayList<>(path)); return; }//三部曲有什麼好說的???? // 周遊可能的搜尋起點 for (int i = begin; i <= n; i++) { // 向路徑變量裡添加一個數 path.addLast(i); // 下一輪搜尋，設定的搜尋起點要加 1，因為組合數理不允許出現重複的元素 dfs(n, k, i + 1, path, res); // 重點了解這裡：深度優先周遊有回頭的過程，是以遞歸之前做了什麼，遞歸之後需要做相同操作的逆向操作 path.removeLast(); } }} 要考慮的優化情況:
優化：分析搜尋起點的上界進行剪枝
我們上面的代碼，搜尋起點周遊到 n，即：遞歸函數中有下面的代碼片段：
// 從目前搜尋起點 begin 周遊到 nfor (int i = begin; i <= n; i++) { path.addLast(i); dfs(n, k, i + 1, path, res); path.removeLast();} 事實上，如果 n = 7, k = 4，從 55 開始搜尋就已經沒有意義了，這是因為：即使把 55 選上，後面的數隻有 66 和 77，一共就 33 個候選數，湊不出 44 個數的組合。是以，搜尋起點有上界，這個上界是多少，可以舉幾個例子分析。
分析搜尋起點的上界，其實是在深度優先周遊的過程中剪枝，剪枝可以避免不必要的周遊，剪枝剪得好，可以大幅度節約算法的執行時間。
下面的圖檔綠色部分是剪掉的枝葉，當 n 很大的時候，能少周遊很多結點，節約了時間。
容易知道：搜尋起點和目前還需要選幾個數有關，而目前還需要選幾個數與已經選了幾個數有關，即與 path 的長度相關。我們舉幾個例子分析：
例如：n = 6 ，k = 4。
path.size() == 1 的時候，接下來要選擇 33 個數，搜尋起點最大是 44，最後一個被選的組合是 [4, 5, 6]；
path.size() == 2 的時候，接下來要選擇 22 個數，搜尋起點最大是 55，最後一個被選的組合是 [5, 6]；
path.size() == 3 的時候，接下來要選擇 11 個數，搜尋起點最大是 66，最後一個被選的組合是 [6]；
再如：n = 15 ，k = 4。
path.size() == 1 的時候，接下來要選擇 33 個數，搜尋起點最大是 1313，最後一個被選的是 [13, 14, 15]；
path.size() == 2 的時候，接下來要選擇 22 個數，搜尋起點最大是 1414，最後一個被選的是 [14, 15]；
path.size() == 3 的時候，接下來要選擇 11 個數，搜尋起點最大是 1515，最後一個被選的是 [15]；
可以歸納出：
搜尋起點的上界 + 接下來要選擇的元素個數 - 1 = n
其中，接下來要選擇的元素個數 = k - path.size()，整理得到：
搜尋起點的上界 = n - (k - path.size()) + 1
是以，我們的剪枝過程就是：把 i <= n 改成 i <= n - (k - path.size()) + 1 ：
難度中等1326收藏分享切換為英文接收動态回報
給你一個整數數組
nums
，數組中的元素 互不相同 。傳回該數組所有可能的子集（幂集）。
解集 不能 包含重複的子集。你可以按 任意順序 傳回解集。
輸入：nums = [1,2,3]輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 輸入：nums = [0]輸出：[[],[0]] //太熟了class Solution { public List<List<Integer>> subsets(int[] nums) { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); dfs(0, nums,t,ans); return ans; } public void dfs(int cur, int[] nums, List<Integer> t,List<List<Integer>> ans) { if (cur == nums.length) { ans.add(new ArrayList<Integer>(t)); return; } t.add(nums[cur]); dfs(cur + 1, nums,t,ans); t.remove(t.size() - 1); dfs(cur + 1, nums,t,ans); }} (重複)
難度中等652收藏分享切換為英文接收動态回報
nums
，其中可能包含重複元素，請你傳回該數組所有可能的子集（幂集）。
解集 不能 包含重複的子集。傳回的解集中，子集可以按 任意順序 排列。
輸入：nums = [1,2,2]輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]] 輸入：nums = [0]輸出：[[],[0]] class Solution { List<Integer> t = new ArrayList<Integer>(); List<List<Integer>> ans = new ArrayList<List<Integer>>(); public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); dfs(false, 0, nums); return ans; } public void dfs(boolean choosePre, int cur, int[] nums) { if (cur == nums.length) { ans.add(new ArrayList<Integer>(t)); return; } dfs(false, cur + 1, nums); if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) { return; } t.add(nums[cur]); dfs(true, cur + 1, nums); t.remove(t.size() - 1); }}作者：LeetCode-Solution連結：https://leetcode-cn.com/problems/subsets-ii/solution/zi-ji-ii-by-leetcode-solution-7inq/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 ** 60. 排列序列
難度困難
給出集合
[1,2,3,...,n]
，其所有元素共有
n!
種排列。
按大小順序列出所有排列情況，并一一标記，當
n = 3
時, 所有排列如下：
-
"123"
-
"132"
-
"213"
-
"231"
-
"312"
-
"321"
給定
n
k
，傳回第
k
個排列。
輸入：n = 3, k = 3輸出："213" 輸入：n = 4, k = 9輸出："2314" 輸入：n = 3, k = 1輸出："123" 你知道為什麼這個是困難嗎 ??? 我也不知道 就是有個字典順序有點煩吧 思路: 1.二進制 2.正兒八經的子集樹(剪枝)走下去不可以回頭,和之前的不一樣.這是輸出一個,需要走到底.回溯會錯!!! 3.2太複雜了(官方的數論 誰想得到啊喂! ) 4.逾時太怕了 題解: 1.用字元串 2.瞎寫就可以了(這就不是回溯的題) 3.重點看這裡吧[康托展開與逆展開](https://blog.csdn.net/qq_45458915/article/details/102561188/) 原來困難時針對我來說的 **小醜就是我自己 93. 複原 IP 位址
難度中等682收藏分享切換為英文接收動态回報
給定一個隻包含數字的字元串，用以表示一個 IP 位址，傳回所有可能從
s
獲得的 有效 IP 位址 。你可以按任何順序傳回答案。
有效 IP 位址 正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導
），整數之間用
'.'
分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 位址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 無效 IP 位址。
輸入：s = "25525511135"輸出：["255.255.11.135","255.255.111.35"] 輸入：s = "0000"輸出：["0.0.0.0"] 輸入：s = "1111"輸出：["1.1.1.1"] 輸入：s = "010010"輸出：["0.10.0.10","0.100.1.0"] 輸入：s = "101023"輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"] class Solution { List<String> res = new ArrayList<>(); List<String> path = new ArrayList<>(); public List<String> restoreIpAddresses(String s) { //這裡就是對字元串的預處理，但是對于測試用例來說我覺得用處不大，畢竟不會蠢到用13位數字讓你分割 if(s.length()<4 || s.length()>12){ return res; } //這裡就是套用最經典的回溯模闆了，相比于分割字元串隻加入分割線一個參數以外，這裡還需要添加額外的層數參數level //因為合法的IP位址隻有四段，我們不能無限對其進行分割 backtracking(s,0,0); return res; } // 判斷分割出來的每一段字元串是否是合法的IP位址 boolean isValidIp(String s){ //判斷其是否含有前導0(dai yiji kaku) if(s.charAt(0)=='0' && s.length()>1){ return false; } //長度為4就直接舍棄，加上這一步是為了後面parseInt做準備,防止超過了Integer可以表示的整數範圍 if(s.length()>3){ return false; } //将字元轉為int判斷是否大于255，因為題目明确說了隻由數字組成，是以這裡沒有對非數字的字元進行判斷 if(Integer.parseInt(s)>255){ return false; } return true; } void backtracking(String s,int splitIndex,int level){ //遞歸終止條件，分割的四個字元串都是合法的IP位址 if(level==4){ //在代碼的最後再利用join函數加上“.”,構造IP位址的表示形式 res.add(String.join(".",path)); return; } for(int i=splitIndex;i<s.length();i++){ //每一次分割之後，對剩餘字元長度是否合理進行判斷，剪枝操作，優化運作速度 if((s.length()-i-1) > 3*(3-level)){ continue; } //如果分割的字元串不是合理的IP位址，跳過 if(! isValidIp(s.substring(splitIndex,i+1))){ continue; } //把合法的IP位址段加入path存儲 path.add(s.substring(splitIndex,i+1)); //每次把分割線往後移一位，且段數level+1 backtracking(s,i+1,level+1); //進行回溯操作 path.remove(path.size()-1); } }} 127. 單詞接龍
難度困難845收藏分享切換為英文接收動态回報
字典
wordList
中從單詞
beginWord
endWord
的 轉換序列 是一個按下述規格形成的序列：
- 序列中第一個單詞是
beginWord
- 序列中最後一個單詞是
endWord
- 每次轉換隻能改變一個字母。
- 轉換過程中的中間單詞必須是字典
wordList
beginWord
endWord
和一個字典
wordList
，找到從
beginWord
到
endWord
的 最短轉換序列 中的 單詞數目 。如果不存在這樣的轉換序列，傳回 0。
輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]輸出：5解釋：一個最短轉換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 傳回它的長度 5。 輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]輸出：0解釋：endWord "cog" 不在字典中，是以無法進行轉換。 package DFSandBFS;import java.util.*;/** * Created with IntelliJ IDEA. * * @Author: 張馳 * @Date: 2021/09/21/16:50 * @Description: 三尺秋水塵不染 *//*示例 1： 輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] 輸出：5 解釋：一個最短轉換序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 傳回它的長度 5。 示例 2： 輸入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] 輸出：0 解釋：endWord "cog" 不在字典中，是以無法進行轉換。 來源：力扣（LeetCode） 連結：https://leetcode-cn.com/problems/word-ladder 著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。 */public class ladderLength { /* * @Method: ladderLength * @Description: 三尺秋水塵不染 * * @param beginWord * @param endWord * @param wordList * @paramType: [java.lang.String, java.lang.String, java.util.List<java.lang.String>] * @return：int * @Author: HaRiJi * @Date: 2021/9/21 */ public int ladderLength(String beginWord, String endWord, List<String> wordList) { // 第 1 步：先将 wordList 放到哈希表裡，便于判斷某個單詞是否在 wordList 裡 HashSet<String> wordSet = new HashSet<>(wordList); //終止條件更具提議 if (wordSet.size() == 0 || !wordSet.contains(endWord)) { return 0; } //.結果集合中沒有 開始的凡此 wordSet.remove(beginWord); // 第 2 步：圖的廣度優先周遊，必須使用隊列和表示是否通路過的 visited 哈希表 Deque<String> queue = new ArrayDeque<>(); queue.offer(beginWord); Set<String> visited = new HashSet<>(); visited.add(beginWord); // 第 3 步：開始廣度優先周遊，包含起點，是以初始化的時候步數為 1 int step = 1; //queue是動态的需要動态判斷 while (!queue.isEmpty()) { int currentSize = queue.size(); for (int i = 0; i < currentSize; i++) { // 依次周遊目前隊列中的單詞 String currentWord = queue.poll(); // 如果 currentWord 能夠修改 1 個字元與 endWord 相同，則傳回 step + 1 if (changeWordEveryOneLetter(currentWord, endWord, queue, visited, wordSet)) { return step + 1; } } step++; } return 0; } /* * @Method: changeWordEveryOneLetter * @Description: 三尺秋水塵不染 * * @param currentWord * @param endWord * @param queue * @param visited * @param wordSet * @paramType: [java.lang.String, java.lang.String, java.util.Queue<java.lang.String>, java.util.Set<java.lang.String>, java.util.Set<java.lang.String>] * @return：boolean * @Author: HaRiJi * @Date: 2021/9/21 */ private boolean changeWordEveryOneLetter(String currentWord, String endWord, Queue<String> queue, Set<String> visited, Set<String> wordSet) { char[] charArray = currentWord.toCharArray(); for (int i = 0; i < endWord.length(); i++) { // 先儲存，然後恢複 //就三位012 char originChar = charArray[i]; //比對 for (char k = 'a'; k <= 'z'; k++) { if (k == originChar) { continue; } charArray[i] = k; //取出轉換 String nextWord = String.valueOf(charArray); if (wordSet.contains(nextWord)) { if (nextWord.equals(endWord)) { return true; } if (!visited.contains(nextWord)) { queue.add(nextWord); // 注意：添加到隊列以後，必須馬上标記為已經通路 visited.add(nextWord); } } } // 恢複 charArray[i] = originChar; } return false; }} 分析題意：
「轉換」意即：兩個單詞對應位置隻有一個字元不同，例如 "hit" 與 "hot"，這種轉換是可以逆向的，是以，根據題目給出的單詞清單，可以建構出一個無向（無權）圖；
如果一開始就建構圖，每一個單詞都需要和除它以外的另外的單詞進行比較，複雜度是 O(N \rm{wordLen})O(NwordLen)，這裡 NN 是單詞清單的長度；
為此，我們在周遊一開始，把所有的單詞清單放進一個哈希表中，然後在周遊的時候建構圖，每一次得到在單詞清單裡可以轉換的單詞，複雜度是 O(26 \times \rm{wordLen})O(26×wordLen)，借助哈希表，找到鄰居與 NN 無關；
使用 BFS 進行周遊，需要的輔助資料結構是：
隊列；
visited 集合。說明：可以直接在 wordSet (由 wordList 放進集合中得到)裡做删除。但更好的做法是新開一個哈希表，周遊過的字元串放進哈希表裡。這種做法具有普遍意義。絕大多數線上測評系統和應用場景都不會在意空間開銷。
作者：liweiwei1419
連結：
https://leetcode-cn.com/problems/word-ladder/solution/yan-du-you-xian-bian-li-shuang-xiang-yan-du-you-2/來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
DFS:
模闆:(隊列queue+相鄰節點cur+标記數組visited)
// 計算從起點 start 到終點 target 的最近距離int BFS(Node start, Node target) { Queue<Node> q; // 核心資料結構 Set<Node> visited; // 避免走回頭路 q.offer(start); // 将起點加入隊列 visited.add(start); int step = 0; // 記錄擴散的步數 while (q not empty) { int sz = q.size(); /* 将目前隊列中的所有節點向四周擴散 */ for (int i = 0; i < sz; i++) { Node cur = q.poll(); /* 劃重點：這裡判斷是否到達終點 */ if (cur is target) return step; /* 将 cur 的相鄰節點加入隊列 */ for (Node x : cur.adj()) if (x not in visited) { q.offer(x); visited.add(x); } } /* 劃重點：更新步數在這裡 step++; }} 752. 打開轉盤鎖
難度中等394收藏分享切換為英文接收動态回報
你有一個帶有四個圓形撥輪的轉盤鎖。每個撥輪都有10個數字：
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
。每個撥輪可以自由旋轉：例如把
'9'
變為
'0'
，
'0'
'9'
。每次旋轉都隻能旋轉一個撥輪的一位數字。
鎖的初始數字為
'0000'
，一個代表四個撥輪的數字的字元串。
清單
deadends
包含了一組死亡數字，一旦撥輪的數字和清單裡的任何一個元素相同，這個鎖将會被永久鎖定，無法再被旋轉。
字元串
target
代表可以解鎖的數字，你需要給出解鎖需要的最小旋轉次數，如果無論如何不能解鎖，傳回
-1
輸入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"輸出：6解釋：可能的移動序列為 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 這樣的序列是不能解鎖的，因為當撥動到 "0102" 時這個鎖就會被鎖定。 輸入: deadends = ["8888"], target = "0009"輸出：1解釋：把最後一位反向旋轉一次即可 "0000" -> "0009"。 輸入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"輸出：-1解釋：無法旋轉到目标數字且不被鎖定。 輸入: deadends = ["0000"], target = "8888"輸出：-1 「雙向 BFS」的基本實作思路如下：
建立「兩個隊列」分别用于兩個方向的搜尋；
建立「兩個哈希表」用于「解決相同節點重複搜尋」和「記錄轉換次數」；
為了盡可能讓兩個搜尋方向“平均”，每次從隊列中取值進行擴充時，先判斷哪個隊列容量較少；
如果在搜尋過程中「搜尋到對方搜尋過的節點」，說明找到了最短路徑。
「雙向 BFS」基本思路對應的僞代碼大緻如下：
d1、d2 為兩個方向的隊列m1、m2 為兩個方向的哈希表，記錄每個節點距離起點的 // 隻有兩個隊列都不空，才有必要繼續往下搜尋// 如果其中一個隊列空了，說明從某個方向搜到底都搜不到該方向的目标節點while(!d1.isEmpty() && !d2.isEmpty()) { if (d1.size() < d2.size()) { update(d1, m1, m2); } else { update(d2, m2, m1); }}// update 為從隊列 d 中取出一個元素進行「一次完整擴充」的邏輯void update(Deque d, Map cur, Map other) {} 作者：AC_OIer
https://leetcode-cn.com/problems/open-the-lock/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-wyr9/一個集合的子集：
思路和心得：
（一）二進制枚舉
class Solution { public List<List<Integer>> subsets(int[] nums) { int n = nums.length; List<List<Integer>> res = new ArrayList<>(); for (int state = 0; state < (1 << n); state ++) { List<Integer> cur = new ArrayList<>(); for (int i = 0; i < n; i ++) { if (((state >> i) & 1) == 1) { cur.add(nums[i]); } } res.add(cur); } return res;}
}
（二）dfs
class Solution { int [] nums; int n; List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) { this.nums = nums; n = nums.length; List<Integer> tmp = new ArrayList<>(); dfs(0, tmp); return res;}public void dfs(int idx, List<Integer> path){ if (idx == n) { res.add(path); return ; } List<Integer> path1 = new ArrayList<>(); path1.addAll(path); dfs(idx + 1, path1); path.add(nums[idx]); List<Integer> path2 = new ArrayList<>(); path2.addAll(path); dfs(idx + 1, path2);}
（三）回溯
class Solution { int [] nums; int n; List<Integer> path = new ArrayList<>(); List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { this.nums = nums; this.n = nums.length; backtrace(0); return res;}public void backtrace(int idx){ if (idx == n) { res.add(new ArrayList<>(path)); return ; } backtrace(idx + 1); path.add(nums[idx]); backtrace(idx + 1); path.remove(path.size() - 1);}
下一篇：遞歸算法
作者：Hanxin_Hanxin
https://leetcode-cn.com/problems/TVdhkn/solution/cpython3java-1er-jin-zhi-mei-ju-2dfs-3hu-3z85/動态規劃：
1.1. 爬樓梯
\70. Climbing Stairs (Easy)
Leetcode (opens new window)/
力扣(opens new window)題目描述：有 N 階樓梯，每次可以上一階或者兩階，求有多少種上樓梯的方法。
定義一個數組 dp 存儲上樓梯的方法數（為了友善讨論，數組下标從 1 開始），dp[i] 表示走到第 i 個樓梯的方法數目。
第 i 個樓梯可以從第 i-1 和 i-2 個樓梯再走一步到達，走到第 i 個樓梯的方法數為走到第 i-1 和第 i-2 個樓梯的方法數之和。
考慮到 dp[i] 隻與 dp[i - 1] 和 dp[i - 2] 有關，是以可以隻用兩個變量來存儲 dp[i - 1] 和 dp[i - 2]，使得原來的 O(N) 空間複雜度優化為 O(1) 複雜度。
方法1:利用狀态方程:
class Solution{ public int climbStairs(int n){ int[] dp = new int[n+1]; dp[0] = 1,dp[1] = 1; for(int i = 0;i<n+1;i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; }} 技巧二:滾動數組(優化dp空間)O(n)~O(1)
class Solution{ public int climbStairs(int n){ int p = 0, q =0 r = 1; for(int i = 0; i< n+1;i++){ p = q; q = r; r = p + q; }return r; }} 補充:
技巧:矩陣快速幂複雜度n小的時候可以
通項公式
2.打家劫舍198(環狀的房屋)
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。
給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。
輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 号房屋（金額 = 2），然後偷竊 3 号房屋（金額 = 2）, 因為他們是相鄰的。
輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 号房屋（金額 = 1），然後偷竊 3 号房屋（金額 = 3）。
偷竊到的最高金額 = 1 + 3 = 4 。2 輸入：nums = [0]
輸出：0
由于不能搶劫鄰近住戶，如果搶劫了第 i -1 個住戶，那麼就不能再搶劫第 i 個住戶，是以
public int rob(int[] nums) { int pre2 = 0, pre1 = 0; for (int i = 0; i < nums.length; i++) { int cur = Math.max(pre2 + nums[i], pre1); pre2 = pre1; pre1 = cur; } return pre1;} 2.1 213. 打家劫舍 II
輸入：nums = [2,3,2]輸出：3解釋：你不能先偷竊 1 号房屋（金額 = 2），然後偷竊 3 号房屋（金額 = 2）, 因為他們是相鄰的。 輸入：nums = [1,2,3,1]輸出：4解釋：你可以先偷竊 1 号房屋（金額 = 1），然後偷竊 3 号房屋（金額 = 3）。 偷竊到的最高金額 = 1 + 3 = 4 。 輸入：nums = [0]輸出：0 //兩種思路:1.差分成單個的兩種:{ 1、不偷竊最後一間房間，那麼問題轉化為偷竊0号到i - 1号房間所能獲得的最高金額。 2、不偷竊第一間房間，那麼問題轉化為偷竊1号到i号房間所能獲得的最高金額。}class Solution { public int rob(int[] nums) { if(nums.length == 0) return 0; if(nums.length == 1) return nums[0]; return Math.max(myRob(Arrays.copyOfRange(nums, 0, nums.length - 1)), myRob(Arrays.copyOfRange(nums, 1, nums.length))); } private int myRob(int[] nums) { int pre = 0, cur = 0, tmp; for(int num : nums) { tmp = cur; cur = Math.max(pre + num, cur); pre = tmp; } return cur; }}作者：jyd連結：https://leetcode-cn.com/problems/house-robber-ii/solution/213-da-jia-jie-she-iidong-tai-gui-hua-jie-gou-hua-/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。`我的:` int n = nums.length; if(n == 1) return nums[0]; //隻有一間房間，傳回nums[0] int[] f = new int[n + 1], g = new int[n + 1]; f[1] = nums[0]; //初始化 g[2] = nums[1]; for(int i = 1; i < n-1; ++i) f[i+1] = Math.max(f[i], f[i - 1] + nums[i]); for(int i = 2; i < n; ++i) g[i+1] = Math.max(g[i], g[i - 1] + nums[i]); return Math.max(f[n - 1], g[n]); } 矩陣問題:
1. 矩陣的最小路徑和
\64. Minimum Path Sum (Medium)
[[1,3,1], [1,5,1], [4,2,1]]Given the above grid map, return 7. Because the path 1→3→1→1→1 minimizes the sum. 題目描述：求從矩陣的左上角到右下角的最小路徑和，每次隻能向右和向下移動。
//利用DP[][]數組儲存我們的路徑值:class Solution{ public int minPathSum(int[][] grid) { if(grid == null || grid.length == 0 || grid[0].length == 0){ return 0; } //初始化變量 int row = grid.length; int col = grid[0].length; int[][] dp = new int[row][col]; dp[0][0] = grid[0][0]; //初始化dp數組外層 for(int i = 1; i < row; i++){ //往右走 //左邊加目前的為第一行的dp dp[i][0] = dp[i - 1][0] +grid[i][0]; } for(int j = 1;j < col; j++){ //向下走 //值為上邊的加目前的 dp[0][j] = dp[0][j - 1] +grid[0][j]; } //使用狀态轉移方程 for(int i = 1; i < row; i++){ for(int j = 1;j < col; j++){ dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1]) + grid[i][j]; } } //傳回狀态轉移方程的結果為二維數組的最後一個 return dp[row-1][col-1]; }} //優化版本如下:(直接修改原來的數組)class Solution { public int minPathSum(int[][] grid) { for(int i = 0; i < grid.length; i++) { for(int j = 0; j < grid[0].length; j++) { //初始化dp數組外層 if(i == 0 && j == 0) continue; else if(i == 0) grid[i][j] = grid[i][j - 1] + grid[i][j]; else if(j == 0) grid[i][j] = grid[i - 1][j] + grid[i][j]; //使用狀态轉移方程 else grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]; } } //傳回狀态轉移方程的結果為二維數組的最後一個 return grid[grid.length - 1][grid[0].length - 1]; }}作者：jyd連結：https://leetcode-cn.com/problems/minimum-path-sum/solution/zui-xiao-lu-jing-he-dong-tai-gui-hua-gui-fan-liu-c/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 62. 不同路徑
難度中等1125
一個機器人位于一個
m x n
網格的左上角 （起始點在下圖中标記為 “Start” ）。
機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為 “Finish” ）。
問總共有多少條不同的路徑？
輸入：m = 3, n = 7輸出：28 輸入：m = 3, n = 2輸出：3解釋：從左上角開始，總共有 3 條路徑可以到達右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下 輸入：m = 7, n = 3輸出：28 輸入：m = 3, n = 3輸出：6 優化:二維轉一維
public int uniquePaths(int m, int n) { int[] dp = new int[n]; Arrays.fill(dp, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1];} 普通:
public int uniquePaths(int m,int n){ int[][] dp = new int[m][n]; for(int i = 0;i < m;i++){ dp[i][0] = 1; } for(int j = 0;j < n;j++){ dp[0][j] = 1; } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){ dp[i][j] = dp[i-1][j]+dp[i][j-1]; } } return dp[m-1][n-1];} 數組區間
# 1. 數組區間和
\303. Range Sum Query - Immutable (Easy)
Given nums = [-2, 0, 3, -5, 2, -1]sumRange(0, 2) -> 1sumRange(2, 5) -> -1sumRange(0, 5) -> -3 求區間 i ~ j 的和，可以轉換為 sum[j + 1] - sum[i]，其中 sum[i] 為 0 ~ i - 1 的和。
class NumArray {public int[] NumArray; public NumArray(int[] nums) { int length = nums.length; NumArray = new int[length+1]; //關鍵地方 for(int i = 1;i < length+1 ;i++){ NumArray[i] = NumArray[i-1] + nums[i-1]; } } public int sumRange(int left, int right) { return NumArray[right + 1] - NumArray[left]; }}/** * Your NumArray object will be instantiated and called as such: * NumArray obj = new NumArray(nums); * int param_1 = obj.sumRange(left,right); */ 2. 數組中等差遞增子區間的個數
\413. Arithmetic Slices (Medium)
A = [0, 1, 2, 3, 4]return: 6, for 3 arithmetic slices in A:[0, 1, 2],[1, 2, 3],[0, 1, 2, 3],[0, 1, 2, 3, 4],[ 1, 2, 3, 4],[2, 3, 4] dp[i] 表示以 A[i] 為結尾的等差遞增子區間的個數。
當 A[i] - A[i-1] == A[i-1] - A[i-2]，那麼 [A[i-2], A[i-1], A[i]] 構成一個等差遞增子區間。而且在以 A[i-1] 為結尾的遞增子區間的後面再加上一個 A[i]，一樣可以構成新的遞增子區間。
dp[2] = 1 [0, 1, 2]dp[3] = dp[2] + 1 = 2 [0, 1, 2, 3], // [0, 1, 2] 之後加一個 3 [1, 2, 3] // 新的遞增子區間dp[4] = dp[3] + 1 = 3 [0, 1, 2, 3, 4], // [0, 1, 2, 3] 之後加一個 4 [1, 2, 3, 4], // [1, 2, 3] 之後加一個 4 [2, 3, 4] // 新的遞增子區間 綜上，在 A[i] - A[i-1] == A[i-1] - A[i-2] 時，dp[i] = dp[i-1] + 1。
因為遞增子區間不一定以最後一個元素為結尾，可以是任意一個元素結尾，是以需要傳回 dp 數組累加的結果。
二分法
int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜尋區間為 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜尋區間變為 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜尋區間變為 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收縮右側邊界 right = mid - 1; } } // 檢查出界情況 if (left >= nums.length || nums[left] != target) return -1; return left;} 第一個，最基本的二分查找算法：
因為我們初始化 right = nums.length - 1是以決定了我們的「搜尋區間」是 [left, right]是以決定了 while (left <= right)同時也決定了 left = mid+1 和 right = mid-1因為我們隻需找到一個 target 的索引即可是以當 nums[mid] == target 時可以立即傳回 第二個，尋找左側邊界的二分查找：
因為我們初始化 right = nums.length是以決定了我們的「搜尋區間」是 [left, right)是以決定了 while (left < right)同時也決定了 left = mid + 1 和 right = mid因為我們需找到 target 的最左側索引是以當 nums[mid] == target 時不要立即傳回而要收緊右側邊界以鎖定左側邊界 第三個，尋找右側邊界的二分查找：
因為我們初始化 right = nums.length是以決定了我們的「搜尋區間」是 [left, right)是以決定了 while (left < right)同時也決定了 left = mid + 1 和 right = mid因為我們需找到 target 的最右側索引是以當 nums[mid] == target 時不要立即傳回而要收緊左側邊界以鎖定右側邊界又因為收緊左側邊界時必須 left = mid + 1是以最後無論傳回 left 還是 right，必須減一 對于尋找左右邊界的二分搜尋，常見的手法是使用左閉右開的「搜尋區間」，我們還根據邏輯将「搜尋區間」全都統一成了兩端都閉，便于記憶，隻要修改兩處即可變化出三種寫法：
int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接傳回 return mid; } } // 直接傳回 return -1;}int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别傳回，鎖定左側邊界 right = mid - 1; } } // 最後要檢查 left 越界的情況 if (left >= nums.length || nums[left] != target) return -1; return left;}int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别傳回，鎖定右側邊界 left = mid + 1; } } // 最後要檢查 right 越界的情況 if (right < 0 || nums[right] != target) return -1; return right;} 如果以上内容你都能了解，那麼恭喜你，二分查找算法的細節不過如此。
滑動視窗:
本質為暴力遞歸優化後的雙指針的優化版.
3. 無重複字元的最長子串
難度中等6149收藏分享切換為英文接收動态回報
給定一個字元串
s
，請你找出其中不含有重複字元的 最長子串 的長度。
輸入: s = "abcabcbb"輸出: 3 解釋: 因為無重複字元的最長子串是 "abc"，是以其長度為 3。 輸入: s = "bbbbb"輸出: 1解釋: 因為無重複字元的最長子串是 "b"，是以其長度為 1。 輸入: s = "pwwkew"輸出: 3解釋: 因為無重複字元的最長子串是 "wke"，是以其長度為 3。 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。 輸入: s = ""輸出: 0 class Solution { public int lengthOfLongestSubstring(String s) { HashMap<Character,Integer> map = new HashMap<Character,Integer> (); int length = s.length(); int ans = 0; for(int start = 0 ,end = 0;end < length; end++ ){ if(map.containsKey(s.charAt(end))){ start = Math.max(map.get(s.charAt(end)),start); } ans = Math.max(ans,end-start+1); map.put(s.charAt(end),end+1); } return ans; }} 76. 最小覆寫子串
難度困難1350收藏分享切換為英文接收動态回報
s
、一個字元串
t
。傳回
s
中涵蓋
t
所有字元的最小子串。如果
s
中不存在涵蓋
t
所有字元的子串，則傳回空字元串
""
注意：
- 對于
t
t
- 如果
s
輸入：s = "ADOBECODEBANC", t = "ABC"輸出："BANC" 輸入：s = "a", t = "a"輸出："a" 輸入: s = "a", t = "aa"輸出: ""解釋: t 中兩個字元 'a' 均應包含在 s 的子串中，是以沒有符合條件的子字元串，傳回空字元串。 class Solution { public String minWindow(String s, String t) { if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) { return ""; } //維護兩個數組，記錄已有字元串指定字元的出現次數，和目标字元串指定字元的出現次數 //ASCII表總長128 int[] need = new int[128]; int[] have = new int[128]; //将目标字元串指定字元的出現次數記錄 for (int i = 0; i < t.length(); i++) { need[t.charAt(i)]++; } //分别為左指針，右指針，最小長度(初始值為一定不可達到的長度) //已有字元串中目标字元串指定字元的出現總頻次以及最小覆寫子串在原字元串中的起始位置 int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0; while (right < s.length()) { char r = s.charAt(right); //說明該字元不被目标字元串需要，此時有兩種情況 // 1.循環剛開始，那麼直接移動右指針即可，不需要做多餘判斷 // 2.循環已經開始一段時間，此處又有兩種情況 // 2.1 上一次條件不滿足，已有字元串指定字元出現次數不滿足目标字元串指定字元出現次數，那麼此時 // 如果該字元還不被目标字元串需要，就不需要進行多餘判斷，右指針移動即可 // 2.2 左指針已經移動完畢，那麼此時就相當于循環剛開始，同理直接移動右指針 if (need[r] == 0) { right++; continue; } //當且僅當已有字元串目标字元出現的次數小于目标字元串字元的出現次數時，count才會+1 //是為了後續能直接判斷已有字元串是否已經包含了目标字元串的所有字元，不需要挨個比對字元出現的次數 if (have[r] < need[r]) { count++; } //已有字元串中目标字元出現的次數+1 have[r]++; //移動右指針 right++; //當且僅當已有字元串已經包含了所有目标字元串的字元，且出現頻次一定大于或等于指定頻次 while (count == t.length()) { //擋視窗的長度比已有的最短值小時，更改最小值，并記錄起始位置 if (right - left < min) { min = right - left; start = left; } char l = s.charAt(left); //如果左邊即将要去掉的字元不被目标字元串需要，那麼不需要多餘判斷，直接可以移動左指針 if (need[l] == 0) { left++; continue; } //如果左邊即将要去掉的字元被目标字元串需要，且出現的頻次正好等于指定頻次，那麼如果去掉了這個字元， //就不滿足覆寫子串的條件，此時要破壞循環條件跳出循環，即控制目标字元串指定字元的出現總頻次(count）-1 if (have[l] == need[l]) { count--; } //已有字元串中目标字元出現的次數-1 have[l]--; //移動左指針 left++; } } //如果最小長度還為初始值，說明沒有符合條件的子串 if (min == s.length() + 1) { return ""; } //傳回的為以記錄的起始位置為起點，記錄的最短長度為距離的指定字元串中截取的子串 return s.substring(start, start + min); }} 你知道滑動視窗是怎麼畫起來的嗎?
class Solution { public String minWindow(String s, String t) { //儲存s HashMap<Character,Integer> hs = new HashMap<Character,Integer>(); //儲存t HashMap<Character,Integer> ht = new HashMap<Character,Integer>(); for(int i = 0;i < t.length();i ++){ ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1); } String ans = ""; //一個得不到的數字罷了,就按照長度加一就好了. int len = 0x3f3f3f3f, cnt = 0; //有多少個元素符合 for(int i = 0,j = 0;i < s.length();i ++) { hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1); if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++; while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))){ int count = hs.get(s.charAt(j)) - 1; hs.put(s.charAt(j), count); j ++; } if(cnt == t.length() && i - j + 1 < len){ len = i - j + 1; ans = s.substring(j,i + 1); } } return ans; }}作者：lin-shen-shi-jian-lu-k連結：https://leetcode-cn.com/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/來源：力扣（LeetCode）著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。 島嶼系列：
本期例題為 LeetCode「島嶼問題」系列：
- [LeetCode 463. Island Perimeter 島嶼的周長（Easy）]()
- [LeetCode 695. Max Area of Island 島嶼的最大面積（Medium）]()
- [LeetCode 827. Making A Large Island 填海造陸（Hard）]()
我們所熟悉的 DFS（深度優先搜尋）問題通常是在樹或者圖結構上進行的。而我們今天要讨論的 DFS 問題，是在一種「網格」結構中進行的。島嶼問題是這類網格 DFS 問題的典型代表。網格結構周遊起來要比二叉樹複雜一些，如果沒有掌握一定的方法，DFS 代碼容易寫得冗長繁雜。
本文将以島嶼問題為例，展示網格類問題 DFS 通用思路，以及如何讓代碼變得簡潔。主要内容包括：
- 網格類問題的基本性質
- 在網格中進行 DFS 周遊的方法與技巧
- 三個島嶼問題的解法
- 相關題目
網格類問題的 DFS 周遊方法
網格問題的基本概念
我們首先明确一下島嶼問題中的網格結構是如何定義的，以友善我們後面的讨論。
網格問題是由 個小方格組成一個網格，每個小方格與其上下左右四個方格認為是相鄰的，要在這樣的網格上進行某種搜尋。
島嶼問題是一類典型的網格問題。每個格子中的數字可能是 0 或者 1。我們把數字為 0 的格子看成海洋格子，數字為 1 的格子看成陸地格子，這樣相鄰的陸地格子就連接配接成一個島嶼。
島嶼問題示例
在這樣一個設定下，就出現了各種島嶼問題的變種，包括島嶼的數量、面積、周長等。不過這些問題，基本都可以用 DFS 周遊來解決。
DFS 的基本結構
網格結構要比二叉樹結構稍微複雜一些，它其實是一種簡化版的圖結構。要寫好網格上的 DFS 周遊，我們首先要了解二叉樹上的 DFS 周遊方法，再類比寫出網格結構上的 DFS 周遊。我們寫的二叉樹 DFS 周遊一般是這樣的：
void traverse(TreeNode root) { // 判斷 base case if (root == null) { return; } // 通路兩個相鄰結點：左子結點、右子結點 traverse(root.left); traverse(root.right);} 可以看到，二叉樹的 DFS 有兩個要素：「通路相鄰結點」和「判斷 base case」。
第一個要素是通路相鄰結點。二叉樹的相鄰結點非常簡單，隻有左子結點和右子結點兩個。二叉樹本身就是一個遞歸定義的結構：一棵二叉樹，它的左子樹和右子樹也是一棵二叉樹。那麼我們的 DFS 周遊隻需要遞歸調用左子樹和右子樹即可。
第二個要素是 判斷 base case。一般來說，二叉樹周遊的 base case 是
root == null
。這樣一個條件判斷其實有兩個含義：一方面，這表示
root
指向的子樹為空，不需要再往下周遊了。另一方面，在
root == null
的時候及時傳回，可以讓後面的
root.left
root.right
操作不會出現空指針異常。
對于網格上的 DFS，我們完全可以參考二叉樹的 DFS，寫出網格 DFS 的兩個要素：
首先，網格結構中的格子有多少相鄰結點？答案是上下左右四個。對于格子
(r, c)
來說（r 和 c 分别代表行坐标和列坐标），四個相鄰的格子分别是
(r-1, c)
、
(r+1, c)
(r, c-1)
(r, c+1)
。換句話說，網格結構是「四叉」的。
網格結構中四個相鄰的格子
其次，網格 DFS 中的 base case 是什麼？從二叉樹的 base case 對應過來，應該是網格中不需要繼續周遊、
grid[r][c]
會出現數組下标越界異常的格子，也就是那些超出網格範圍的格子。
網格 DFS 的 base case
這一點稍微有些反直覺，坐标竟然可以臨時超出網格的範圍？這種方法我稱為「先污染後治理」—— 甭管目前是在哪個格子，先往四個方向走一步再說，如果發現走出了網格範圍再趕緊傳回。這跟二叉樹的周遊方法是一樣的，先遞歸調用，發現
root == null
再傳回。
這樣，我們得到了網格 DFS 周遊的架構代碼：
void dfs(int[][] grid, int r, int c) { // 判斷 base case // 如果坐标 (r, c) 超出了網格範圍，直接傳回 if (!inArea(grid, r, c)) { return; } // 通路上、下、左、右四個相鄰結點 dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1);}// 判斷坐标 (r, c) 是否在網格中boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;} 如何避免重複周遊
網格結構的 DFS 與二叉樹的 DFS 最大的不同之處在于，周遊中可能遇到周遊過的結點。這是因為，網格結構本質上是一個「圖」，我們可以把每個格子看成圖中的結點，每個結點有向上下左右的四條邊。在圖中周遊時，自然可能遇到重複周遊結點。
這時候，DFS 可能會不停地「兜圈子」，永遠停不下來，如下圖所示：
DFS 周遊可能會兜圈子（動圖）
如何避免這樣的重複周遊呢？答案是标記已經周遊過的格子。以島嶼問題為例，我們需要在所有值為 1 的陸地格子上做 DFS 周遊。每走過一個陸地格子，就把格子的值改為 2，這樣當我們遇到 2 的時候，就知道這是周遊過的格子了。也就是說，每個格子可能取三個值：
- 0 —— 海洋格子
- 1 —— 陸地格子（未周遊過）
- 2 —— 陸地格子（已周遊過）
我們在架構代碼中加入避免重複周遊的語句：
void dfs(int[][] grid, int r, int c) { // 判斷 base case if (!inArea(grid, r, c)) { return; } // 如果這個格子不是島嶼，直接傳回 if (grid[r][c] != 1) { return; } grid[r][c] = 2; // 将格子标記為「已周遊過」 // 通路上、下、左、右四個相鄰結點 dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1);}// 判斷坐标 (r, c) 是否在網格中boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;} 标記已周遊的格子
這樣，我們就得到了一個島嶼問題、乃至各種網格問題的通用 DFS 周遊方法。以下所講的幾個例題，其實都隻需要在 DFS 周遊架構上稍加修改而已。
小貼士：
在一些題解中，可能會把「已周遊過的陸地格子」标記為和海洋格子一樣的 0，美其名曰「陸地沉沒方法」，即周遊完一個陸地格子就讓陸地「沉沒」為海洋。這種方法看似很巧妙，但實際上有很大隐患，因為這樣我們就無法區分「海洋格子」和「已周遊過的陸地格子」了。如果題目更複雜一點，這很容易出 bug。
島嶼問題的解法
了解了網格結構的 DFS 周遊方法以後，島嶼問題就不難解決了。下面我們分别看看三個題目該如何用 DFS 周遊來求解。
例題 1：島嶼的最大面積
LeetCode 695. Max Area of Island （Medium）
給定一個包含了一些 0 和 1 的非空二維數組，一個島嶼是一組相鄰的 1（代表陸地），這裡的「相鄰」要求兩個 1 必須在水準或者豎直方向上相鄰。你可以假設grid
grid
的四個邊緣都被 0（代表海洋）包圍着。
找到給定的二維數組中最大的島嶼面積。如果沒有島嶼，則傳回面積為 0 。
這道題目隻需要對每個島嶼做 DFS 周遊，求出每個島嶼的面積就可以了。求島嶼面積的方法也很簡單，代碼如下，每周遊到一個格子，就把面積加一。
int area(int[][] grid, int r, int c) { return 1 + area(grid, r - 1, c) + area(grid, r + 1, c) + area(grid, r, c - 1) + area(grid, r, c + 1);} 最終我們得到的完整題解代碼如下：
public int maxAreaOfIsland(int[][] grid) { int res = 0; for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == 1) { int a = area(grid, r, c); res = Math.max(res, a); } } } return res;}int area(int[][] grid, int r, int c) { if (!inArea(grid, r, c)) { return 0; } if (grid[r][c] != 1) { return 0; } grid[r][c] = 2; return 1 + area(grid, r - 1, c) + area(grid, r + 1, c) + area(grid, r, c - 1) + area(grid, r, c + 1);}boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;} 例題 2：填海造陸問題
LeetCode 827. Making A Large Island （Hard）
在二維地圖上， 0 代表海洋，1代表陸地，我們最多隻能将一格 0 （海洋）變成 1 （陸地）。進行填海之後，地圖上最大的島嶼面積是多少？
這道題是島嶼最大面積問題的更新版。現在我們有填海造陸的能力，可以把一個海洋格子變成陸地格子，進而讓兩塊島嶼連成一塊。那麼填海造陸之後，最大可能構造出多大的島嶼呢？
大緻的思路我們不難想到，我們先計算出所有島嶼的面積，在所有的格子上标記出島嶼的面積。然後搜尋哪個海洋格子相鄰的兩個島嶼面積最大。例如下圖中紅色方框内的海洋格子，上邊、左邊都與島嶼相鄰，我們可以計算出它變成陸地之後可以連接配接成的島嶼面積為 。
一個海洋格子連接配接起兩個島嶼
然而，這種做法可能遇到一個問題。如下圖中紅色方框内的海洋格子，它的上邊、左邊都與島嶼相鄰，這時候連接配接成的島嶼面積難道是 ？顯然不是。這兩個 7 來自同一個島嶼，是以填海造陸之後得到的島嶼面積應該隻有 。
一個海洋格子與同一個島嶼有兩個邊相鄰
可以看到，要讓算法正确，我們得能區分一個海洋格子相鄰的兩個 7 是不是來自同一個島嶼。那麼，我們不能在方格中标記島嶼的面積，而應該标記島嶼的索引（下标），另外用一個數組記錄每個島嶼的面積，如下圖所示。這樣我們就可以發現紅色方框内的海洋格子，它的「兩個」相鄰的島嶼實際上是同一個。
标記每個島嶼的索引（下标）
可以看到，這道題實際上是對網格做了兩遍 DFS：第一遍 DFS 周遊陸地格子，計算每個島嶼的面積并标記島嶼；第二遍 DFS 周遊海洋格子，觀察每個海洋格子相鄰的陸地格子。
這道題的基本思路就是這樣，具體的代碼還有一些需要注意的細節，但和本文的主題已經聯系不大。各位可以自己思考一下如何把上述思路轉化為代碼。
例題 3：島嶼的周長
LeetCode 463. Island Perimeter （Easy）
給定一個包含 0 和 1 的二維網格地圖，其中 1 表示陸地，0 表示海洋。網格中的格子水準和垂直方向相連（對角線方向不相連）。整個網格被水完全包圍，但其中恰好有一個島嶼（一個或多個表示陸地的格子相連組成島嶼）。
島嶼中沒有“湖”（“湖” 指水域在島嶼内部且不和島嶼周圍的水相連）。格子是邊長為 1 的正方形。計算這個島嶼的周長。
題目示例
實話說，這道題用 DFS 來解并不是最優的方法。對于島嶼，直接用數學的方法求周長會更容易。不過這道題是一個很好的了解 DFS 周遊過程的例題，不信你跟着我往下看。
我們再回顧一下 網格 DFS 周遊的基本架構：
void dfs(int[][] grid, int r, int c) { // 判斷 base case if (!inArea(grid, r, c)) { return; } // 如果這個格子不是島嶼，直接傳回 if (grid[r][c] != 1) { return; } grid[r][c] = 2; // 将格子标記為「已周遊過」 // 通路上、下、左、右四個相鄰結點 dfs(grid, r - 1, c); dfs(grid, r + 1, c); dfs(grid, r, c - 1); dfs(grid, r, c + 1);}// 判斷坐标 (r, c) 是否在網格中boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;} 可以看到，
dfs
函數直接傳回有這幾種情況：
-
!inArea(grid, r, c)
(r, c)
-
grid[r][c] != 1
-
-
grid[r][c] == 0
-
grid[r][c] == 2
-
那麼這些和我們島嶼的周長有什麼關系呢？實際上，島嶼的周長是計算島嶼全部的「邊緣」，而這些邊緣就是我們在 DFS 周遊中，
dfs
函數傳回的位置。觀察題目示例，我們可以将島嶼的周長中的邊分為兩類，如下圖所示。黃色的邊是與網格邊界相鄰的周長，而藍色的邊是與海洋格子相鄰的周長。
将島嶼周長中的邊分為兩類
當我們的
dfs
函數因為「坐标
(r, c)
超出網格範圍」傳回的時候，實際上就經過了一條黃色的邊；而當函數因為「目前格子是海洋格子」傳回的時候，實際上就經過了一條藍色的邊。這樣，我們就把島嶼的周長跟 DFS 周遊聯系起來了，我們的題解代碼也呼之欲出：
public int islandPerimeter(int[][] grid) { for (int r = 0; r < grid.length; r++) { for (int c = 0; c < grid[0].length; c++) { if (grid[r][c] == 1) { // 題目限制隻有一個島嶼，計算一個即可 return dfs(grid, r, c); } } } return 0;}int dfs(int[][] grid, int r, int c) { // 函數因為「坐标 (r, c) 超出網格範圍」傳回，對應一條黃色的邊 if (!inArea(grid, r, c)) { return 1; } // 函數因為「目前格子是海洋格子」傳回，對應一條藍色的邊 if (grid[r][c] == 0) { return 1; } // 函數因為「目前格子是已周遊的陸地格子」傳回，和周長沒關系 if (grid[r][c] != 1) { return 0; } grid[r][c] = 2; return dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1);}// 判斷坐标 (r, c) 是否在網格中boolean inArea(int[][] grid, int r, int c) { return 0 <= r && r < grid.length && 0 <= c && c < grid[0].length;}