其他:

今日總結
往期打卡

---

77. 組合

跳轉: 77. 組合

學習: 代碼隨想錄公開講解

問題:

給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。

你可以按 任何順序 返回答案。

思路:

遞歸傳入剩余需選個數,歸零終止.
剪枝: 用需選個數可以求出遍歷范圍,及至少給以后的選擇留出足夠的數
因為使用dfs,一次只需要存儲一條路徑即可

使用迭代法需要儲存大量的子狀態. 而且因為空間需要提前預定義,所以不方便做剪枝.
其上下層之間的操作相對獨立,沒有明顯練習,所以無法做遞推.

復雜度:

• 時間復雜度: $O(k^2)$
• 空間復雜度: $O(k)$

代碼:

class Solution {int k;List<List<Integer>> ans;private final List<Integer> path = new ArrayList<>();void dfs(int n){int d = k-path.size();if(d==0) {ans.add(new ArrayList<>(path));return;}for(int j=n;j>=d;j--){path.add(j);dfs(j-1);path.remove(path.size()-1);}}public List<List<Integer>> combine(int n, int k) {this.k = k;ans = new ArrayList<>();dfs(n);return ans;}
}

---

216. 組合總和 III

跳轉: 216. 組合總和 III

學習: 代碼隨想錄公開講解

問題:

找出所有相加之和為 n 的 k 個數的組合，且滿足下列條件：

• 只使用數字1到9
• 每個數字 最多使用一次

返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。

思路:

遞歸的終止條件改為兩個,和大于n或還需選擇數為0

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {List<List<Integer>> ans ;List<Integer> path = new ArrayList<>();int sum = 0;int n;void dfs(int k,int start){if(sum>n) return;if(k==0){if(sum==n) ans.add(new ArrayList<>(path));return;}for(int i=start;i<=9;i++){sum+=i;path.add(i);dfs(k-1,i+1);sum-=i;path.remove(path.size()-1);}}public List<List<Integer>> combinationSum3(int k, int n) {ans = new ArrayList<>();this.n = n;dfs(k,1);return ans;}
}

---

17. 電話號碼的字母組合

跳轉: 17. 電話號碼的字母組合

學習: 代碼隨想錄公開講解

問題:

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

給出數字到字母的映射如下（與電話按鍵相同）。注意 1 不對應任何字母。

思路:

終止條件為按過全部電話鍵,因為這題求的是全排列,所以沒法做剪枝操作

復雜度:

• 時間復雜度: $O(3^n)$
• 空間復雜度: $O(n)$

代碼:

