网站建设首页模板,w3c网站怎么做,连锁酒店网站建设公司,网站关键词数量一、LeetCode 491.递增子序列 题目链接/文章讲解/视频讲解#xff1a;https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 状态#xff1a;已解决 1.思路 这道题看似和90题差不多#xff0c;都是求子集并且有重复元素#xff0c;但实则…一、LeetCode 491.递增子序列 题目链接/文章讲解/视频讲解https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html 状态已解决 1.思路 这道题看似和90题差不多都是求子集并且有重复元素但实则大有不同。因为这道题要求给出非递减子序列因此我们不能用排序的方式来去重。那该怎么办呢其实40题的去重逻辑的核心就是要我们在同层递归树层的时候不再选取已经出现过的值。 在40题中我们用nums[i]nums[i-1]和used[i-1]0两个共同的条件来判定此时是树层重复还是树枝重复。那失去了nums[i]有序的这个条件又如何判定了其实很简单因为我们只需要控制同一树层的时候不选取已经选取过的值也就是说只要我们在树层开始前设个数组让这个数组存放已经出现过的值那么如果这次for循环选取的值数组中已经有了就说明该值已经出现过我们跳过不做后续操作就好。做完了发现可行并且老师也是这个做法
2.代码实现 每层递归用来存放for循环已经选取过的值的数组可以采用set实现也可以用map实现。我这里用的map老师讲解用的set。
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums,int startIndex){if(path.size()1)//注意集合中至少两个元素result.push_back(path);if(startIndexnums.size()){return ;}unordered_mapint,int used;for(int istartIndex;inums.size();i){if(istartIndex used.find(nums[i])! used.end() used[nums[i]]1){continue;}//判断是否已经出现过该值used.find(nums[i])! used.end()很重要if(path.size()0 || nums[i]path[path.size()-1]){path.push_back(nums[i]);used[nums[i]]1;backtracking(nums,i1);path.pop_back();}}}vectorvectorint findSubsequences(vectorint nums) {path.clear();result.clear();backtracking(nums,0);return result;}
};
二、46.全排列 题目链接/文章讲解/视频讲解https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html 状态已解决 1.思路 排列与组合的区别在于排列要看集合元素之间的顺序而组合不看也就是说对排列来说{12}和{21}是两个集合而对组合而言二者是同一个集合。我们在做组合题时曾经说过为了避免组合时出现相同组合{12}、{2,1}令startIndex根据上层i的取值来取使得startIndexi因此要使组合变排列只需将startIndex的取值范围变一下变为从0开始取值确保原数组后面的元素也可以作为集合中靠前的元素。不过为了确保前后取到同一个元素值我们需要记录下来每层递归所取的值让后续递归不再取它们也就是要进行树枝去重用used数组实现。
2.完整代码
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums,vectorint used){if(path.size() nums.size()){result.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);used[i] 0;path.pop_back();}}vectorvectorint permute(vectorint nums) {vectorint used(nums.size(),0);backtracking(nums,used);return result;}
};
三、47.全排列 II 题目链接/文章讲解/视频讲解https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html 状态已解决 1.思路 因为有重复元素又是排列题故此题实则就是40题双重去重和46题的一个结合。需要在46题一个树枝去重和一个树层去重的操作具体怎么操作可以去看40题的解法。注意对于used操作的用法在组合和排序中used数组含义是相同的但是组合主要是用来佐证确定树层去重而排序是用来确保树枝去重的。
2.代码实现
class Solution {
public:vectorint path;vectorvectorint result;void backtracking(vectorint nums,vectorint used){if(path.size() nums.size()){result.push_back(path);return ;}for(int i0;inums.size();i){if(i0 nums[i]nums[i-1] used[i-1]0) continue;if(used[i]1) continue;path.push_back(nums[i]);used[i]1;backtracking(nums,used);used[i]0;path.pop_back();}}vectorvectorint permuteUnique(vectorint nums) {sort(nums.begin(),nums.end());vectorint used(nums.size(),0);backtracking(nums,used);return result;}
};
