宣傳類的網(wǎng)站怎么做/廣告軟文代理平臺
來源0x3f:https://space.bilibili.com/206214
回溯分為【子集型回溯】【組合型回溯】【排列型回溯】
文章目錄
- 回溯基本概念
- [17. 電話號碼的字母組合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/)
- 子集型回溯(分割問題也可以看作枚舉分割點==>子集型)
- [78. 子集](https://leetcode.cn/problems/subsets/)
- 方法一:輸入的視角(每個節(jié)點可以選擇選和不選)
- 方法二:答案的角度(枚舉第一個數(shù)選誰、第二個數(shù)選誰)
- [131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/)
- 思路:設每兩個相鄰字符間有逗號,枚舉每個逗號結束位置。這樣就變成了[78. 子集]問題
- [784. 字母大小寫全排列](https://leetcode.cn/problems/letter-case-permutation/)
- [93. 復原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses/)
- 組合型回溯(剪枝技巧)
- [77. 組合](https://leetcode.cn/problems/combinations/)
- [216. 組合總和 III](https://leetcode.cn/problems/combination-sum-iii/)
- [22. 括號生成](https://leetcode.cn/problems/generate-parentheses/)
- 排列型回溯(棋盤問題也是排列型回溯)
- [46. 全排列](https://leetcode.cn/problems/permutations/)
- [51. N 皇后](https://leetcode.cn/problems/n-queens/)
回溯基本概念
回溯三問:
1、當前操作?
2、子問題?
3、下一個子問題?
void backtracking(參數(shù)) {if (終止條件) {存放結果;return;}for (選擇:本層集合中元素(樹中節(jié)點孩子的數(shù)量就是集合的大小)) {處理節(jié)點;backtracking(路徑,選擇列表); // 遞歸回溯,撤銷處理結果}
}
17. 電話號碼的字母組合
難度中等2314
給定一個僅包含數(shù)字 2-9
的字符串,返回所有它能表示的字母組合。答案可以按 任意順序 返回。
給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對應任何字母。
示例 1:
輸入:digits = "23"
輸出:["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2:
輸入:digits = ""
輸出:[]
示例 3:
輸入:digits = "2"
輸出:["a","b","c"]
提示:
0 <= digits.length <= 4
digits[i]
是范圍['2', '9']
的一個數(shù)字。
回溯三問:
1、當前操作? 枚舉 path[i] 要填入的字母
2、子問題? 構造字符串>=i 的部分
3、下一個子問題? 構造字符串>= i+1 的部分
class Solution {private static final String[] arr = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};List<String> res = new ArrayList<>();public List<String> letterCombinations(String digits) {if(digits.equals("")) return res;dfs(digits, 0, new StringBuilder());return res;}public void dfs(String digits, int i, StringBuilder sb){if(i == digits.length()){res.add(sb.toString());return;}String str = arr[digits.charAt(i) - '0'];for(int j = 0; j < str.length(); j++){sb.append(str.charAt(j));dfs(digits, i+1, sb);sb.deleteCharAt(sb.length()-1);}}
}
子集型回溯(分割問題也可以看作枚舉分割點==>子集型)
子集型回溯:每個元素都可以選和不選
回溯三問:
**1、當前操作?**枚舉第 i 個數(shù)選/不選
2、子問題? 從下標 >=i 的數(shù)字中構造子集
3、下一個子問題? 從下標 >=i+1 的數(shù)字中構造子集
78. 子集
難度中等1931
給你一個整數(shù)數(shù)組 nums
,數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集(冪集)。
解集 不能 包含重復的子集。你可以按 任意順序 返回解集。
示例 1:
輸入:nums = [1,2,3]
輸出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
輸入:nums = [0]
輸出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums
中的所有元素 互不相同
題解:
方法一:輸入的視角(每個節(jié)點可以選擇選和不選)
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur;public List<List<Integer>> subsets(int[] nums) {cur = new ArrayList<>();dfs(nums, 0);return res;}// 每個節(jié)點可以選擇選和不選public void dfs(int[] nums, int i){if(i == nums.length){res.add(new ArrayList<>(cur));return;}dfs(nums, i+1);cur.add(nums[i]);dfs(nums, i+1);cur.remove(cur.size()-1);}
}
方法二:答案的角度(枚舉第一個數(shù)選誰、第二個數(shù)選誰)
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur;public List<List<Integer>> subsets(int[] nums) {cur = new ArrayList<>();dfs(nums, 0);return res;}// 每個節(jié)點可以選擇選和不選public void dfs(int[] nums, int i){// 關鍵在這里, 遞歸入口每次記錄答案res.add(new ArrayList<>(cur));if(i == nums.length){return;}for(int j = i; j < nums.length; j++){cur.add(nums[j]);dfs(nums, j+1);cur.remove(cur.size()-1);}}
}
131. 分割回文串
難度中等1387
給你一個字符串 s
,請你將 s
分割成一些子串,使每個子串都是 回文串 。返回 s
所有可能的分割方案。
回文串 是正著讀和反著讀都一樣的字符串。
示例 1:
輸入:s = "aab"
輸出:[["a","a","b"],["aa","b"]]
示例 2:
輸入:s = "a"
輸出:[["a"]]
提示:
1 <= s.length <= 16
s
僅由小寫英文字母組成
思路:設每兩個相鄰字符間有逗號,枚舉每個逗號結束位置。這樣就變成了[78. 子集]問題
方法二:答案的角度(枚舉字串結束位置)
class Solution {List<List<String>> res = new ArrayList<>();List<String> cur;public List<List<String>> partition(String s) {cur = new ArrayList<>();dfs(s, 0);return res;}public void dfs(String s, int i){if(i == s.length()){res.add(new ArrayList<>(cur));return;}//枚舉字串結束位置(設以j結尾是否符合要求)for(int j = i; j < s.length(); j++){//判斷一下[i, j] 部分是否為回文串String str = s.substring(i, j+1);if(isrev(str)){cur.add(str);dfs(s, j+1);cur.remove(cur.size()-1);}}}public boolean isrev(String str){int left = 0, right = str.length()-1;while(left < right){if(str.charAt(left) != str.charAt(right))return false;left++; right--;}return true;}
}
784. 字母大小寫全排列
難度中等515
給定一個字符串 s
,通過將字符串 s
中的每個字母轉變大小寫,我們可以獲得一個新的字符串。
返回 所有可能得到的字符串集合 。以 任意順序 返回輸出。
示例 1:
輸入:s = "a1b2"
輸出:["a1b2", "a1B2", "A1b2", "A1B2"]
示例 2:
輸入: s = "3z4"
輸出: ["3z4","3Z4"]
提示:
1 <= s.length <= 12
s
由小寫英文字母、大寫英文字母和數(shù)字組成
題解:
DFS 回溯 看到題目要求組合或者集合,馬上想到可以用回溯法:
回溯法本來是說對于每個元素都先考慮放它的情況,再考慮不放它的情況;
放在這道題的背景里就是,對于每個字母,先考慮放它,再考慮放它的另一種大小寫形式。
class Solution {List<String> res = new ArrayList<>();public List<String> letterCasePermutation(String s) {dfs(s, 0, new StringBuilder());return res;}public void dfs(String s, int i, StringBuilder sb){if(i == s.length()){res.add(new String(sb.toString()));return;}// 不改sb.append(s.charAt(i));dfs(s, i+1, sb);sb.deleteCharAt(sb.length()-1);//改if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z'){sb.append((char)(s.charAt(i) - 32));dfs(s, i+1, sb);}else if(s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'){sb.append((char)(s.charAt(i) + 32));dfs(s, i+1, sb);}if((s.charAt(i) >= 'a' && s.charAt(i) <= 'z') || (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z'))sb.deleteCharAt(sb.length()-1);}
}
93. 復原 IP 地址
難度中等1146收藏分享切換為英文接收動態(tài)反饋
有效 IP 地址 正好由四個整數(shù)(每個整數(shù)位于 0
到 255
之間組成,且不能含有前導 0
),整數(shù)之間用 '.'
分隔。
- 例如:
"0.1.2.201"
和"192.168.1.1"
是 有效 IP 地址,但是"0.011.255.245"
、"192.168.1.312"
和"192.168@1.1"
是 無效 IP 地址。
給定一個只包含數(shù)字的字符串 s
,用以表示一個 IP 地址,返回所有可能的有效 IP 地址,這些地址可以通過在 s
中插入 '.'
來形成。你 不能 重新排序或刪除 s
中的任何數(shù)字。你可以按 任何 順序返回答案。
示例 1:
輸入:s = "25525511135"
輸出:["255.255.11.135","255.255.111.35"]
示例 2:
輸入:s = "0000"
輸出:["0.0.0.0"]
示例 3:
輸入:s = "101023"
輸出:["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示:
1 <= s.length <= 20
s
僅由數(shù)字組成
class Solution {List<String> res = new ArrayList<>(); List<String> tmp = new ArrayList<>();public List<String> restoreIpAddresses(String s) {dfs(s, 0);return res;}public void dfs(String s, int begin){if(tmp.size() == 4 && begin != s.length()) return;if(tmp.size() == 4 && begin == s.length()){res.add(String.join(".",tmp));return;}//枚舉分割點for(int j = begin; j < s.length() && j < begin+3; j++){String str = s.substring(begin, j+1);// 每個整數(shù)位于 0 到 255 之間組成if(Integer.parseInt(str) <= 255){// 不能含有前導 0if(str.length() > 1 && str.charAt(0) == '0'){return;}tmp.add(str);dfs(s, j+1);tmp.remove(tmp.size()-1);}else{return;}}}
}
組合型回溯(剪枝技巧)
77. 組合
難度中等1284
給定兩個整數(shù) n
和 k
,返回范圍 [1, n]
中所有可能的 k
個數(shù)的組合。
你可以按 任何順序 返回答案。
示例 1:
輸入:n = 4, k = 2
輸出:
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]
示例 2:
輸入:n = 1, k = 1
輸出:[[1]]
提示:
1 <= n <= 20
1 <= k <= n
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n;k = _k;dfs(1);return res;}public void dfs(int i){if(cur.size() == k){ // d == 0res.add(new ArrayList<>(cur));return;}for(int j = i; j <= n - (k - cur.size()) + 1 ; j++){cur.add(j);dfs(j+1);cur.remove(cur.size() - 1);}}
}
相同方式倒著遍歷的寫法
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n; k = _k;dfs(n);return res;}public void dfs(int i){int d = k - cur.size();// 還要選 d 個數(shù)if(d == 0){ res.add(new ArrayList<>(cur));return;}for(int j = i; j >= d; j--){cur.add(j);dfs(j-1);cur.remove(cur.size() - 1);}}
}
216. 組合總和 III
難度中等622
找出所有相加之和為 n
的 k
個數(shù)的組合,且滿足下列條件:
- 只使用數(shù)字1到9
- 每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次,組合可以以任何順序返回。
示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。
示例 2:
輸入: k = 3, n = 9
輸出: [[1,2,6], [1,3,5], [2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
沒有其他符合的組合了。
示例 3:
輸入: k = 4, n = 1
輸出: []
解釋: 不存在有效的組合。
在[1,9]范圍內(nèi)使用4個不同的數(shù)字,我們可以得到的最小和是1+2+3+4 = 10,因為10 > 1,沒有有效的組合。
提示:
2 <= k <= 9
1 <= n <= 60
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();int k;public List<List<Integer>> combinationSum3(int _k, int n) {k = _k;dfs(9, n);return res;}public void dfs(int i, int target){int d = k - cur.size();// 還要選 d 個數(shù)//剪枝// 首項+末項 *項數(shù) /2 仍然比target小,就不用遞歸了if(target < 0 || target > (i*2 - d + 1) * d / 2)return; // d = 0 , (i*2 - d + 1) * d / 2也是等于0的,就不用判斷target = 0 了if(d == 0){ res.add(new ArrayList<>(cur));return;}for(int j = i; j >= d; j--){cur.add(j);dfs(j-1, target-j);cur.remove(cur.size() - 1);}}
}
22. 括號生成
難度中等3091
數(shù)字 n
代表生成括號的對數(shù),請你設計一個函數(shù),用于能夠生成所有可能的并且 有效的 括號組合。
示例 1:
輸入:n = 3
輸出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
輸入:n = 1
輸出:["()"]
提示:
1 <= n <= 8
class Solution {int n;char[] path;List<String> res = new ArrayList<>();public List<String> generateParenthesis(int n) {this.n = n;path = new char[n * 2];dfs(0, 0);return res;}public void dfs(int i, int open){if(i == n * 2){res.add(new String(path));}if(open < n){ // 可以填左括號path[i] = '(';dfs(i+1, open+1);}if(i - open < open){ // 不可以填左括號了,只能填右括號}path[i] = ')';dfs(i+1, open);}}
}
排列型回溯(棋盤問題也是排列型回溯)
排列型和組合型的區(qū)別:組合中不能有{1,2} {2,1} 同時存在,因為他們是相同的組合
46. 全排列
難度中等2411
給定一個不含重復數(shù)字的數(shù)組 nums
,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。
示例 1:
輸入:nums = [1,2,3]
輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
輸入:nums = [0,1]
輸出:[[0,1],[1,0]]
示例 3:
輸入:nums = [1]
輸出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums
中的所有整數(shù) 互不相同
class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> cur = new ArrayList<>();boolean[] visit;public List<List<Integer>> permute(int[] nums) {visit = new boolean[nums.length];dfs(0, nums);return res;}public void dfs(int i, int[] nums){if(i == nums.length){res.add(new ArrayList<>(cur));return;}for(int k = 0; k < nums.length; k++){if(visit[k] == false){visit[k] = true;cur.add(nums[k]);dfs(i+1, nums);cur.remove(cur.size()-1);visit[k] = false;}}}}
51. N 皇后
難度困難1648
按照國際象棋的規(guī)則,皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。
n 皇后問題 研究的是如何將 n
個皇后放置在 n×n
的棋盤上,并且使皇后彼此之間不能相互攻擊。
給你一個整數(shù) n
,返回所有不同的 n 皇后問題 的解決方案。
每一種解法包含一個不同的 n 皇后問題 的棋子放置方案,該方案中 'Q'
和 '.'
分別代表了皇后和空位。
示例 1:
輸入:n = 4
輸出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋:如上圖所示,4 皇后問題存在兩個不同的解法。
示例 2:
輸入:n = 1
輸出:[["Q"]]
提示:
1 <= n <= 9
題解:https://leetcode.cn/problems/n-queens/solution/java-c-by-tizzi-i9j0/
class Solution {List<List<String>> ans = new ArrayList<>();int[] row;boolean[] cols, d, ud;int N;public List<List<String>> solveNQueens(int n) {N = n;cols = new boolean[n];d = new boolean[30];ud = new boolean[30];row = new int[n];// 用來保存第幾行第幾列放置Qdfs(0);return ans;}// col【】數(shù)組記錄某列已經(jīng)放過了皇后。col【i】= 1代表第i列已經(jīng)放了一個皇后。// d【】 數(shù)組來記錄某正對角線已經(jīng)放置過了皇后。// ud【】數(shù)組來記錄某反對角線已經(jīng)放置過了皇后。public void dfs(int i){if(i == N){char[] arr = new char[N];Arrays.fill(arr, '.');List<String> g = new ArrayList<>();for(int j = 0; j < N; j++){arr[row[j]] = 'Q';g.add(new String(arr));arr[row[j]] = '.';}ans.add(g);return;}// 選擇一個位置進行放置for(int j = 0; j < N; j++){// 列,對角線、反對角線判斷if (!cols[j] && !d[i + j] && !ud[N - i + j]){cols[j] = d[i+j] = ud[N-i+j] = true;row[i] = j;dfs(i+1);cols[j] = d[i+j] = ud[N-i+j] = false;}}}
}