佛山网站建设公司哪专业,安卓app在线生成,WordPress中文章固定链接,成都百度推广账户优化Leetcode 491. 非递减子序列
链接#xff1a;491. 非递减子序列
thought:
设 stack 中最后一个值的位置为 last。如果 stack 为空#xff0c;则 last -1。 设当前正在处理的位置为 pos。如果在 nums 的子区间 [last1, pos) 中#xff0c;存在和 nums[pos] 相同的值…Leetcode 491. 非递减子序列
链接491. 非递减子序列
thought:
设 stack 中最后一个值的位置为 last。如果 stack 为空则 last -1。 设当前正在处理的位置为 pos。如果在 nums 的子区间 [last1, pos) 中存在和 nums[pos] 相同的值则当前 nums[pos] 必须丢弃不然会产生重复的子序列。 完整C代码如下
class Solution {
public:vectorvectorint findSubsequences(vectorint nums) {vectorvectorint res;vectorint path;backtracking(res, nums, path, 0);return res;}private:void backtracking(vectorvectorint res, vectorint nums, vectorint path, int start) {if (path.size() 2) // 如果当前递增子序列长度大于等于2则将其加入结果集res.push_back(path);unordered_setint seen; // 用一个集合来记录当前层已经使用过的数字避免重复//注意为当前层for (int i start; i nums.size(); i) {if ((!path.empty() nums[i] path.back()) || seen.count(nums[i])) // 如果当前数字小于上一个数字不符合递增或者已经使用过则跳过continue;seen.insert(nums[i]); // 将当前数字加入集合path.push_back(nums[i]); // 将当前数字加入递增序列backtracking(res, nums, path, i 1); // 递归搜索下一个位置path.pop_back(); // 回溯将当前数字从递增序列中删除}}
}; Leetcode 46. 全排列
链接46. 全排列
thought:
设置bool数组记录当前位置数是否已经使用过若使用过直接跳过
完整C代码如下
class Solution {
public:vectorvectorint permute(vectorint nums) {vectorintpath;vectorvectorintres;vectorboolused(nums.size(),false);backtracking(nums,path,res,used);return res;}void backtracking(vectorint nums,vectorintpath,vectorvectorintres,vectorboolused){if(path.size()nums.size()){res.push_back(path);return;}for(int i0;inums.size();i){if(used[i])continue;used[i]true;path.push_back(nums[i]);backtracking(nums,path,res,used);//递归path.pop_back();//回溯used[i]false;//回溯}}
};Leetcode 47. 全排列 II
链接47. 全排列 II
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) {// used[i - 1] true说明同一树枝nums[i - 1]使用过// used[i - 1] false说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过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) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vectorbool used(nums.size(), false);backtracking(nums, used);return result;}
};
