建德网站,建筑装饰装修工程公司,网页制作公司列举自己的优势,张槎建网站公司491.非减子序列
题目链接. - 力扣#xff08;LeetCode#xff09;
这里和子集问题||很像#xff0c;但是这里要的是非递减的子序列#xff0c;要按照给的数组的顺序来进行排序#xff0c;就是如果我给定的数组是[4,4,3,2,1]#xff0c;如果用子集||的做法先进行排序得到…491.非减子序列
题目链接. - 力扣LeetCode
这里和子集问题||很像但是这里要的是非递减的子序列要按照给的数组的顺序来进行排序就是如果我给定的数组是[4,4,3,2,1]如果用子集||的做法先进行排序得到[1,2,3,4,4]那我就会收集得到[1,2][2,3][3,4][4,4]等等子集但是这道题的话我得到的集合只有[4,4]就是这里我只从我给的数组里进行排序给非递减的子集。
去结点操作
一、进行树层去重
但是用之前的方法排序后看used数组里面我两个元素到底用没用已经不可行了所以这里加了一个set数组来进行去重只要我没有和之前相同的元素那就继续取
这里不用回溯掉used 我觉得是之前回溯是因used定义是在主函数里面你不手动回溯那个值不会主动变为0而这里直接定义函数里在每一层循环外面我一进去递归就重开了一个set数组天然的就不用进行回溯了
二、去掉递减的结点
去结点的时候我们把我们遍历到的节点和收集到的结点进行比较如果这个节点比我们收集到的结点小了那么我们硬塞进去就不是递增序列了所以直接continue进行收集下一个结点。
class Solution {
public:
vectorintpath;
vectorvectorint result;
void backtracing (vectorint nums,int startindex){if(path.size()1){result.push_back(path);//子集在2到2以上再进行收集}unordered_setint used;//每一层都会重置usedfor(int istartindex;inums.size();i){if(!path.empty()nums[i]path.back()||used.find(nums[i])!used.end()){continue;//去掉要进行递减的结点和树层去重}path.push_back(nums[i]);used.insert(nums[i]);//把nums[i]的值放used里面好进行判断到底用没用过backtracing (nums,i1);path.pop_back();}
}vectorvectorint findSubsequences(vectorint nums) {backtracing (nums,0);return result;}
};
46.全排列
题目链接https://leetcode.cn/problems/permutations
要求是同一个数不能重复选取嘛所以要用到used数组
这个是排列问题需要返回和传进来数组大小相等的全排列数组所以排列问题就不用设置startindex了因为不用对前面的数进行去重但是要设置一个used数组不能重复选择同一个元素。
class Solution {//正确代码
public:
vectorintpath;
vectorvectorintresult;void backtracking(vectorint nums,vectorboolused){if(path.size()nums.size()){result.push_back(path);return;}for(int i0;inums.size();i){if(used[i]true){//用过的数就跳过continue;}path.push_back(nums[i]);used[i]true;backtracking(nums,used);path.pop_back();used[i]false;}}vectorvectorint permute(vectorint nums) {vectorboolused(nums.size(),false);backtracking(nums,used);return result;}
}; 注意这里只能是递归到used数组为true的时候continue进行下一次选取如果像我一样直接对used等于0来进行判断的话那它等于1的时候就不会有限制就会一直进行递归进行循环直到栈空离大谱..
for(int i0;inums.size();i){//错误代码if(used[i]false){path.push_back(nums[i]);used[i]true;}backtracking(nums,used);path.pop_back();used[i]false;}
47.全排列||
题目链接https://leetcode.cn/problems/permutations-ii
这道题和46.全排列不太一样的就是这里给的nums数组有重复值比如nums给[1,1,2]那么如果我按没有重复数的做法来做的话就会有两个[1,1,2]那这里就是不允许的所以我们要在上一道题的基础上多进行一次去重就是像组合问题一样进行树层去重同一树层上的数continue不再选取。
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums, vectorbool used) {if (nums.size() path.size()) {result.push_back(path);//到了nums大小就收集到result然后返回return;}for (int i 0; i nums.size(); i) {if (i 0 nums[i] nums[i - 1] used[i - 1] false)continue;//树层去重if (used[i] true)//选过的不再重复选continue;path.push_back(nums[i]);used[i] true;backtracking(nums, used);used[i] false;path.pop_back();}}vectorvectorint permuteUnique(vectorint nums) {vectorbool used(nums.size(), false);sort(nums.begin(), nums.end());//把nums排序used数组好进行比较进行树层去重backtracking(nums, used);return result;}
};
