hot100（8）

71.10. 正則表達式匹配 - 力扣（LeetCode）

動態規劃

題解：10. 正則表達式匹配題解 - 力扣（LeetCode）

72.5. 最長回文子串 - 力扣（LeetCode）

動態規劃

1.dp數組及下標含義

dp[i][j] : 下標i到下標j的子串是否是回文串

2.遞推方程

dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j)

3.初始化

對于單個字母,dp[i][i] = true;

對于兩個字母的子串，如果兩個字母相同，dp[i][i+1] = true;

4.遞推順序

5.dp數組舉例說明

public String longestPalindrome(String s) {if(s.length() < 2){return s;}boolean[][] dp = new boolean[s.length()][s.length()];for(int i = 0 ; i < s.length() ; i++){dp[i][i] = true;}int maxlen = 0,start = 0;for(int len = 2 ; len <= s.length() ; len++){for(int i = 0 ; i < s.length() - len + 1 ; i++){int j = i + len - 1;if(s.charAt(i) != s.charAt(j)){dp[i][j] = false;}else{if(j - i < 3){dp[i][j] = true;}else{dp[i][j] = dp[i+1][j-1];}}if(dp[i][j] && j - i + 1 > maxlen){maxlen = j - i + 1;start = i;}}}return s.substring(start,start +maxlen);}

方法二類似于使用滾動數組優化動態規劃的空間復雜度的本質，只使用上一個狀態，不必保留所有狀態。

枚舉出所有的中心，即可得到所有可能的回文子串（必由某一中心擴展而來）

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) {return "";}int start = 0, end = 0;for (int i = 0; i < s.length(); i++) {int len1 = expandAroundCenter(s, i, i);int len2 = expandAroundCenter(s, i, i + 1);int len = Math.max(len1, len2);if (len > end - start) {start = i - (len - 1) / 2;end = i + len / 2;}}return s.substring(start, end + 1);}public int expandAroundCenter(String s, int left, int right) {while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {--left;++right;}return right - left - 1;}
}

73.

74.3. 無重復字符的最長子串 - 力扣（LeetCode）

滑動窗口

public int lengthOfLongestSubstring(String s) {int l = 0 , r = 0 , ans = 0 ;Set<Character> set = new HashSet<>();for(; r < s.length() ;r++){while(set.contains(s.charAt(r))){set.remove(s.charAt(l));l++;}set.add(s.charAt(r));int len = r - l + 1;ans = Math.max(ans,len);}return ans;}

滑動窗口題目匯總：3. 無重復字符的最長子串題解 - 力扣（LeetCode）

75.2. 兩數相加 - 力扣（LeetCode）

鏈表，進位邊界情況的處理分析

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {int carry = 0;ListNode head = new ListNode(-1);ListNode p = head;ListNode p1 = l1 , p2 = l2;while(p1 != null && p2 != null){int value = p1.val + p2.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p1 = p1.next;p2 = p2.next;}while(p1 != null){int value = p1.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p1 = p1.next;}while(p2 != null){int value = p2.val + carry;carry = value/10;p.next = new ListNode(value % 10);p = p.next;p2 = p2.next;}if(carry != 0){p.next = new ListNode(carry);}return head.next;}

時間復雜度O(m+n)

空間復雜度O(m+n)

76.79. 單詞搜索 - 力扣（LeetCode）

回溯，dfs

