目录
非递减子序列
题干
题目:给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中至少有两个元素 。你可以按 任意顺序 返回答案。数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
示例 1:
输入:nums = [4,6,7,7] 输出:[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2:
输入:nums = [4,4,3,2,1] 输出:[[4,4]]
说明:
-
给定数组的长度不会超过15。
-
数组中的整数范围是 [-100,100]。
-
给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。
注意:原数组 nums 不一定有序!
思路和代码
这道题可以在整数数组中找子集的基础上进行调整,我们可以先找出子集大小大于等于 2 的所有子集,若子集满足非递减序列,则插入结果中。同时,数组中可能含有重复元素,因此我们需要进行去重。和之前的去重操作类似,我们需要在树层去重,而不是树枝去重,即在同一层 for 循环中进行去重,而不是对递归去重。注意:我们不可以对数组 nums 进行排序,不然会改变元素的顺序,求出的递增子序列也不同。
递归法
-
递归参数和返回值:参数是传入的整数数组和本层递归的起始位置 startIndex,无返回值。
-
递归结束条件:当遍历完整个数组则返回,写不写终止条件都可以。
-
递归顺序:先判断当前元素是否满足递增序列,且是否不和之前的元素重复,若满足递增且不重复,则继续递归后续的整数数组寻找递增子序列。
class Solution {
public:
vector<int> composition;
vector<vector<int>> result;
void backTracking(vector<int> &nums, int startIndex){
if (composition.size() >= 2) result.push_back(composition); // 子集大小大于等于2,才插入结果
// 写不写终止条件都可以
unordered_set<int> usedValue; // !!!记录在同一层 for 循环中使用过的 Value
for (int i = startIndex; i < nums.size(); ++i) {
if (!composition.empty() && nums[i] < composition.back()){ // 违反递增顺序,continue
continue; // 因为后续可能还有元素,所以并不 return,而是 continue
}
if (usedValue.find(nums[i]) != usedValue.end()) continue; // 去重!
composition.push_back(nums[i]);
usedValue.insert(nums[i]); // 插入遍历过的元素
backTracking(nums,i+1);
composition.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backTracking(nums,0);
return result;
}
};
递归优化
我们在上一个方法中,用了 unordered_map 来记录遍历过的元素,程序运行的时候对 unordered_set 频繁的insert,相对费时间。而本题中数组的元素范围是[-100,100],范围并不大,因此可以用数组直接做哈希映射,效率会提高。
设定一个大小为 201 的 bool 型数组,下标为 0~200,元素 -100 映射到下标为0的数组空间中,元素 100 映射到下标为200的数组空间。
class Solution {
public:
vector<int> composition;
vector<vector<int>> result;
void backTrack(vector<int> &nums, int startIndex){
if (composition.size() >= 2) result.push_back(composition);
// 终止条件写不写都行
bool isUsed[201] = {false}; // 记录元素在同一层 for 循环是否被使用过,初始化为 false
for (int i = startIndex; i < nums.size(); ++i) {
if (!composition.empty() && nums[i] < composition.back()) continue;
if (isUsed[nums[i]+100]) continue; // 若被使用过,则去重,跳过
composition.push_back(nums[i]);
isUsed[nums[i]+100] = true; // 修改当前元素的使用状态
backTrack(nums,i+1);
composition.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backTrack(nums,0);
return result;
}
};
全排列
题干
题目:给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路和代码
递归法
全排列中,每个排列的大小是固定的,我们递归进入下一个排列的位置,for 循环改变该排列位置上的元素。
-
递归参数和返回值:参数是传入的整数数组和本层递归的起始位置 stratIndex,无返回值。
-
递归终止条件:当排列的大小已经等于数组的大小时,将排列插入结果集,并返回。
-
递归顺序:在本层递归中固定好当前元素后,继续递归进行全排列,在下一层递归中将数组中所有其余的元素遍历一遍。因此我们需要用数组 isUsed 记录哪些元素已经被使用过。
class Solution {
public:
bool isUsed[10]; // 该数组记录元素是否已经被使用过
vector<int> path;
vector<vector<int>> result;
void findPath(vector<int> &nums,int startIndex){
if (path.size() == nums.size()){
result.push_back(path);
return;
}
// 每层都要从 0 开始搜索,因为排列是有序的,[1,2]和[2,1]属于两种不同的排列
for (int i = 0; i < nums.size(); ++i) {
if (isUsed[i]){ // 该元素已经在排列中被用过,跳过
continue;
}
path.push_back(nums[i]);
isUsed[i] = true; // 修改当前元素的使用状态
findPath(nums,i+1);
path.pop_back();
isUsed[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
findPath(nums,0);
return result;
}
};
全排列Ⅱ
题干
题目:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
思路和代码
本题就是在上一题的思路上进行去重。去重的思路之前说过很多,也就是在当前 for 循环中如果有重复的元素,则跳过。
方法一:用集合 set 去重
class Solution {
public:
bool isUsed[10];
vector<int> path;
vector<vector<int>> result;
void backTrack(vector<int> &nums){
if (path.size() == nums.size()){
result.push_back(path);
return;
}
unordered_set<int> uSet; // 记录当前 for 循环遍历过的元素!!!
for (int i = 0; i < nums.size(); ++i) {
if (isUsed[i]) continue;
if (uSet.find(nums[i]) != uSet.end()) continue; // 去重!!!
path.push_back(nums[i]);
isUsed[i] = true;
uSet.insert(nums[i]);
backTrack(nums);
path.pop_back();
isUsed[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
backTrack(nums);
return result;
}
};
方法二:先排序,再用数组去重
class Solution {
public:
bool isUsed[10];
vector<int> path;
vector<vector<int>> result;
void backTrack(vector<int> &nums){
if (path.size() == nums.size()){
result.push_back(path);
return;
}
for (int i = 0; i < nums.size(); ++i) {
if (isUsed[i]) continue;
if (i > 0 && nums[i] == nums[i-1] && !isUsed[i-1]){ // 对树层去重
continue; // 去重!!
}
path.push_back(nums[i]);
isUsed[i] = true;
backTrack(nums);
path.pop_back();
isUsed[i] = false;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
backTrack(nums);
return result;
}
};
标签:24,递归,nums,DAY25,isUsed,随想录,back,vector,数组
From: https://blog.csdn.net/chan_lay/article/details/141528919