class Solution {private static final String[] MAPPING = new String[]{ "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> ans;private char[] path;void backtracking(char[] list,int index){if(index==list.length){ans.add(new String(path));return;}int k = list[index]-50;for(char c:MAPPING[k].toCharArray()){path[index] = c;backtracking(list,index+1);}}public List<String> letterCombinations(String digits) {int n = digits.length();ans = new ArrayList<>();if(n==0) return ans;path = new char[n];backtracking(digits.toCharArray(),0);return ans;}
}

---

2537. 統計好子數組的數目(每日一題)

跳轉: 2537. 統計好子數組的數目

學習: 靈茶山艾府題解

問題:

給你一個整數數組 nums 和一個整數 k ，請你返回 nums 中 好 子數組的數目。

一個子數組 arr 如果有 至少 k 對下標 (i, j) 滿足 i < j 且 arr[i] == arr[j] ，那么稱它是一個 好 子數組。

子數組 是原數組中一段連續 非空 的元素序列。

思路:

這題可以使用滑動窗口加哈希表,每次收縮到剛好滿足條件,計算時加上被拋棄的前綴數
求的是選出兩個相同元素,對于單個元素來講,剛好是0,1,3,6,每次加一個n-1到n

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼:

class Solution {public long countGood(int[] nums, int k) {int n = nums.length;Map<Integer,Integer> map = new HashMap<>();int sum = 0;long ans = 0;for(int i=0,pre = 0;i<n;i++){sum+=map.getOrDefault(nums[i],0);map.put(nums[i],map.getOrDefault(nums[i],0)+1);while(sum>=k){map.put(nums[pre],map.get(nums[pre])-1);sum-=map.get(nums[pre]);pre++;// System.out.println(pre);}ans=ans+pre;}return ans;}
}

---

516. 最長回文子序列

跳轉: 516. 最長回文子序列

學習: 靈茶山艾府題解

問題:

給你一個字符串 s ，找出其中最長的回文子序列，并返回該序列的長度。

子序列定義為：不改變剩余字符順序的情況下，刪除某些字符或者不刪除任何字符形成的一個序列。

思路:

題目中不要求連續,但給出了回文序列的條件.
滿足條件就都選,不滿足條件留使子串最大的一邊
dp數組值的含義是當前區間內能選出的最大的回文子串長度

復雜度:

• 時間復雜度: $O(n^2)$
• 空間復雜度: $O(n)$

代碼(遞推空間優化):

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[] f = new int[n];for(int i=n-1;i>=0;i--){f[i] = 1;int pre = 0;for(int j=i+1;j<n;j++){int tmp = f[j];if(s.charAt(i)==s.charAt(j)) f[j] = pre+2;else f[j] = Math.max(f[j],f[j-1]);pre = tmp;}}return f[n-1];}
}

復雜度:

• 時間復雜度: $O(n^2)$
• 空間復雜度: $O(n^2)$

代碼(遞歸+記憶化搜索):

class Solution {int[][] cache;int dfs(String s,int l,int r){if(l==r) return 1;if(l>r) return 0;if(cache[l][r]!=-1) return cache[l][r];if(s.charAt(l)==s.charAt(r)) return cache[l][r] = dfs(s,l+1,r-1)+2;else return cache[l][r] = Math.max(dfs(s,l+1,r),dfs(s,l,r-1));}public int longestPalindromeSubseq(String s) {cache = new int[s.length()][s.length()];for(int[] i:cache){Arrays.fill(i,-1);}return dfs(s,0,s.length()-1);}
}

代碼(遞推):

class Solution {public int longestPalindromeSubseq(String s) {int n = s.length();int[][] f = new int[n][n];for(int i=n-1;i>=0;i--){for(int j=0;j<n;j++){if(i==j) f[i][j] = 1;else if(i>j) continue;else {if(s.charAt(i)==s.charAt(j)) f[i][j] = f[i+1][j-1]+2;else f[i][j] = Math.max(f[i+1][j],f[i][j-1]);}}            }return f[0][n-1];}
}

---

1039. 多邊形三角剖分的最低得分

跳轉: 1039. 多邊形三角剖分的最低得分

學習: 靈茶山艾府題解

問題:

你有一個凸的 n 邊形，其每個頂點都有一個整數值。給定一個整數數組 values ，其中 values[i] 是第 i 個頂點的值（即 順時針順序 ）。

假設將多邊形 剖分 為 n - 2 個三角形。對于每個三角形，該三角形的值是頂點標記的乘積，三角剖分的分數是進行三角剖分后所有 n - 2 個三角形的值之和。

返回 多邊形進行三角剖分后可以得到的最低分 。

思路:

遍歷區間找所有可能的三角形,每次劃分繼續二分區間遍歷

復雜度:

• 時間復雜度: $O(n^2)$
• 空間復雜度: $O(n^2)$

代碼(遞推):

class Solution {public int minScoreTriangulation(int[] values) {int n = values.length;int[][] f = new int[n][n];for(int i = n-3;i>=0;i--){for(int j=i+2;j<n;j++){f[i][j] = Integer.MAX_VALUE;for(int k=i+1;k<j;k++){f[i][j] = Math.min(f[i][j],f[i][k]+f[k][j]+values[i]*values[k]*values[j]);}}}return f[0][n-1];}
}

代碼(遞歸):

class Solution {int[] v;int[][] cache;int dfs(int l,int r){if(r<=l+1) return 0;if(cache[l][r]!=0) return cache[l][r];int min = Integer.MAX_VALUE>>1;for(int i=l+1;i<r;i++){int tmp = dfs(l,i)+dfs(i,r)+v[i]*v[l]*v[r];if(tmp<min) min = tmp;}return cache[l][r]=min;}public int minScoreTriangulation(int[] values) {int n = values.length;cache = new int[n][n];v = values;return dfs(0,n-1);}
}

---

543. 二叉樹的直徑

跳轉: 543. 二叉樹的直徑

學習: 靈茶山艾府題解

問題:

給你一棵二叉樹的根節點，返回該樹的 直徑 。

二叉樹的 直徑 是指樹中任意兩個節點之間最長路徑的 長度 。這條路徑可能經過也可能不經過根節點 root 。

兩節點之間路徑的 長度 由它們之間邊數表示。

思路:

當前最大是左最大+右最大+1
然后返回左右最大的一條數量

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {int ans=0;int dfs(TreeNode root){if(root==null) return 0;int l = dfs(root.left);int r = dfs(root.right);ans = Math.max(ans,l+r);return Math.max(l,r)+1;}public int diameterOfBinaryTree(TreeNode root) {dfs(root);return ans;}
}

---

124. 二叉樹中的最大路徑和

跳轉: 124. 二叉樹中的最大路徑和

學習: 靈茶山艾府題解

問題:

二叉樹中的 路徑 被定義為一條節點序列，序列中每對相鄰節點之間都存在一條邊。同一個節點在一條路徑序列中 至多出現一次 。該路徑 至少包含一個 節點，且不一定經過根節點。

路徑和 是路徑中各節點值的總和。

給你一個二叉樹的根節點 root ，返回其 最大路徑和 。

思路:

dfs,上一題求數量改求和了
不過需要注意,子樹如果為負不應該選,所以可以直接返回時和0比較一下

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {int ans=Integer.MIN_VALUE;int dfs(TreeNode root){if(root==null) return 0;int l = dfs(root.left);int r = dfs(root.right);ans = Math.max(ans,l+r+root.val);return Math.max(Math.max(l,r)+root.val,0);}public int maxPathSum(TreeNode root) {dfs(root);return ans;}
}

---

2246. 相鄰字符不同的最長路徑

跳轉: 2246. 相鄰字符不同的最長路徑

學習: 靈茶山艾府題解

問題:

給你一棵 樹（即一個連通、無向、無環圖），根節點是節點 0 ，這棵樹由編號從 0 到 n - 1 的 n 個節點組成。用下標從 0 開始、長度為 n 的數組 parent 來表示這棵樹，其中 parent[i] 是節點 i 的父節點，由于節點 0 是根節點，所以 parent[0] == -1 。

另給你一個字符串 s ，長度也是 n ，其中 s[i] 表示分配給節點 i 的字符。

請你找出路徑上任意一對相鄰節點都沒有分配到相同字符的 最長路徑 ，并返回該路徑的長度。

思路:

父節點的父節點一定比子節點的父節點小嗎? 顯然這題不是這樣的,我們無法排出一個合理的順序.
所以這題不能使用倒序遍歷,只能自頂向下遍歷.

題目中給的是父節點數組,所以需要構造和子節點的哈希.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(1)$

代碼:

class Solution {private List<Integer>[] g;private char[] s;private int ans;int dfs(int x){int maxLen = 0;for(int y:g[x]){int len = dfs(y)+1;if(s[y]!=s[x]){ans = Math.max(ans,maxLen+len);maxLen = Math.max(maxLen,len);}}return maxLen;}public int longestPath(int[] parent, String s) {int n = parent.length;this.s = s.toCharArray();g = new ArrayList[n];Arrays.setAll(g, e -> new ArrayList<>());for(int i=1;i<n;i++){g[parent[i]].add(i);}dfs(0);return ans+1;}
}

---

總結

練習了組合回溯以及區間DP,樹性DP

回溯算法模板框架:

void backtracking(參數) {if (終止條件) {存放結果;return;}for (選擇：本層集合中元素（樹中節點孩子的數量就是集合的大小）) {處理節點;backtracking(路徑，選擇列表); // 遞歸回溯，撤銷處理結果}
}

往期打卡

代碼隨想錄算法訓練營第十八天

代碼隨想錄算法訓練營第十七天

代碼隨想錄算法訓練營周末三

代碼隨想錄算法訓練營第十六天

代碼隨想錄算法訓練營第十五天

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天