int[][] directions = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};boolean res = false;char[][] board;StringBuilder path = new StringBuilder();String word;boolean[][] isVisited;public boolean exist(char[][] board, String word) {this.board = board;this.word = word;isVisited = new boolean[board.length][board[0].length];char head = word.charAt(0);for(int i = 0 ; i < board.length ; i++){for(int j = 0 ; j < board[0].length ; j++){if(board[i][j] == head){isVisited[i][j] = true;path.append(board[i][j]);dfs(i,j,0);path.deleteCharAt(path.length() - 1);isVisited[i][j] = false;}if(res){return res;}}}return res;}public void dfs(int x , int y , int index){if(word.charAt(index) != path.charAt(path.length() - 1)){//剪枝，減去board[x][y]與word對應字符不匹配的搜索return ;}if(path.toString().equals(word)){res = true;//剪枝，減去找到正確答案以后得搜索return;}for(int i = 0 ; i < 4 ; i++){int newX = x + directions[i][0];int newY = y + directions[i][1];if(newX < 0 || newX >= board.length || newY < 0 || newY >= board[0].length || isVisited[newX][newY]){continue;}isVisited[newX][newY] = true;path.append(board[newX][newY]);dfs(newX,newY,path.length() - 1);path.deleteCharAt(path.length() - 1);isVisited[newX][newY] = false;}}

77.114. 二叉樹展開為鏈表 - 力扣（LeetCode）

I創建一個新的鏈表，dfs，然后修改樹

ListNode head;ListNode list;public void flatten(TreeNode root) {if(root == null) return;head = new ListNode(0);list = head;dfs(root);list = head.next.next;root.left = null;TreeNode node = root;while(list != null){node.right = new TreeNode(list.val);node = node.right;list = list.next;}}public void dfs(TreeNode root){list.next = new ListNode(root.val);list = list.next;if(root.left != null){dfs(root.left);}if(root.right != null){dfs(root.right);}}

II 根據先序遍歷中左右的順序，分析插入的順序，進行模擬

將左子樹插入到右子樹的地方
將原來的右子樹接到左子樹的最右邊節點
考慮新的右子樹的根節點，一直重復上邊的過程，直到新的右子樹為 null

    1/ \2   5/ \   \
3   4   6//將 1 的左子樹插入到右子樹的地方1\2         5/ \         \3   4         6        
//將原來的右子樹接到左子樹的最右邊節點1\2          / \          3   4  \5\6//將 2 的左子樹插入到右子樹的地方1\2          \          3       4  \5\6   //將原來的右子樹接到左子樹的最右邊節點1\2          \          3      \4  \5\6         ......

public void flatten(TreeNode root) {while(root != null){if(root.left == null){root = root.right;}else{TreeNode pre = root.left;while(pre.right != null){pre = pre.right;}pre.right = root.right;root.right = root.left;root.left = null;root = root.right;}}}

III原地修改

容易想到的方法是在先序遍歷的過程中，把當前遍歷的結點改成上一結點的右結點就能滿足題目要求，但會發現原來還沒有訪問的右結點丟失了。那么可以想到如果先訪問結點，再修改，就能避免修改造成的影響，只要按照右、左、中的順序進行遍歷，即后序遍歷，將當前節點的右結點改成上一次訪問的結點，即能滿足題目要求，并且把左結點置為null，而左結點已經放問過了，不會有影響。

TreeNode pre;public void flatten(TreeNode root) {if(root == null) return;postOrder(root);}public void postOrder(TreeNode root){if(root.right != null){postOrder(root.right);}if(root.left != null){postOrder(root.left);}root.right = pre;root.left = null;pre = root;}

78.621. 任務調度器 - 力扣（LeetCode）

模擬貪心

貪心：每次選擇待執行次數最多的任務

class Solution {public int leastInterval(char[] tasks, int n) {Map<Character, Integer> freq = new HashMap<Character, Integer>();for (char ch : tasks) {freq.put(ch, freq.getOrDefault(ch, 0) + 1);}// 任務種類數int m = freq.size();List<Integer> nextValid = new ArrayList<Integer>();List<Integer> rest = new ArrayList<Integer>();Set<Map.Entry<Character, Integer>> entrySet = freq.entrySet();for (Map.Entry<Character, Integer> entry : entrySet) {int value = entry.getValue();nextValid.add(1);rest.add(value);}int time = 0;for (int i = 0; i < tasks.length; ++i) {++time;int minNextValid = Integer.MAX_VALUE;for (int j = 0; j < m; ++j) {if (rest.get(j) != 0) {minNextValid = Math.min(minNextValid, nextValid.get(j));}}time = Math.max(time, minNextValid);int best = -1;for (int j = 0; j < m; ++j) {if (rest.get(j) != 0 && nextValid.get(j) <= time) {if (best == -1 || rest.get(j) > rest.get(best)) {best = j;}}}nextValid.set(best, time + n + 1);rest.set(best, rest.get(best) - 1);}return time;}
}

另一種貪心策略：

 public int leastInterval(char[] tasks, int n) {//統計每個任務出現的次數，找到出現次數最多的任務int[] hash = new int[26];for(int i = 0; i < tasks.length; ++i) {hash[tasks[i] - 'A'] += 1;}Arrays.sort(hash);//因為相同元素必須有n個冷卻時間，假設A出現3次，n = 2，任務要執行完，至少形成AXX AXX A序列（X看作預占位置）//該序列長度為int minLen = (n+1) *  (hash[25] - 1) + 1;//此時為了盡量利用X所預占的空間（貪心）使得整個執行序列長度盡量小，將剩余任務往X預占的空間插入//剩余的任務次數有兩種情況：//1.與A出現次數相同，比如B任務最優插入結果是ABX ABX AB，中間還剩兩個空位，當前序列長度+1//2.比A出現次數少，若還有X，則按序插入X位置，比如C出現兩次，形成ABC ABC AB的序列//直到X預占位置還沒插滿，剩余元素逐個放入X位置就滿足冷卻時間至少為nfor(int i = 24; i >= 0; --i){if(hash[i] == hash[25]) ++ minLen;}//當所有X預占的位置插滿了怎么辦？//在任意插滿區間（這里是ABC）后面按序插入剩余元素，比如ABCD ABCD發現D之間距離至少為n+1，肯定滿足冷卻條件//因此，當X預占位置能插滿時，最短序列長度就是task.length，不能插滿則取最少預占序列長度return Math.max(minLen, tasks.length);}

79.617. 合并二叉樹 - 力扣（LeetCode）

遞歸

1.確定遞歸函數參數和返回值

參數：兩個樹的根節點

返回值：合并后樹的根節點

2.終止條件

因為是傳入了兩個樹，那么就有兩個樹遍歷的節點t1 和 t2，如果t1 == NULL 了，兩個樹合并就應該是 t2 了（如果t2也為NULL也無所謂，合并之后就是NULL）。

反過來如果t2 == NULL，那么兩個數合并就是t1（如果t1也為NULL也無所謂，合并之后就是NULL）。

3.確定單層邏輯

重復利用一下t1這個樹，t1就是合并之后樹的根節點（就是修改了原來樹的結構）。

那么單層遞歸中，就要把兩棵樹的元素加到一起。

t1.val += t2.val;

接下來t1 的左子樹是：合并 t1左子樹 t2左子樹之后的左子樹。

t1 的右子樹：是合并 t1右子樹 t2右子樹之后的右子樹。

最終t1就是合并之后的根節點。

public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}

80.105. 從前序與中序遍歷序列構造二叉樹 - 力扣（LeetCode）

首先回憶一下如何根據兩個順序構造一個唯一的二叉樹，相信理論知識大家應該都清楚，就是以后序數組的最后一個元素為切割點，先切中序數組，根據中序數組，反過來再切后序數組。一層一層切下去，每次后序數組最后一個元素就是節點元素。

如果讓我們肉眼看兩個序列，畫一棵二叉樹的話，應該分分鐘都可以畫出來。

流程如圖：

那么代碼應該怎么寫呢？

說到一層一層切割，就應該想到了遞歸。

來看一下一共分幾步：

第一步：如果數組大小為零的話，說明是空節點了。
第二步：如果不為空，那么取后序數組最后一個元素作為節點元素。
第三步：找到后序數組最后一個元素在中序數組的位置，作為切割點
第四步：切割中序數組，切成中序左數組和中序右數組（順序別搞反了，一定是先切中序數組）
第五步：切割后序數組，切成后序左數組和后序右數組
第六步：遞歸處理左區間和右區間

不難寫出如下代碼：（先把框架寫出來）

TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {// 第一步if (postorder.size() == 0) return NULL;// 第二步：后序遍歷數組最后一個元素，就是當前的中間節點int rootValue = postorder[postorder.size() - 1];TreeNode* root = new TreeNode(rootValue);// 葉子節點if (postorder.size() == 1) return root;// 第三步：找切割點int delimiterIndex;for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;}// 第四步：切割中序數組，得到 中序左數組和中序右數組// 第五步：切割后序數組，得到 后序左數組和后序右數組// 第六步root->left = traversal(中序左數組, 后序左數組);root->right = traversal(中序右數組, 后序右數組);return root;
}

難點大家應該發現了，就是如何切割，以及邊界值找不好很容易亂套。

此時應該注意確定切割的標準，是左閉右開，還有左開右閉，還是左閉右閉，這個就是不變量，要在遞歸中保持這個不變量。

首先要切割中序數組，為什么先切割中序數組呢？

切割點在后序數組的最后一個元素，就是用這個元素來切割中序數組的，所以必要先切割中序數組。

中序數組相對比較好切，找到切割點（后序數組的最后一個元素）在中序數組的位置，然后切割，如下代碼中我堅持左閉右開的原則：

// 找到中序遍歷的切割點
int delimiterIndex;
for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {if (inorder[delimiterIndex] == rootValue) break;
}// 左閉右開區間：[0, delimiterIndex)
vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
// [delimiterIndex + 1, end)
vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );

接下來就要切割后序數組了。

首先后序數組的最后一個元素指定不能要了，這是切割點也是當前二叉樹中間節點的元素，已經用了。

后序數組的切割點怎么找？

后序數組沒有明確的切割元素來進行左右切割，不像中序數組有明確的切割點，切割點左右分開就可以了。

此時有一個很重的點，就是中序數組大小一定是和后序數組的大小相同的（這是必然）。

中序數組我們都切成了左中序數組和右中序數組了，那么后序數組就可以按照左中序數組的大小來切割，切成左后序數組和右后序數組。

代碼如下：

// postorder 舍棄末尾元素，因為這個元素就是中間節點，已經用過了
postorder.resize(postorder.size() - 1);// 左閉右開，注意這里使用了左中序數組大小作為切割點：[0, leftInorder.size)
vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
// [leftInorder.size(), end)
vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());

此時，中序數組切成了左中序數組和右中序數組，后序數組切割成左后序數組和右后序數組。

接下來可以遞歸了，代碼如下：

root->left = traversal(leftInorder, leftPostorder);
root->right = traversal(rightInorder, rightPostorder);

完整代碼如下：

class Solution {Map<Integer, Integer> map;  // 方便根據數值查找位置public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的數值對應位置map.put(inorder[i], i);}return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前閉后開}public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {// 參數里的范圍都是前閉后開if (inBegin >= inEnd || postBegin >= postEnd) {  // 不滿足左閉右開，說明沒有元素，返回空樹return null;}int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍歷的最后一個元素在中序遍歷中的位置TreeNode root = new TreeNode(inorder[rootIndex]);  // 構造結點int lenOfLeft = rootIndex - inBegin;  // 保存中序左子樹個數，用來確定后序數列的個數root.left = findNode(inorder, inBegin, rootIndex,postorder, postBegin, postBegin + lenOfLeft);root.right = findNode(inorder, rootIndex + 1, inEnd,postorder, postBegin + lenOfLeft, postEnd - 1);return root;}
}

前序和中序遍歷的解決方法和上面講解的中序和后序的解決方法思想一樣。

Map<Integer,Integer> map = new HashMap<>();int[] preorder;int[] inorder;public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;this.inorder = inorder;for(int i = 0 ; i < inorder.length ; i++){map.put(inorder[i],i);}return findNode(0,preorder.length,0,inorder.length);}public TreeNode findNode(int preBegin,int preEnd,int inBegin,int inEnd){if(preBegin >= preEnd || inBegin >= inEnd){return null;}int index = map.get(preorder[preBegin]);int lenOfLeft = index - inBegin;TreeNode node = new TreeNode(preorder[preBegin]);node.left = findNode(preBegin + 1, preBegin + lenOfLeft + 1,inBegin,index);node.right = findNode(preBegin + lenOfLeft + 1, preEnd,index + 1, inEnd);return node;}