非科班学习算法day26 | LeetCode491:非递减子序列 ,Leetcode46:全排列 ,Leetcode47:全排列||
介绍
包含LC的两道题目,还有相应概念的补充。
相关图解和更多版本:
代码随想录 (programmercarl.com)https://programmercarl.com/#%E6%9C%AC%E7%AB%99%E8%83%8C%E6%99%AF
一、LeetCode题目
1.LeetCode491:非递减子序列
题目链接:491. 非递减子序列 - 力扣(LeetCode)
题目解析
和前面问题(子集||)最大的区别在于这里不能够排序,所以去重采用更为普遍的set方法;同时关于中止和收集条件要格外注意。
c++代码如下:
class Solution {
public:
// 有重复-不能排序->使用set去重-判断非递减-路径中至少包含2个
// 结果
vector<vector<int>> res;
// 路径
vector<int> path;
// 回溯函数
void backtracking(vector<int>& nums, int index) {
if (path.size() >= 2) {
res.push_back(path); // 不要return
}
// 创建set
unordered_set<int> uset;
for (int i = index; i < nums.size(); i++) {
// 不满足剪枝
if (!path.empty() && path.back() > nums[i])
continue;
// 树层去重
if (uset.find(nums[i]) != uset.end())
continue;
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
注意点1:首先是收集路径,这里是有条件的,要求路径里的元素至少有两个;这里不需要额外写中止条件
注意点2:选用set去重的逻辑是一样的,关键在于理解这个set的位置,set是每一层递归进入时新建的,就负责本层的元素去重记录,所以不需要回溯。
2.Leetcode46: 全排列
题目解析
排列和组合的区别在于有顺序要求
C++代码如下:
class Solution {
public:
// 顺序要求-没有重复-收集叶子节点
// 结果
vector<vector<int>> res;
// 路径
vector<int> path;
// 回溯函数-不需要index
void backtracking(vector<int>& nums, vector<bool> used) {
if (path.size() == nums.size()) {
res.push_back(path); // 需要return结束本层
return;
}
for (int i = 0; i < nums.size(); i++) {
if (used[i])
continue;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used = vector<bool>(nums.size(), false);
backtracking(nums, used);
return res;
}
};
注意点1:首先明确需求就是,不需要排序也不需要index,因为没有重复元素,而且收集的是叶子节点,内容包含所有元素所以不需要index,借助used数组可以在遍历过程中跳过已经选过的元素。
3.Leetcode47:全排列||
题目链接:47. 全排列 II - 力扣(LeetCode)
题目解析
参考子集||还有全排列
C++代码如下:
class Solution {
public:
// 有重复-排序去重-排列-无index
// 结果
vector<vector<int>> res;
// 路径
vector<int> path;
// 回溯函数
void backtracking(vector<int>& nums, vector<bool> used) {
if (path.size() == nums.size()) {
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])
continue;
if (used[i])
continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used = vector<bool>(nums.size(), false);
sort(nums.begin(),nums.end());
backtracking(nums, used);
return res;
}
};
注意点1:一定要记得排序
总结
打卡第 26天,坚持!!!