leetcode_day24

本文最后更新于 2024年8月18日 下午

今日任务:

前言

进入回溯算法篇章,对递归掌握仍然不熟练,尤其是回溯算法,在左的课上写全排列等题目简直惨不忍睹,趁此机会,再次尝试学会回溯算法,每题务必隔天复习重写熟悉

卡哥的题解也要仔细看,综合多篇题解学习。

文章讲解
视频讲解

77. 组合

题目:

给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。

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

思路:

多重for循环就行,但是由于层数不定,所以不能直接for,需要靠递归来实现任意层数循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> ans; //回溯模板1:总答案
vector<int> temp; //回溯模板2:单个答案暂存
void backtracking(int n, int k, int start) {
if(temp.size() == k) { //回溯模板3:递归结束条件:遍历到叶子节点
ans.push_back(temp);
return ;
}
for(int i = start;i <= n - k + temp.size() + 1;i++) {
temp.push_back(i); //回溯模板4:选择当前,进入下一步
backtracking(n, k, i + 1);
temp.pop_back(); //回溯模板5:取消之前操作,回溯
}
}
vector<vector<int>> combine(int n, int k) {
backtracking(n, k, 1);
return ans;
}
};

216. 组合总和Ⅲ

题目:

找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。

思路:

和上一道题很像,卡哥选题还是很有深意的。熟悉模板写法,给出的代码没有剪枝,剪枝写法参见:

代码随想录 | 组合总和iii

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> ans;
vector<int> temp;
void backtracking(int k, int n, int start) {
if(temp.size() == k) {
if(n == 0) ans.push_back(temp);
return;
}
for(int i = start;i <= 9;i++) {
temp.push_back(i);
backtracking(k, n - i, i + 1);
temp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
backtracking(k, n, 1);
return ans;
}
};

17. 电话号码的字母组合

题目:

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

思路:

仍然是不定次数for循环,使用递归来解,同样,剪枝写法参见代码随想录 | 电话号码的字母组合

注意打表方式,值得学习,自己打表还用的unordered_map,结果打出来一堆bug,还是string数组聪明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
vector<string> ans;
string temp;
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
void backtracking(string digits, int begin_for_string) {
if(temp.size() == digits.size()) {
ans.push_back(temp);
return;
}
int digit = digits[begin_for_string] - '0';
string letter = letterMap[digit];
for(int i = 0;i < letter.size();i++) {
temp.push_back(letter[i]);
backtracking(digits, begin_for_string + 1);
temp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
if(digits.size() == 0) return ans;
backtracking(digits, 0);
return ans;
}
};

leetcode_day24
https://novelyear.github.io/2024/06/15/leetcode-day24/
作者
Leoo Yann
更新于
2024年8月18日
许可协议