网站换域名怎么办,电商广告,app网站怎么制作,自己做的网站出现乱码第七章 回溯算法 part05
1.LeetCode. 递增子序列
1.1题目链接#xff1a;491.递增子序列
文章讲解#xff1a;代码随想录 视频讲解#xff1a;B站卡哥视频
1.2思路#xff1a;这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。这又是子集491.递增子序列
文章讲解代码随想录 视频讲解B站卡哥视频
1.2思路这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。这又是子集又是去重是不是不由自主的想起了刚刚讲过的90.子集II。就是因为太像了更要注意差别所在要不就掉坑里了在90.子集II (opens new window)中我们是通过排序再加一个标记数组来达到去重的目的。而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。所以不能使用之前的去重逻辑
为了有鲜明的对比我用[4, 7, 6, 7]这个数组来举例抽象为树形结构如图
1.3附加代码如下所示
class Solution {
public:vectorvectorintresult;vectorintpath;void backtracking(vectorintnums,int startindex){if(path.size()1){result.push_back(path);// 注意这里不要加return要取树上的节点}unordered_setintuset;// 使用set对本层元素进行去重for(int istartindex;inums.size();i){if(!path.empty()nums[i]path.back()||uset.find(nums[i])!uset.end()){continue;}uset.insert(nums[i]);// 记录这个元素在本层用过了本层后面不能再用了path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {result.clear();path.clear();backtracking(nums,0);return result;}
};2.LeetCode. 全排列
2.1题目链接46.全排列
文章讲解代码随想录 视频讲解B站卡哥视频
2.2思路首先排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合这和之前分析的子集以及组合所不同的地方。可以看出元素1在[1,2]中已经使用过了但是在[2,1]中还要在使用一次1所以处理排列问题就不用使用startIndex了。但排列问题需要一个used数组标记已经选择的元素如图橘黄色部分所示: 2.3附加代码如下所示
class Solution {
public:vectorvectorintresult;vectorintpath;void backtracking(vectorintnums,vectorboolused){if(path.size()nums.size()) // 此时说明找到了一组{result.push_back(path);return;}for(int i0;inums.size();i){if(used[i]true)continue;// path里已经收录的元素直接跳过path.push_back(nums[i]);used[i]true;backtracking(nums,used);path.pop_back();used[i]false;}}vectorvectorint permute(vectorint nums) {result.clear();path.clear();vectorboolused(nums.size(),0);backtracking(nums,used);return result;}
};3.LeetCode.全排列 II
3.1题目链接47.全排列 II
文章讲解代码随想录 视频讲解B站卡哥视频
3.2思路这道题目和46.全排列 (opens new window)的区别在与给定一个可包含重复数字的序列要返回所有不重复的全排列。这里又涉及到去重了。在40.组合总和II (opens new window)、90.子集II (opens new window)我们分别详细讲解了组合问题和子集问题如何去重。那么排列问题其实也是一样的套路。还要强调的是去重一定要对元素进行排序这样我们才方便通过相邻的节点来判断是否重复使用了。
以示例中的 [1,1,2]为例 为了方便举例已经排序抽象为一棵树去重过程如图
3.3附加代码如下所示
//树层不可以重复取值树枝可以重复取值
class Solution {
public:vectorvectorintresult;vectorintpath;void backtracking(vectorintnums,vectorboolused){if(path.size()nums.size()) // 此时说明找到了一组{result.push_back(path);return;}for(int i0;inums.size();i){// used[i - 1] true说明同一树枝nums[i - 1]使用过// used[i - 1] false说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过if(i0nums[i-1]nums[i]used[i-1]false)continue;//去重要进行树层去重树枝不去重used[i-1]false表明这是同一个树层if(used[i]true)continue;//同一树枝中去过的数不能再取值了path.push_back(nums[i]);used[i]true;backtracking(nums,used);path.pop_back();used[i]false;}}vectorvectorint permuteUnique(vectorint nums) {result.clear();path.clear();vectorboolused(nums.size(),false);sort(nums.begin(),nums.end());backtracking(nums,used);return result;}
};
