网页设计注册页面代码,seo关键词优化排名软件,全国城市感染率排名,企业简介的网站怎么做491 递增子序列
题目描述
给你一个整数数组 nums #xff0c;找出并返回所有该数组中不同的递增子序列#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素#xff0c;如出现两个整数相等#xff0c;也可以视作递增序列的一…491 递增子序列
题目描述
给你一个整数数组 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]]提示
1 nums.length 15-100 nums[i] 100
题目分析
而本题求自增子序列是不能对原数组进行排序的排完序的数组都是自增子序列了。
所以不能使用之前的去重逻辑同一父节点下的同层上使用过的元素就不能再使用了 对于已经习惯写回溯的同学看到递归函数上面的uset.insert(nums[i]);下面却没有对应的pop之类的操作应该很不习惯吧
这也是需要注意的点unordered_setint uset; 是记录本层元素是否重复使用新的一层uset都会重新定义清空所以要知道uset只负责本层
acm模式代码
#include iostream
#include vector
#include unordered_setclass Solution {
private:std::vectorstd::vectorint result; // 用于存储所有递增子序列的结果集std::vectorint path; // 用于在递归中构建当前递增子序列的路径// 回溯法主体函数void backtracking(std::vectorint nums, int startIndex) {// 如果路径长度大于1将其加入结果集if (path.size() 1) {result.push_back(path);// 注意这里不要加return因为要取树上的所有节点}std::unordered_setint uset; // 使用set对本层元素进行去重for (int i startIndex; i nums.size(); i) {// 如果当前元素小于路径中最后一个元素或者本层已经使用过该元素则跳过if ((!path.empty() nums[i] path.back()) || uset.find(nums[i]) ! uset.end()) {continue;}uset.insert(nums[i]); // 记录这个元素在本层用过了本层后面不能再用path.push_back(nums[i]);backtracking(nums, i 1); // 递归调用尝试下一个元素path.pop_back(); // 回溯撤销上一步操作}}public:// 公有函数调用此函数开始寻找所有递增子序列std::vectorstd::vectorint findSubsequences(std::vectorint nums) {result.clear(); // 清空上一次的结果path.clear(); // 清空路径backtracking(nums, 0); // 从第一个元素开始递归return result; // 返回结果集}
};int main() {Solution solution;std::vectorint nums {4, 6, 7, 7}; // 示例数组auto subsequences solution.findSubsequences(nums);std::cout Found subsequences.size() increasing subsequences: std::endl;for (const auto seq : subsequences) {for (int num : seq) {std::cout num ;}std::cout std::endl;}return 0;
}46 全排列
题目描述
给定一个不含重复数字的数组 nums 返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2
输入nums [0,1]
输出[[0,1],[1,0]]示例 3
输入nums [1]
输出[[1]]提示
1 nums.length 6-10 nums[i] 10nums 中的所有整数 互不相同
题目分析
首先排列是有序的也就是说 [1,2] 和 [2,1] 是两个集合这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了但是在[2,1]中还要在使用一次1所以处理排列问题就不用使用startIndex了。
acm模式代码
#include iostream
#include vectorclass Solution {
private:std::vectorstd::vectorint result; // 用于存储所有可能的排列结果std::vectorint path; // 临时存储一个排列结果// 回溯法函数void backtracking(std::vectorint nums, std::vectorbool used) {// 如果当前排列长度等于原数组长度说明找到了一个完整的排列if (path.size() nums.size()) {result.push_back(path); // 将当前排列加入结果集return;}for (int i 0; i nums.size(); i) {// 如果数字已被使用则跳过if (used[i] true) {continue;}used[i] true; // 标记数字为已使用path.push_back(nums[i]); // 将数字添加到当前排列路径中backtracking(nums, used); // 继续递归填充下一个数字path.pop_back(); // 回溯从当前排列中移除最后一个数字used[i] false; // 重置当前数字的使用状态}return;}
public:// 主函数返回给定数组的所有排列组合std::vectorstd::vectorint permute(std::vectorint nums) {std::vectorbool used(nums.size(), false); // 初始化所有数字未被使用result.clear(); // 清空结果集path.clear(); // 清空当前路径backtracking(nums, used); // 开始回溯搜索return result; // 返回所有排列组合的结果集}
};int main() {Solution sol;std::vectorint nums {1, 2, 3}; // 示例数组std::vectorstd::vectorint result sol.permute(nums); // 获取所有排列// 打印所有排列for (const auto path : result) {for (const int num : path) {std::cout num ;}std::cout std::endl;}return 0;
}输出
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
47全排列Ⅱ
题目描述
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。 示例 1
输入nums [1,1,2]
输出
[[1,1,2],[1,2,1],[2,1,1]]示例 2
输入nums [1,2,3]
输出[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]提示
1 nums.length 8-10 nums[i] 10
题目分析
去重最为关键的代码为
if (i 0 nums[i] nums[i - 1] used[i - 1] false) {continue;
}
对于排列问题树层上去重和树枝上去重都是可以的但是树层上去重效率更高
acm模式代码
#include iostream
#include vector
#include algorithm // 引入算法头文件用于排序class Solution {
private:std::vectorstd::vectorint result; // 存储最终的排列结果std::vectorint path; // 临时存储当前排列的路径// 回溯法函数用于递归生成排列void backtracking(std::vectorint nums, std::vectorbool used) {// 如果当前路径长度等于原数组长度说明找到了一个完整排列if (path.size() nums.size()) {result.push_back(path); // 将当前路径添加到结果集中return; // 回溯}for (int i 0; i nums.size(); i) {// 跳过已使用的元素或同一层级中的重复元素if (used[i] || (i 0 nums[i] nums[i - 1] !used[i -1])) {continue;}used[i] true; // 标记当前元素为已使用path.push_back(nums[i]); // 将当前元素添加到路径中backtracking(nums, used); // 递归调用继续构建路径path.pop_back(); // 回溯移除路径中的最后一个元素used[i] false; // 重置当前元素为未使用}}
public:// 公共接口返回给定数组的所有独特排列std::vectorstd::vectorint permuteUnique(std::vectorint nums) {std::sort(nums.begin(), nums.end()); // 对数组进行排序以便有效地跳过重复元素std::vectorbool used(nums.size(), false); // 初始化使用标记数组result.clear(); // 清空结果集path.clear(); // 清空当前路径backtracking(nums, used); // 开始回溯搜索return result; // 返回结果集}
};int main() {Solution sol;std::vectorint nums {1, 1, 2, 3}; // 示例输入std::vectorstd::vectorint result sol.permuteUnique(nums); // 获取所有独特的排列// 打印所有排列for (const auto path : result) {for (const int num : path) {std::cout num ;}std::cout std::endl;}return 0;
}输出
1 1 2 3 1 1 3 2 1 2 1 3 1 2 3 1 1 3 1 2 1 3 2 1 2 1 1 3 2 1 3 1 2 3 1 1 3 1 1 2 3 1 2 1 3 2 1 1
