flashfxp怎么上传对应网站空间,分切机网站建设,政务服务网站建设标准,棋牌网站搭建公司题目#xff1a;491.递增子序列、46.全排列、47.全排列 II
参考链接#xff1a;代码随想录
491.递增子序列
思路#xff1a;一开始按照基本回溯的模板来写。当路径长度大于2时加入ans#xff0c;结束条件为开始位置到达末尾。for循环部分遍历第一个加入path中的数#…题目491.递增子序列、46.全排列、47.全排列 II
参考链接代码随想录
491.递增子序列
思路一开始按照基本回溯的模板来写。当路径长度大于2时加入ans结束条件为开始位置到达末尾。for循环部分遍历第一个加入path中的数如果目前的数小于path末尾则直接考虑下一个数。写完后运行发现没有去重处理但本题的去重和上题集合2不同不能排序不是相邻也可能重复比如[4,4,5,4]会产生3个[4,4]去重方法我一开始没想到。 一开始的错误代码
class Solution {
public: vectorvectorint ans;vectorint path;void backtracking(vectorint nums,int begin){//begin为开始取的位置if(path.size()2){ans.push_back(path);}if(beginnums.size()){return;}for(int ibegin;inums.size()-1;i){if(path.size()0nums[i]path.back()){//如果目前遍历的数小于path末尾则不满足递增情况直接考虑下一个数continue;}path.push_back(nums[i]);backtracking(nums,i1);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {backtracking(nums,0);return ans;}
};看了解析需要对每一层进行去重由于重复元素不相邻只能用集合来判断重复。不能再简单的用used数组了。时间复杂度O(n*2^n)。 标答
class Solution {
public: vectorvectorint ans;vectorint path;void backtracking(vectorint nums,int begin){//begin为开始取的位置if(path.size()2){ans.push_back(path);}if(beginnums.size()){return;}unordered_setint set;//对本层去重for(int ibegin;inums.size()-1;i){if(path.size()0nums[i]path.back()||set.find(nums[i])!set.end()){//如果目前遍历的数小于path末尾则不满足递增情况直接考虑下一个数。或者在同一层出现重复。continue;}path.push_back(nums[i]);set.insert(nums[i]);backtracking(nums,i1);path.pop_back();//这里不需要set中移出nums[i]因为是对整层的去重}}vectorvectorint findSubsequences(vectorint nums) {backtracking(nums,0);return ans;}
};注意使用set在回溯的时候不用移出元素因为是对整层去重。set也是每一层for循环之前定义一个。 看了标答发现由于题目说了数值范围[-100,100]因此可以使用数组做哈希表
class Solution {
private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {if (path.size() 1) {result.push_back(path);}int used[201] {0}; // 这里使用数组来进行去重操作题目说数值范围[-100, 100]for (int i startIndex; i nums.size(); i) {if ((!path.empty() nums[i] path.back())|| used[nums[i] 100] 1) {continue;}used[nums[i] 100] 1; // 记录这个元素在本层用过了本层后面不能再用了path.push_back(nums[i]);backtracking(nums, i 1);path.pop_back();}}
public:vectorvectorint findSubsequences(vectorint nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};46.全排列
思路排列的组合的最大区别就是有顺序的考虑。比如第一个元素选的2那么后面1和3还需要考虑而组合就只需要考虑3了。所以在回溯模板的区别中首先是for循环必须每次都是从0到结束那么如何判断那些元素可以选呢我们继续采用used数组当for遍历的元素已经用过则直接continue否则加入路径。当路径长度为数组长度时将路径添加到ans。时间复杂度O(n*n!)注意这个时间复杂度就是所有排列方式的数量A(n,n)乘以生成每一个答案需要的n次push_back。
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,vectorint used){if(path.size()nums.size()){ans.push_back(path);return;}for(int i0;inums.size();i){//每次都要全部遍历if(used[i]1){continue;}path.push_back(nums[i]);used[i]1;backtracking(nums,used);path.pop_back();used[i]0;}}vectorvectorint permute(vectorint nums) {vectorint used(nums.size(),0);backtracking(nums,used);return ans;}
};47.全排列 II
思路一开始想的就是在上题基础上加一个每层去重由于排列每次for都要遍历所有元素不是相邻情况故每层使用了一个set去重。
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,vectorint used){if(path.size()nums.size()){ans.push_back(path);}unordered_setint set;for(int i0;inums.size();i){//每一层去重这里不是相邻重复情况使用setif(used[i]1||set.find(nums[i])!set.end()){continue;}path.push_back(nums[i]);used[i]1;set.insert(nums[i]);backtracking(nums,used);path.pop_back();used[i]0;}}vectorvectorint permuteUnique(vectorint nums) {vectorint used(nums.size(),0);backtracking(nums,used);return ans;}
};看完标答发现可以先排序然后只用一个used就可以完成所有功能。判断相邻方法和之前的组合一样。时间复杂度O(n*n!)。
class Solution {
public:vectorvectorint ans;vectorint path;void backtracking(vectorint nums,vectorint used){if(path.size()nums.size()){ans.push_back(path);}for(int i0;inums.size();i){if(used[i]1||i0nums[i]nums[i-1]used[i-1]0){continue;}path.push_back(nums[i]);used[i]1;backtracking(nums,used);path.pop_back();used[i]0;}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());vectorint used(nums.size(),0);backtracking(nums,used);return ans;}
};对于回溯算法的时间复杂度可以直接看这里。
