app网站搭建,上海装修公司排名榜前30名,.net 门户网站,装修网站平台推荐目录
一、#xff08;leetcode 491#xff09;递增子序列
二、#xff08;leetcode 46#xff09;全排列
三、#xff08;leetcode 47#xff09;全排列 II 一、#xff08;leetcode 491#xff09;递增子序列
力扣题目链接 状态#xff1a;去重方法错误。 这道题…目录
一、leetcode 491递增子序列
二、leetcode 46全排列
三、leetcode 47全排列 II 一、leetcode 491递增子序列
力扣题目链接 状态去重方法错误。 这道题和之前全排列的区别就在于不是对同一层的重复元素进行去重而是去除同一父节点下的重复使用元素为了达到这个目的需要使用哈希来判断是否重复注意到数组中值的大小是-100到100之间因此可以直接利用哈希数组进行判断
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint nums, int startIndex){if(path.size() 2){res.emplace_back(path);}int len nums.size();int used[201] {0};for(int i startIndex; i len; i){if((!path.empty() path.back() nums[i]) || used[nums[i] 100] 1){continue;}used[nums[i] 100] 1;path.emplace_back(nums[i]);backtracking(nums, i1);path.pop_back();}}vectorvectorint findSubsequences(vectorint nums) {res.clear();path.clear();backtracking(nums, 0);return res;}
};
二、leetcode 46全排列
力扣题目链接 状态查看思路后AC。 注意全排列和组合子集的最大区别在于全排列的回溯展开每次都是从0开始而不是startIndex因此需要一个used数组来对已经使用过的节点进行记录值得注意的是在pop之后used数组也要进行更新
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint nums, vectorbool used){if(path.size() nums.size()){res.emplace_back(path);return;}for(int i 0; i nums.size(); i){if(used[i]) continue;used[i] true;path.emplace_back(nums[i]);backtracking(nums, used);path.pop_back();used[i] false;}}vectorvectorint permute(vectorint nums) {res.clear();path.clear();vectorbool used(nums.size(), false);backtracking(nums, used);return res;}
};
三、leetcode 47全排列 II
力扣题目链接 状态查看思路后也没AC。 这里的去重逻辑和组合中的树层去重逻辑类似注意细节。
class Solution {
public:vectorvectorint res;vectorint path;void backtracking(vectorint nums, vectorbool used){if(path.size() nums.size()){res.emplace_back(path);return;}for(int i 0; i nums.size(); i){if(i 0 nums[i-1] nums[i] used[i-1] true) continue;if(used[i] false){used[i] true;path.emplace_back(nums[i]);backtracking(nums, used);
