创业网站搭建设计方案,大连建设工程信息网官网官网官,o2o平台有哪些行业,2345网址大全官网491.非递减子序列 思路#xff1a;这道题最开始的时候#xff0c;我想到两个问题#xff1a;一个是如何维持递增的序列#xff0c;一个是如何去重#xff0c;写了一版代码#xff0c;用的前面的去重方法#xff0c;但是遇到一个case始终过不了#xff0c;[1,2,3,4,5,6,…491.非递减子序列 思路这道题最开始的时候我想到两个问题一个是如何维持递增的序列一个是如何去重写了一版代码用的前面的去重方法但是遇到一个case始终过不了[1,2,3,4,5,6,7,8,9,10,1,1,1,1,1]肯定是过不了的因为其不是一个有序序列并且必须保持其原本的大小顺序故这道题只能使用哈希表来去重这道题其实力扣上面还有点小坑就是他给的两个示例特么都是排序的但是题目又没提误导人 错误的思考
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums,int index,vectorbool used){if(path.size()2){result.push_back(path);}if(indexnums.size()){return;}for(int iindex;inums.size();i){if(!path.empty() path.back()nums[i]) continue;if(i0 nums[i-1]nums[i] used[i-1]false)continue;path.push_back(nums[i]);used[i]true;backtracking(nums,i1,used);used[i]false;path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(),false);backtracking(nums,0,used);return result;}
};正确写法 又学会一种新的去重同一层的方法 class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums,int index){if(path.size()2){result.push_back(path);}if(indexnums.size()){return;}unordered_setint myset;for(int iindex;inums.size();i){if((!path.empty() nums[i]path.back())||myset.find(nums[i])!myset.end()) continue;myset.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;}
};46.全排列 思路第一次接触全排列的问题体会其与组合分割问题的不同之处 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);used[i]false;path.pop_back();}}vectorvectorint permute(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(),false);backtracking(nums,used);return result;}
};47.全排列II 思路这道题就是把前两道题的技巧结合起来了其这道题可以用used这个数组直接进行去重其实对于排列问题使用的used数组就是用来标记当前是否使用过的 class Solution {
public:vectorvectorint result;vectorint path;void backtracking(vectorint nums,vectorbool used){if(path.size()nums.size()){result.push_back(path);return;}unordered_setint myset;for(int i0;inums.size();i){if(used[i]true||myset.find(nums[i])!myset.end()) continue;myset.insert(nums[i]);used[i]true;path.push_back(nums[i]);backtracking(nums,used);used[i]false;path.pop_back();}}vectorvectorint permuteUnique(vectorint nums) {result.clear();path.clear();vectorbool used(nums.size(),false);backtracking(nums,used);return result;}
};
