沈阳网站建设本地化技术服务,东莞网站建设营销网站,厦门seo网站推广,保定曲阳网站建设题1#xff1a;
指路#xff1a;491. 非递减子序列 - 力扣#xff08;LeetCode#xff09;
思路与代码#xff1a;
对于这个题我们应该想起我们做过的子集问题#xff0c;就是在原来的问题上加一个去重操作。我们用unordered_set集合去重#xff0c;集合中使用过的元…题1
指路491. 非递减子序列 - 力扣LeetCode
思路与代码
对于这个题我们应该想起我们做过的子集问题就是在原来的问题上加一个去重操作。我们用unordered_set集合去重集合中使用过的元素我们要对结果集进行横向去重集合中有的元素就已经被用过弃之。代码如下
class Solution {private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, int startIndex) {if (path.size() 2 path.size() nums.size()) {result.push_back(path);}unordered_setint uset; // 元素去重集合 for (int i startIndex; i nums.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, i 1);path.pop_back(); }}
public:vectorvectorint findSubsequences(vectorint nums) {backtracking(nums, 0);return result;}
};
题2
指路46. 全排列 - 力扣LeetCode
思路与代码
排列与组合的不同点在于组合无顺序排列有顺序。例如[1, 2, 3] 和[3, 2, 1]对于组合来说二者无区别对于排列来说二者有区别。所以这也是单层循环逻辑中的不同所在我们每次从数组i 0的地方开始遍历如果遇到未遍历过的元素则加入路径集反之如果是已经遍历过的元素则跳过本轮循环继而寻找下一元素。其中我们用used数组来标识元素是否用过。初始化为false用过则赋值为true。最终当路径集大小与原数组集相等时加入最终结果集。代码如下
class Solution {private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used) {if (path.size() nums.size()) {result.push_back(path);return ;}for (int i 0; i nums.size(); i) { // 0开始全排列if (used[i] true) continue; // 用过的元素跳过直接取下一个元素used[i] true;path.push_back(nums[i]);backtracking(nums, used);used[i] false; // 回溯path.pop_back();}}
public:vectorvectorint permute(vectorint nums) {vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
};
题3
指路47. 全排列 II - 力扣LeetCode
思路与代码
相似于上题排列本题不同点在于有了重复元素这就意味着会出现重复子序列所以需要我们做的就是去重。相似于组合总和Ⅱ的去重操作。我们将数组排序得到一个升序数组如果相邻两个元素相等时只需要得到一个数的子序列即可。代码如下
class Solution {private:vectorvectorint result;vectorint path;void backtracking(vectorint nums, vectorbool used) {if (path.size() nums.size()) {result.push_back(path);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] false) {used[i] true;path.push_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}}}
public:vectorvectorint permuteUnique(vectorint nums) {vectorbool used (nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, used);return result;}
};
