网页设计中用div做网站例子,官网推广方案seo,中信建设有限责任公司总经理,ppt素材大全免费下载491.递增子序列 本题和大家刚做过的 90.子集II 非常像#xff0c;但又很不一样#xff0c;很容易掉坑里。 代码随想录 视频讲解#xff1a;回溯算法精讲#xff0c;树层去重与树枝去重 | LeetCode#xff1a;491.递增子序列_哔哩哔哩_bilibili 一个是去重#xff0c;一…491.递增子序列 本题和大家刚做过的 90.子集II 非常像但又很不一样很容易掉坑里。 代码随想录 视频讲解回溯算法精讲树层去重与树枝去重 | LeetCode491.递增子序列_哔哩哔哩_bilibili 一个是去重一个是判断是否递增去重发生在横向递增发生在纵向。 横向去重需要额外构建一个集合。 Python class Solution:def __init__(self):self.result []self.path []def backtracking(self, nums, start_index):if len(self.path)2:self.result.append(self.path[:])used_set set()for i in range(start_index, len(nums)):if len(self.path)1 and nums[i]self.path[-1]: # 纵向去重continueif nums[i] in used_set: # 横向去重continue used_set.add(nums[i])self.path.append(nums[i])self.backtracking(nums, i1)self.path.pop()returndef findSubsequences(self, nums: List[int]) - List[List[int]]:self.backtracking(nums, 0)return self.result C class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {if (path.size()2) result.push_back(path);unordered_setint uset;for (int istartIndex; inums.size(); i) {if (uset.find(nums[i])!uset.end()) continue;if (!path.empty() nums[i]path.back()) continue;uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i1);path.pop_back();}return;}vectorvectorint findSubsequences(vectorint nums) {backtracking(nums, 0);return result; }
}; 46.全排列 本题重点感受一下排列问题 与 组合问题组合总和子集问题的区别。 为什么排列问题不用 startIndex 代码随想录 视频讲解组合与排列的区别回溯算法求解的时候有何不同| LeetCode46.全排列_哔哩哔哩_bilibili Python: class Solution:def __init__(self):self.result []self.path []def backtracking(self, nums, k):if len(self.path)k:self.result.append(self.path[:])for i in range(len(nums)):self.path.append(nums[i])new_nums nums[:i] nums[i1:]self.backtracking(new_nums, k)self.path.pop()returndef permute(self, nums: List[int]) - List[List[int]]:k len(nums)self.backtracking(nums, k)return self.result C: 用指针实现标记是否使用过更为节省内存和时间。 class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used) {if (path.size()nums.size()) {result.push_back(path);return;}for (int i0; inums.size(); i) {if (used[i] true) continue;used[i] true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}return;}vectorvectorint permute(vectorint nums) {vectorbool used(nums.size(), false);backtracking(nums, used);return result; }
}; 47.全排列 II 本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合可以先自己做一下然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] true 也行used[i - 1] false 也行 代码随想录 视频讲解回溯算法求解全排列如何去重| LeetCode47.全排列 II_哔哩哔哩_bilibili Python: class Solution:def __init__(self):self.result []self.path []def backtracking(self, nums, used):if len(self.path) len(nums):self.result.append(self.path[:])returnuset set()for i in range(len(nums)):if used[i]: continue # 纵向去重if nums[i] in uset: continue # 横向去重uset.add(nums[i])used[i] Trueself.path.append(nums[i])self.backtracking(nums, used)self.path.pop()used[i] Falsereturndef permuteUnique(self, nums: List[int]) - List[List[int]]:nums.sort()used [False] * len(nums)self.backtracking(nums, used)return self.result C class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used) {if (path.size()nums.size()) {result.push_back(path);}unordered_setint uset;for (int i0; inums.size(); i) {if (uset.find(nums[i]) ! uset.end()) continue;if (used[i]true) continue;used[i] true;uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}return;}vectorvectorint permuteUnique(vectorint nums) {vectorbool used(nums.size(), false);backtracking(nums, used);return result; }
};
