【Weekly Algorithm】算法周记之《代码随想录》回溯（二）
学习小结
本周跟随《代码随想录》学习回溯的剩余题目，如八皇后，全排列等问题，当初看上去可怕的题目，在回溯的套路下，显得也没那么难，重点在于理解整个回溯的树遍历过程。
通常回溯部分的函数无返回值，但当回溯只求全树唯一一个解时，比如[[全排列]][[解数独]]，可将回溯函数返回值设为 bool 类型，在一个叶子为 true，层层上传，避免无用遍历。
回溯
组合总和II
- 代码随想录
- 40. 组合总和 II - 力扣（LeetCode）
- 题意，与[[组合总和III]]类似，但待选数组内出现重复元素，且结果的组合不能重复
- 方法，重点是分清两种去重，一种是同一树支的去重（纵向），一种是同一树层的去重（横向），两者都可以通过用 used 数组实现，前者要求 used 中同值点不可同时 true 才能加入结果，后者要求同值点必须 true 该点才能加入结果；换句话，used 中 ture 的点说明在同一树支（路径）上
- 参考代码随想录思路的解法
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
36
37
38
39class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void back_track(vector<int> &candidates, int target, vector<int> &used, int sum, int start_index) {
// 终止条件，和过大或相等
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
}
for (int i = start_index; i < candidates.size(); i++) {
// 去重，used[i-1] true 说明在同一个路径上
// used[i-1] flase 说明在同一层，属于要去除的情况
if (i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false) {
continue;
}
used[i] = true;
path.push_back(candidates[i]);
sum += candidates[i];
back_track(candidates, target, used, sum, i+1);
sum -= candidates[i];
path.pop_back();
used[i] = false;
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> used = vector<int>(candidates.size());
result.clear();
path.clear();
sort(candidates.begin(), candidates.end()); // 使数组有序
back_track(candidates, target, used, 0, 0);
return result;
}
}; 分割回文串
- 代码随想录
- 131. 分割回文串 - 力扣（LeetCode）
- 题意，给一个字符串，把字符串分成多个回文串组成的字符串数组，返回所有组合
- 方法，难点有两，一是如何分割字符串，二是如何判断回文串。
对于一，采用 start_index 作为本层分割字符串的起点，用 for 循环决定重点，递归更新 start_index；对于二，就用 for 循环前后检测是否相等，可以用动态规划优化速度，但太麻烦了，等dp学完再回来罢：） - 参照代码随想录思路的解法
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
36
37class Solution {
private:
bool isRevStr(string s) { // 判断回文串，前读和后读一样，其实前半和后半一样就行
for (int i = 0, j = s.size()-1; i < j; i++,j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}
vector<vector<string>> result;
vector<string> path;
void back_track(string s, int start_index) {
if (start_index >= s.size()) { // start_index 为分割线，分割到字符串外说明前面都割好了
result.push_back(path);
}
for (int i = start_index; i < s.size(); i++) {
// 从 start_index 到 i 割串，检测
string tmp = s.substr(start_index, i-start_index+1);
//cout << tmp << endl;
if (isRevStr(tmp)) {
path.push_back(tmp);
back_track(s, i+1);
path.pop_back();
}
}
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
back_track(s, 0);
return result;
}
}; 复原IP地址
- 代码随想录
- 93. 复原 IP 地址 - 力扣（LeetCode）
- 题意，有一串数字，可能是 IP 地址，要求返回该数字可能组成所有有效的 IP 地址（最少4位、最多12位，中间有三个点分隔的数字字符串）
- 方法，与[[分割回文串]]类似，但这里限制了分割的个数，所以需要变量记录，且注意前导0和把字符串转整数的操作
- 参考代码随想录思路的解法
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59class Solution {
private:
vector<string> result;
bool isValid(const string &s, int start_index, int end_index) {
// 满足字符串是0-255，无前导0，且是数字
if (start_index > end_index) { // 去除最后 i+2 后 start_index 比 end 大的情况，下面代码没考虑
return false;
}
if (s[start_index] == '0' && start_index != end_index) { // 前导0
return false;
}
int num = 0; // 记录数值
for (int i = start_index; i <= end_index; i++) {
num *=10;
char c = s[i];
if (c < '0' || c > '9') {
return false;
}
num += int(c - '0');
if (num > 255) {// 过大
return false;
}
}
return true;
}
void backTrack(string s, int start_index, int point_num) {
if (point_num == 3 && isValid(s, start_index, s.size()-1)) {
result.push_back(s);
return;
}
cout << s << endl;
for (int i = start_index; i < s.size(); i++) {
if (isValid(s, start_index, i)) {
s.insert(s.begin()+i+1, '.'); // 采用插点的方式来分割字符串，插入点的下标为 i+1
point_num++;
backTrack(s, i+2, point_num);
point_num--;
s.erase(s.begin()+i+1);
}
else {
break; // 要么数组过大，要么有非法字符，后面的都一定不符合
}
}
}
public:
vector<string> restoreIpAddresses(string s) {
result.clear();
if (s.size() < 4 || s.size() > 12) { // ip 地址最少4位，每处最多3位，共12位
return result;
}
backTrack(s, 0, 0);
return result;
}
}; 子集
- 代码随想录
- 78. 子集 - 力扣（LeetCode）
- 题意，给一个整数数组，求其所有子集
- 方法，回溯，注意由于集合内无序性，元素不能重复；该题其实遍历了树上所有节点，而之前的组合、分割则是收集树中的叶子节点。
- 参考代码随想录思路的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTrack(vector<int> &nums, int start_index) {
if (start_index > nums.size()) {
return;
}
result.push_back(path);
for (int i = start_index; i < nums.size(); i++) {
path.push_back(nums[i]);
backTrack(nums, i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backTrack(nums, 0);
return result;
}
}; 子集II
- 代码随想录
- 90. 子集 II - 力扣（LeetCode）
- 题意，相比[[子集]]，数组中会有重复的数字元素，求的结果子集仍然要求一样
- 方法，类似[[组合总和II]]，通过 used 去除同层同值的节点造成子集重复的问题
- 陆爻齐自己解法（与代码随想录思路相近）
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
36class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTrack(vector<int> &nums, int start_index, vector<int> &used) {
// 记录结果，遍历每个节点
result.push_back(path);
if (start_index >= nums.size()) {
return;
}
for (int i = start_index; i < nums.size(); i++) {
// 排除那些同层同值的节点
if (i>0 && nums[i] == nums[i-1] && used[i-1] == false) {
continue;
}
used[i] = true;
path.push_back(nums[i]);
backTrack(nums, i+1, used);
path.pop_back();
used[i] = false;
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
// 需要有序才能方便去除同层相同数，不排序的话需要哈希表
sort(nums.begin(), nums.end());
vector<int> used = vector<int>(nums.size());
backTrack(nums, 0, used);
return result;
}
}; 非递减子序列
- 代码随想录
- 491. 非递减子序列 - 力扣（LeetCode）
- 题意，给一个数组，要求返回其中所有至少长度为2的递增子序列
- 方法，看似与[[子集II]]相似，只要排下序，回溯即可；其实不行，因为一旦排序，整个序列都是递增的，那么如何去重呢？那就要用到 hash。不过本地的数字大小在 -100 到 100，所以用大小为 201 的数组把数字映射上去即可
- 参考代码随想录思路的代码
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
30class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTrack(vector<int> &nums, int start_index) {
if (path.size() >= 2) {
result.push_back(path); // 添加结果条件
// 不需要 return，因为需要遍历整个树的节点
vector<int> used = vector<int>(201); // 把-100至100两个个数，映射到0-200 的数组上
for (int i = start_index; i < nums.size(); i++) {
if (used[nums[i]+100] == 1) continue; // 去重
if (path.size() > 0 && nums[i] < path[path.size()-1]) continue; // 使得新加值不小于path末值
used[nums[i]+100] = 1; // 只管本层去重，所以记录有就行，不需要恢复0
path.push_back(nums[i]);
backTrack(nums, i+1);
path.pop_back();
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
result.clear();
path.clear();
backTrack(nums, 0);
return result;
}
}; 全排列
- 代码随想录
- 46. 全排列 - 力扣（LeetCode）
- 题意，把一个无重复数字的数组所有可能的全排列按任意顺序返回答案
- 方法，运用回溯，不过由于要求全排列，也就是可能之前的值在下面也用得到，所以不用 start_index
- 参考代码随想录思路的解法
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
29class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTrack(vector<int> &nums,vector<int> &used) {
if (path.size() == nums.size()) { // 到叶子节点，说明全排列完成
result.push_back(path);
}
for (int i = 0; i < nums.size(); i++) {
if (used[i] == 1) continue; // 排除用过数字的情况
used[i] = 1;
path.push_back(nums[i]);
backTrack(nums, used);
path.pop_back();
used[i] = 0;
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
result.clear();
path.clear();
vector<int> used = vector<int>(nums.size());
backTrack(nums, used);
return result
}
}; 全排列II
- 代码随想录
- 47. 全排列 II - 力扣（LeetCode）
- 题意，与[[全排列]]类似，但数组中出现重复元素
- 方法，在[[全排列]]的基础上，加入去重，不过这个去重其实在树枝去重和树层去重都是可以的，但对树层去重效率会高很多，可以举个【1，1，1】的例子试试
- 参考代码随想录思路的代码
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
32class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backTrack(vector<int> &nums, vector<int> &used) {
if (path.size() == nums.size()) {
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (i>0 && nums[i] == nums[i-1] && used[i-1]==0) continue;
if (used[i] == 0) {
used[i] = 1;
path.push_back(nums[i]);
backTrack(nums, used);
path.pop_back();
used[i] = 0;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
result.clear();
path.clear();
vector<int> used(nums.size());// 映射这个值是否用过
sort(nums.begin(), nums.end());
backTrack(nums, used);
return result;
}
}; 重新安排行程
- 代码随想录
- 332. 重新安排行程 - 力扣（LeetCode）
- 题意，给一系列大小为 2 的字符串数组，当作机票的出发地和目的地，要求从 JFK 出发，每张票要用且只能使用一次，要求最后返回一条有效路程，若有多个有效路程则返回字典序最小的那条
- 方法，主要是如何在回溯过程中记录回溯历程，这里使用了一个 unordered_map<string, map<string, int>> 来记录，翻译为自然语言，就是 unordered_map<出发地, map<目的地，票数>>，map是有序的，直接遍历就是字典序从小到大
- 参考代码随想录思路的方法
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
36
37class Solution {
private:
vector<string> result;
unordered_map<string,map<string, int>> rec_tic;
bool backTrack(int ticket_num) {
if (ticket_num + 1 == result.size()) {
return true;
}
map<string, int> &target = rec_tic[result[result.size()-1]];
for (pair<const string, int> &travel : target) {
if (travel.second > 0) {
travel.second--;
result.push_back(travel.first);
if (backTrack(ticket_num)) return true;
result.pop_back();
travel.second++;
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
result.clear();
rec_tic.clear();
for (vector<string> tic : tickets) {
rec_tic[tic[0]][tic[1]]++;
}
result.push_back("JFK");
backTrack(tickets.size());
return result;
}
}; N皇后
- 代码随想录
- 51. N 皇后 - 力扣（LeetCode）
- 题意，国际棋盘上，皇后这个棋子同行、同列、两斜线上都是唯一，给棋盘大小，要求摆皇后的所有方案
- 方法，把行作为递归深度，到底就是得出结果，然后代入回溯模板即可，由于在二维数组上（棋盘）从上往下遍历，故检查下棋位置是否合法只要检测上面即可
- 参考代码随想录思路的方法，时隔许久再做，好像也没那么恐怖哈
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55class Solution {
private:
vector<vector<string>> result;
vector<string> chess_board;
bool isValid(int row, int col, int n) {
// 检查同列
for (int i = 0; i < row; i++) {
if (chess_board[i][col] == 'Q') {
return false;
}
}
// 由于由上向下，故向上检查斜角即可
// 检查左上方的，45度
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chess_board[i][j] == 'Q') {
return false;
}
}
// 检查右上方，135度
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chess_board[i][j] == 'Q') {
return false;
}
}
return true;
}
void backTrack(int n, int row) {
if (row == n) {
result.push_back(chess_board);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col, n)) {
chess_board[row][col] = 'Q';
backTrack(n, row+1);
chess_board[row][col] = '.';
}
}
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
chess_board.clear();
chess_board = vector<string>(n, string(n, '.'));
backTrack(n, 0);
return result;
}
}; 解数独
- 代码随想录
- 37. 解数独 - 力扣（LeetCode）
- 题意，给出一个二维数组，其中待填部分为 .，要求填入合适数字完成数独
- 方法，和[[八皇后]]类似的棋盘问题，也是需要二重回溯，区别就是在判断终止条件，由于该题需要遍历一整棵树找一个合理方案，故让回溯方法返回布尔值，以去除不必要的遍历。
- 参考代码随想录思路的解法
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class Solution {
private:
bool isValid(int row, int col, char k, vector<vector<char>> &board, int size) {
for (int i = 0; i < size; i++) { // 同列是否有相同值
if (board[i][col] == k) {
return false;
}
}
for (int j = 0; j < size; j++) { // 同行是否有相同值
if (board[row][j] == k) {
return false;
}
}
int start_row = row/3*3; // 同九方格起始坐标
int start_col = col/3*3;
for (int i = start_row; i < start_row + 3; i++) {
for (int j = start_col; j < start_col + 3; j++)
if (board[i][j] == k) {
return false;
}
}
return true;
}
bool backTrack(vector<vector<char>> &board, int size) {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (board[i][j] != '.') continue;
for (char k = '1'; k <= '9'; k++) {
if (isValid(i, j, k, board, size)) {
board[i][j] = k;
if (backTrack(board, size)) return true;
board[i][j] = '.';
}
}
return false; // 如果有一个可填处 9 个值都填不了，那么这个方案不可行
}
}
return true; // 如果全填完了，说明必定出现答案了
}
public:
void solveSudoku(vector<vector<char>>& board) {
backTrack(board, board.size());
}
};
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 LuYaoQi's Blogs！
相关推荐
2024-11-17
【Weekly Algorithm】算法周记之《代码随想录》动态规划（一）
学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...
2024-11-24
【Weekly Algorithm】算法周记之《代码随想录》动态规划（二）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...
2024-12-01
【Weekly Algorithm】算法周记之《代码随想录》动态规划（三）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...
2024-12-15
【Weekly Algorithm】算法周记之《代码随想录》动态规划（五）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...
2025-01-12
【Weekly Algorithm】算法周记之《代码随想录》动态规划（六）
学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...
2025-02-09
【Weekly Algorithm】算法周记之《代码随想录》单调栈和图论（一）
学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...
系列文章