当前位置：首页 > news >正文

代码随想录算法训练营：26/60

news 来源：原创 2024/9/21 12:26:18

非科班学习算法day26 | LeetCode491:非递减子序列，Leetcode46:全排列，Leetcode47:全排列||

介绍

包含LC的两道题目，还有相应概念的补充。

一、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}// 创建setunordered_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: 全排列

题目链接：46. 全排列 - 力扣（LeetCode）

题目解析

排列和组合的区别在于有顺序要求

C++代码如下：

class Solution {
public:// 顺序要求-没有重复-收集叶子节点// 结果vector<vector<int>> res;// 路径vector<int> path;// 回溯函数-不需要indexvoid 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：一定要记得排序