【算法day20】回溯:子集与全排列问题

server/2024/12/25 1:12:36/

题目引用


  1. 非递减子序列
  2. 全排列
  3. 全排列II

1. 非递减子序列


给你一个整数数组 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]]

首先我们拿到题目的时候就看到了不同的子序列,说明我们需要对其中的结果进行去重。有同学就会说了,去重我知道呀,就是用used数组去标记他就好啦,不不不,这道题目不一样。当我们使用used数组时,我们需要对原数组进行排序,可是那样就会破坏原有数组的稳定性,所以我们不能使用used数组来进行去重。那么我们应该使用什么方法呢?
大家在做哈希时一直使用的东西,unordered_set。每当我们进入下一层时就创建一个set,这样我们就能知道在这一树层时其他的元素有没有被使用。那么具体怎么做呢?
来看代码:

class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums,int startIndex){if(path.size()>1){res.push_back(path);}unordered_set<int> uset;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();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums,0);return res;}
};

当我们的数组元素不大于当前路径的最后一个元素时或者我们在set中能够找到这个元素时,我们进行剪枝,进行下一个循环。

2. 全排列


给定一个不含重复数字的数组 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]]

既然是不含重复数字,那么我们就只需要创建一个used数组来标记同一层里有没有重复的元素,并进行去重,保证当前路径没有重复元素即可。同时因为是全排列,我们就不要对数组进行排序和使用startIndex来标记下一个元素的起始位置了,而是从0开始,这也是全排列问题与其他问题不同的地方。
那么我们来看代码:

class Solution {
public: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(used[i]==true) continue;used[i]=true;path.push_back(nums[i]);backtracking(nums,used);path.pop_back();used[i]=false;}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(),false);backtracking(nums,used);return res;}
};

3. 全排列II


给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。

示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]

都做了这么多题目啦,看到包含重复数字时,我们的条件反射就是:第一、对数组进行排序。第二在遍历数组时加上筛选条件,当前项nums[i]==nums[i-1]&&used[i-1]=false时,说明我们在同一树层中有了重复项,进行剪枝操作。那么来看代码 :

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking (vector<int>& nums, vector<bool>& 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:vector<vector<int>> permuteUnique(vector<int>& nums) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

总结


今天是回溯的最后一天,大家觉得回溯难不难呀


http://www.ppmy.cn/server/152917.html

相关文章

阿里云cdn稳定吗?

阿里云CDN&#xff08;内容分发网络&#xff09;是阿里云提供的一项全球加速服务&#xff0c;它的稳定性通常被认为是非常高的&#xff0c;尤其在国内市场。九河云给大家总结了阿里云CDN的稳定性情况&#xff1a; 1. 全球节点覆盖广泛 阿里云CDN在全球范围内拥有数百个加速节…

MongoDB常见面试题总结(上)

MongoDB 基础 MongoDB 是什么? MongoDB 是一个基于 分布式文件存储 的开源 NoSQL 数据库系统,由 C++ 编写的。MongoDB 提供了 面向文档 的存储方式,操作起来比较简单和容易,支持“无模式”的数据建模,可以存储比较复杂的数据类型,是一款非常流行的 文档类型数据库 。 …

RHCE-第七章:SELinux

一、selinux的说明 SELinux是Security-Enhanced Linux的缩写&#xff0c;意思是安全强化的linux。SELinux 主要由美国国家安全局&#xff08;NSA&#xff09;开发&#xff0c;当初开发的目的是为了避免资源的误用。系统资源都是通过程序进行访问的&#xff0c;如果将 /var/www…

【C/C++】推荐一个性能优良的错误码打印机制,已实测!

基于上1篇 switch与for的性能比较文章&#xff0c;若我们在开发一个较大型的系统架构&#xff0c;则错误码机制是必不可少的。 但是&#xff0c;基于灵活可扩展思想&#xff0c;我们的错误码是与日俱增的&#xff0c;所以&#xff0c;如何能不写很多switch-case语句&#xff0c…

【题解】—— LeetCode一周小结50

&#x1f31f;欢迎来到 我的博客 —— 探索技术的无限可能&#xff01; &#x1f31f;博客的简介&#xff08;文章目录&#xff09; 【题解】—— 每日一道题目栏 上接&#xff1a;【题解】—— LeetCode一周小结49 9.判断国际象棋棋盘中一个格子的颜色 题目链接&#xff1a;…

PostgreSQL 的历史

title: PostgreSQL 的历史 date: 2024/12/23 updated: 2024/12/23 author: cmdragon excerpt: PostgreSQL 是一款功能强大且广泛使用的开源关系型数据库管理系统。其历史可以追溯到1986年,当时由加州大学伯克利分校的一个研究团队开发。文章将深入探讨 PostgreSQL 的起源、…

内容与资讯API优质清单

作为开发者&#xff0c;拥有一套API合集是必不可少的。这个开发者必备的API合集汇集了各种实用的API资源&#xff0c;为你的开发工作提供了强大的支持&#xff01;无论你是在构建网站、开发应用还是进行数据分析&#xff0c;这个合集都能满足你的需求。你可以通过这些免费API获…

探索大语言模型的世界:入门指南

随着人工智能技术的飞速发展&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为诸多行业关注的焦点。从自然语言处理到生成式人工智能&#xff0c;LLMs 正在改变我们与技术互动的方式。如果你刚刚接触大语言模型&#xff0c;不知道从何下手&…