-
【leetcode刷题记录（二）】
三、算法技巧
3.1 暴力搜索
3.1.1 回溯算法解题套路框架
框架
result = [] def backtrack(路径, 选择列表): if 满足结束条件: result.add(路径) return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
1、全排列 leetcode
题解：
时间复杂度：O（n x n!）
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; vector<int> vis; void backtrace(vector<int>& nums, vector<int> path) { if(path.size()==nums.size()) { ans.push_back(path); return; } for(int i=0;i<nums.size();i++) { if(vis[i]==0) { vis[i]=1; path.push_back(nums[i]); backtrace(nums, path); path.pop_back(); vis[i]=0; } } } vector<vector<int>> permute(vector<int>& nums) { vis = vector<int>(nums.size(), 0); backtrace(nums, { }); return ans; } };- 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
2、N 皇后 leetcode
题解：
时间复杂度：O（n!）
空间复杂度：O（n）class Solution { public: vector<vector<string> > ans; bool judge(vector<string>& grid, int i, int j, int n) { for(int q=0;q<n;q++) { if(grid[i][q] == 'Q') { return false; } } for(int p=0;p<n;p++) { if(grid[p][j] == 'Q') { return false; } } int new_i = i; int new_j = j; while(new_i>=0 && new_j>=0) { if(grid[new_i][new_j]=='Q') { return false; } new_i--; new_j--; } new_i = i; new_j = j; while(new_i<n && new_j<n) { if(grid[new_i][new_j]=='Q') { return false; } new_i++; new_j++; } new_i = i; new_j = j; while(new_i>=0 && new_j<n) { if(grid[new_i][new_j]=='Q') { return false; } new_i--; new_j++; } new_i = i; new_j = j; while(new_i<n && new_j>=0) { if(grid[new_i][new_j]=='Q') { return false; } new_i++; new_j--; } return true; } void backtrace(vector<string>& grid, int index, int n) { if(index==n) { ans.push_back(grid); return; } for(int i=0;i<n;i++) { if(judge(grid, index, i, n)) { grid[index][i] = 'Q'; backtrace(grid, index+1, n); grid[index][i] = '.'; } } } vector<vector<string>> solveNQueens(int n) { vector<string> grid(n); string kong = ""; for(int i=0;i<n;i++) { kong+='.'; } for(int i=0;i<n;i++) { grid[i]=kong; } backtrace(grid, 0, n); return ans; } };- 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
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
3.1.2 集合划分问题
1、划分为k个相等的子集 leetcode
题解：
时间复杂度：O（k^n）
空间复杂度：O（k）class Solution { public: bool canPartitionKSubsets(vector<int>& nums, int k) { if(k > nums.size()) return false; int sum = accumulate(nums.begin(), nums.end(), 0); if(sum % k != 0) return false; // 记录每个子集中数字之和 bucket.resize(k); // 每个桶中的数字之和应该为target int target = sum/k; // 从大到小放数字 sort(nums.rbegin(), nums.rend()); // index = 0, 表示从0号元素开始遍历 return backtrack(nums, 0, target); } private: // 记录每个子集中数字之和 vector<int> bucket; bool backtrack(vector<int> &nums, int index, int target){ // 如果所有数字遍历完了,是不需要检查bucket中的元素和是否都是target的。因为前面的 if(sum % k != 0) return false; 已经能保证只要所有元素都放入bucket中，那么bucket中的元素和都为target。 if(index == nums.size()){ return true; } // 注意：i 表示第i个子集，index 表示第index个数字 for(int i = 0; i < bucket.size(); i++){ // 如果这个数字放入子集i中使子集i中元素和超出target了 if(bucket[i] + nums[index] > target){ continue; } // 如果 当前子集的元素和 与 前一个子集的元素和 是一样的，那就跳过 if(i > 0 && bucket[i] == bucket[i-1]){ continue; } // 将数字放入子集i中 bucket[i] += nums[index]; // 递归穷举下一个数字的情况 if(backtrack(nums, index + 1, target)){ return true; } // 撤销选择 bucket[i] -= nums[index]; } // 如果 nums[index] 放入哪个子集都不行 return false; } };- 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
- 59
3.1.3 排列/组合/子集问题
1、子集 leetcode
（元素无重不可复选）题解：
时间复杂度：O（n*2^n）
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; void backtrace(vector<int>& nums, int idx, vector<int> path) { ans.push_back(path); for(int i=idx;i<nums.size();i++) { path.push_back(nums[i]); backtrace(nums, i+1, path); path.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { backtrace(nums, 0, { }); return ans; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
2、组合 leetcode
（元素无重不可复选）题解：转化为子集问题
时间复杂度：O( C n k C_{n}^k Cnk×k)
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; vector<int> nums; void backtrace(int idx, int k, vector<int> path) { if(path.size()==k) { ans.push_back(path); return; } for(int i=idx;i<nums.size();i++) { path.push_back(nums[i]); backtrace(i+1, k, path); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { for(int i=1;i<=n;i++) { nums.push_back(i); } backtrace(0, k, { }); return ans; } };- 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
题解：提前剪枝
时间复杂度：O( C n k C_{n}^k Cnk×k)
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; vector<int> nums; void backtrace(int cur, int k, vector<int> path, int n) { if(path.size() + (n - cur) < k) { return; } if(path.size()==k) { ans.push_back(path); return; } path.push_back(nums[cur]); backtrace(cur+1, k, path, n); path.pop_back(); backtrace(cur+1, k, path, n); } vector<vector<int>> combine(int n, int k) { for(int i=1;i<=n;i++) { nums.push_back(i); } backtrace(0, k, { }, n); return ans; } };- 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
3、全排列 leetcode
（元素无重不可复选）题解：
时间复杂度：O(n x n!)
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; vector<int> vis; void backtrace(vector<int>& nums, vector<int> path) { if(path.size()==nums.size()) { ans.push_back(path); return; } for(int i=0;i<nums.size();i++) { if(vis[i]==0) { vis[i]=1; path.push_back(nums[i]); backtrace(nums, path); path.pop_back(); vis[i]=0; } } } vector<vector<int>> permute(vector<int>& nums) { int n = nums.size(); vis.resize(n, 0); backtrace(nums, { }); return ans; } };- 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
4、子集 II leetcode
（元素可重不可复选）题解：
时间复杂度：O（n x 2^n）
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; void backtrace(vector<int>& nums, int idx, vector<int> path) { ans.push_back(path); for(int i=idx;i<nums.size();i++) { if(i>idx && nums[i]==nums[i-1]) continue; path.push_back(nums[i]); backtrace(nums, i+1, path); path.pop_back(); } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); backtrace(nums, 0, { }); return ans; } };- 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
5、组合总和 II leetcode
题解：
时间复杂度：O（n x 2^n）
空间复杂度：O（n）class Solution { public: vector<vector<int> > ans; void backtrace(vector<int>& candidates, int idx, int sum, int target, vector<int> path) { if(sum > target) { return; } if(sum==target) { ans.push_back(path); } for(int i=idx;i<candidates.size();i++) { if(i>idx && candidates[i]==candidates[i-1]) continue; path.push_back(candidates[i]); backtrace(candidates, i+1, sum+candidates[i], target, path); path.pop_back(); } } vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); backtrace(candidates, 0, 0, target, { }); return ans; } };- 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
6、全排列 II leetcode
题解：
时间复杂度：O(n x n!)
空间复杂度：O（n）class Solution { public: vector<vector<int>> ans; vector<int> vis; void backtrace(vector<int>& nums, vector<int> path) { if(path.size()==nums.size()) { ans.push_back(path); return; } for(int i=0;i<nums.size();i++) { if(vis[i]==0) { // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置 if(i>0 && nums[i]==nums[i-1] && vis[i-1]==0) // 如果前面的相邻相等元素没有用过，那么当前元素也不能用，要跳过。只有当前面相等的元素用过了，当前相等元素才能用，这样保持了相对顺序。 continue; vis[i]=1; path.push_back(nums[i]); backtrace(nums, path); path.pop_back(); vis[i]=0; } } } vector<vector<int>> permuteUnique(vector<int>& nums) { sort(nums.begin(), nums.end()); vis.resize(nums.size(), 0); backtrace(nums, { }); return ans; } };- 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
7、组合总和 leetcode
（元素无重可复选）题解：
class Solution { public: vector<vector<int> > ans; void backtrace(vector<int>& candidates, int idx, int sum, int target, vector<int> path) { if(sum>target) { return; } if(sum==target) { ans.push_back(path); return; } for(int i=idx;i<candidates.size();i++) { path.push_back(candidates[i]); backtrace(candidates, i, sum+candidates[i], target, path); path.pop_back(); } } vector<vector<int>> combinationSum(vector<int>& candidates- 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
-
相关阅读:
SQL—— 优化
【Node.js操作SQLite指南】
CLAHE 算法学习 matlab
【多线程】CountDownLatch
ScrollView 源码注解
哈希 -- 位图、布隆过滤器、海量数据处理
Python封装机制及实现方法
java计算机毕业设计计算机公共课程学习资源管理系统MyBatis+系统+LW文档+源码+调试部署
LabVIEW生产者消费者架构
ITSS认证从申报到获得证书需要多长时间？
- 原文地址：https://blog.csdn.net/qq_43557445/article/details/126403532
