代码随想录第29天|491.递增子序列 46.全排列 47.全排列 II

目录:

491.递增子序列

46.全排列

47.全排列 II 

491.递增子序列

491. 非递减子序列 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

回溯算法精讲,树层去重与树枝去重 | LeetCode:491.递增子序列_哔哩哔哩_bilibili

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

第一反应是把所有的子序列列出来,然后再判断是不是递增子序列。

 回溯三部曲:
1、确定参数:除了path、result和startIndex之外,还需要一个集合来存放一层的值,避免在同一层中出现重复的值从而出现重复的子序列:

// 声明一个结果集合,用于存储所有满足条件的子序列List<List<Integer>> result = new ArrayList<>();// 声明一个路径集合,用于存储当前正在构建的子序列List<Integer> path = new ArrayList<>();HashSet<Integer> hs = new HashSet<>();
private void backTracking(int[] nums, int startIndex) {
}

 2、确定终止条件:当path的大小大于1,且path里面的值符合曾序序列的要求时,把path加到result数组里,然后返回:

if (path.size() >= 2)result.add(new ArrayList<>(path));

3、确定单层搜索的逻辑:
同一父节点下同层元素中,如果一个数字在同层已经出现过的话,就不能再使用了,因为再次使用的话会出现重复子序列:

 for (int i = startIndex; i < nums.length; i++) {// 如果当前路径不为空,并且路径中的最后一个数字大于当前数字,或者当前数字已经在路径中出现过,则跳过当前数字if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i]))continue;// 将当前数字加入到路径中hs.add(nums[i]);path.add(nums[i]);// 递归调用,继续寻找以当前数字结尾的子序列backTracking(nums, i + 1);// 回溯,将当前数字从路径中移除,准备尝试其他可能的数字path.remove(path.size() - 1);}

综合代码:

// 定义一个名为 Solution 的类
class Solution {// 声明一个结果集合,用于存储所有满足条件的子序列List<List<Integer>> result = new ArrayList<>();// 声明一个路径集合,用于存储当前正在构建的子序列List<Integer> path = new ArrayList<>();// 主方法,入口点public List<List<Integer>> findSubsequences(int[] nums) {// 调用回溯函数,开始查找所有满足条件的子序列backTracking(nums, 0);// 返回结果集合return result;}// 回溯函数,用于查找所有满足条件的子序列private void backTracking(int[] nums, int startIndex) {// 如果当前路径的长度大于等于2,则将其加入到结果集合中if (path.size() >= 2)result.add(new ArrayList<>(path));            // 创建一个哈希集合,用于记录当前路径中已经出现过的数字HashSet<Integer> hs = new HashSet<>();// 遍历数组,从startIndex位置开始for (int i = startIndex; i < nums.length; i++) {// 如果当前路径不为空,并且路径中的最后一个数字大于当前数字,或者当前数字已经在路径中出现过,则跳过当前数字if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i]))continue;// 将当前数字加入到路径中hs.add(nums[i]);path.add(nums[i]);// 递归调用,继续寻找以当前数字结尾的子序列backTracking(nums, i + 1);// 回溯,将当前数字从路径中移除,准备尝试其他可能的数字path.remove(path.size() - 1);}}
}

这里仍然有一个小疑惑:为什么hs里面的数不需要弹出呢?

46.全排列 

. - 力扣(LeetCode)

代码随想录 (programmercarl.com)

组合与排列的区别,回溯算法求解的时候,有何不同?| LeetCode:46.全排列_哔哩哔哩_bilibili

给定一个不含重复数字的数组 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] <= 10
  • nums 中的所有整数 互不相同

这道题我第一次看到的时候觉得就是每个位置上每个数字都可以放,但是不知道怎么代码实现。看了卡哥视频:
回溯三部曲:
1、确定参数:排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方

可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组,标记已经选择的元素。

List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used; // 用于标记数字是否被使用过

2、确定终止条件:叶子节点终止,即path长度和nums数组的大小一样时终止:

 if (path.size() == nums.length){// 将当前路径加入到结果集合中result.add(new ArrayList<>(path));return;}

3、确定单层搜索的逻辑:

// 遍历数组中的每个元素for (int i = 0; i < nums.length; i++){// 如果该元素已经被使用过,则跳过if (used[i]){continue;}// 标记该元素为已使用used[i] = true;// 将该元素加入到当前路径中path.add(nums[i]);// 递归调用,继续生成全排列结果permuteHelper(nums);// 回溯,将当前加入的元素移除path.removeLast();// 标记该元素为未使用used[i] = false;}

综合代码:

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果boolean[] used; // 用于标记数字是否被使用过// 主函数,输入数组 nums,返回其全排列结果public List<List<Integer>> permute(int[] nums) {// 如果数组为空,则直接返回结果集合if (nums.length == 0){return result;}// 初始化 used 数组为与 nums 相同长度的布尔数组used = new boolean[nums.length];// 调用递归函数进行全排列permuteHelper(nums);// 返回全排列结果return result;}// 辅助递归函数,用于生成全排列结果private void permuteHelper(int[] nums){// 如果当前路径长度等于数组长度,表示已经得到一个全排列结果if (path.size() == nums.length){// 将当前路径加入到结果集合中result.add(new ArrayList<>(path));return;}// 遍历数组中的每个元素for (int i = 0; i < nums.length; i++){// 如果该元素已经被使用过,则跳过if (used[i]){continue;}// 标记该元素为已使用used[i] = true;// 将该元素加入到当前路径中path.add(nums[i]);// 递归调用,继续生成全排列结果permuteHelper(nums);// 回溯,将当前加入的元素移除path.removeLast();// 标记该元素为未使用used[i] = false;}}
}

47.全排列 II 

47. 全排列 II - 力扣(LeetCode)

代码随想录 (programmercarl.com)

回溯算法求解全排列,如何去重?| LeetCode:47.全排列 II_哔哩哔哩_bilibili

给定一个可包含重复数字的序列 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

如图,还是要考虑一个去重的逻辑。

1、确定参数:

 // 存放结果List<List<Integer>> result = new ArrayList<>();// 暂存结果List<Integer> path = new ArrayList<>();
  // 标记每个数字是否被使用过boolean[] used = new boolean[nums.length];

2、确定终止条件:

// 如果当前路径长度等于数组长度,说明已经找到一个排列if (path.size() == nums.length) {result.add(new ArrayList<>(path)); // 将当前路径加入结果集return; // 结束当前递归}

3、确定单层搜索逻辑:used[i-1]为false的时候,才保证了是树层上的数值不能相同,而不是树枝上。

// 遍历所有数字for (int i = 0; i < nums.length; i++) {// 如果当前数字已经被使用过,直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}// 如果当前数字未被使用过,开始处理if (used[i] == false) {used[i] = true; // 标记当前数字被使用过path.add(nums[i]); // 将当前数字加入路径backTrack(nums, used); // 递归处理下一层path.remove(path.size() - 1); // 回溯,移除当前数字used[i] = false; // 恢复当前数字的未使用状态}}

综合代码:

class Solution {// 存放结果List<List<Integer>> result = new ArrayList<>();// 暂存结果List<Integer> path = new ArrayList<>();// 主函数,入口public List<List<Integer>> permuteUnique(int[] nums) {// 标记每个数字是否被使用过boolean[] used = new boolean[nums.length];Arrays.fill(used, false); // 初始化为未使用状态Arrays.sort(nums); // 对输入数组排序,确保相同数字相邻backTrack(nums, used); // 调用回溯函数return result; // 返回最终结果}// 回溯函数,用于搜索所有排列组合private void backTrack(int[] nums, boolean[] used) {// 如果当前路径长度等于数组长度,说明已经找到一个排列if (path.size() == nums.length) {result.add(new ArrayList<>(path)); // 将当前路径加入结果集return; // 结束当前递归}// 遍历所有数字for (int i = 0; i < nums.length; i++) {// 如果当前数字已经被使用过,直接跳过if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}// 如果当前数字未被使用过,开始处理if (used[i] == false) {used[i] = true; // 标记当前数字被使用过path.add(nums[i]); // 将当前数字加入路径backTrack(nums, used); // 递归处理下一层path.remove(path.size() - 1); // 回溯,移除当前数字used[i] = false; // 恢复当前数字的未使用状态}}}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1323546.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

2023最新汽车网络安全报告汇总

2023最新汽车网络安全报告、安全参考架构及指南汇总&#xff0c;供大家学习参考。https://t.zsxq.com/18RkG260k 汽车信息安全法律法规及标准全景图V3.2.pdf 车载智能计算基础平台参考架构2.0.pdf 车载智能计算芯片白皮书(2023版).pdf 智能驾驶行为安全评价方法发布版.pdf 智能…

超细节小白教学Windows10系统 数据库MYSQL服务安装及验证

超细节小白教学Windows10系统 数据库MYSQL服务安装 一、MySQL下载及安装 官网下载地址&#xff1a;https://dev.mysql.com/downloads/mysql/ 进入官网页面如下图所示&#xff1a; 一般64-bit代表64位系统&#xff0c;如果需要32位系统可以在历史版本中寻找。 等待下载完成&a…

【协议篇:Http与Https】

1. Http 1.1 Http的定义 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;是用于分布式、协作式和超媒体信息系统的应用层协议。它是互联网上最广泛应用的数据通信协议之一&#xff0c;尤其对于万维网&#xff08;WWW&#xff09;服务而言…

5.动态规划

1.背包问题 (1)0/1背包问题 01背包问题即每个物品只能选1个 考虑第i件物品&#xff0c;当j<w[i]时&#xff0c;f[i][j]f[i-1][j]&#xff0c;当j>w[i]时&#xff0c;此时有两种选择&#xff0c;选择第i件物品和不选第i件物品。此时f[i][j]max(f[i-1][j],f[i-1][j-w[i]]v…

【QingHub】QingHub Studio企业级应用作业编排

简介 QingHub作业编排中心是一个通过插件化方式&#xff0c;提供数据从采集&#xff0c;转化&#xff0c;计算&#xff0c;存储为一体的全流程数据处理方案&#xff0c;他一方面为前端应用提供数据源&#xff0c;同时也为前端应用与数据源头的通信搭建起桥梁&#xff0c;实现数…

【WebKit架构讲解】

&#x1f308;个人主页:程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…

C++:函数重载,引用

文章目录 1. 函数重载1.1 函数重载概念1.2 C支持函数重载的原理--名字修饰1.3 缺省参数与重载 2. 引用2.1引用概念2.2 引用特性2.3 常引用2.4 使用场景2.5 引用和指针的区别 1. 函数重载 1.1 函数重载概念 C允许在同一作用域中声明几个功能类似的同名函数&#xff0c;这些同名…

查看并设定【网络适配器】的优先级(跃点数)

目录 前言&#xff1a; 1.查看所有的适配器 2.修改优先级&#xff08;需要以管理员身份运行&#xff09; 跃点数&#xff08;InterfaceMetric &#xff09; DHCP 3.修改后的效果 pwoerShell 再次运行之前的程序 4.其他 参考 网络适配器1&#xff0c;8相关知识介绍1 …

回溯算法|47.全排列II

力扣题目链接 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);r…

【前端】CSS(引入方式+选择器+常用元素属性+盒模型)

文章目录 CSS一、什么是CSS二、语法规范三、引入方式1.内部样式表2.行内样式表3.外部样式 四、选择器1.选择器的种类1.基础选择器&#xff1a;单个选择器构成的1.标签选择器2.类选择器3.id 选择器4.通配符选择器 2.复合选择器1.后代选择器2.子选择器3.并集选择器4.伪类选择器 五…

python基于django协同算法的个性化音乐推荐系统的设计与实现

本个性化音乐推荐系统以Django作为框架&#xff0c;b/s模式以及MySql作为后台运行的数据库。本系统主要包括以下功能模块&#xff1a;首页&#xff0c;个人中心&#xff0c;用户管理&#xff0c;歌曲类型管理&#xff0c;明星歌手管理&#xff0c;歌曲音乐管理&#xff0c;歌曲…

Java基于微信小程序的电子竞技信息交流系统,附源码(V2.0)

博主介绍&#xff1a;✌IT徐师兄、7年大厂程序员经历。全网粉丝15W、csdn博客专家、掘金/华为云//InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;&#x1f3…

AI预测福彩3D第24弹【2024年4月2日预测--第6套算法开始计算第1次测试】

今天&#xff0c;咱们进行第6套算法测试&#xff0c;本套算法将结合012路直选共27种组合&#xff0c;同时考虑了对012路的和值进行统计分析。今天为第1次测试&#xff0c;好了&#xff0c;废话不多说了。直接上结果~ 仍旧是分为两个方案&#xff0c;1大1小。 经过人工神经网络计…

常用的限流方案思路和实现

限流方案 1、计数器&#xff08;固定窗口&#xff09; 1.1、简介 计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数&#xff0c;如果请求数超过了阈值&#xff0c;则舍弃该请求&#xff1b;如果没有达到设定的阈值&#xf…

【单点登录SSO,Auth2,jwt-过程分析】

目录 单点登录简介 SSO&CAS是什么 单点登录适合什么场景 单点登录的三种实现方式 CAS的几个重要知识点 CAS的实现过程 单点登录简介 单点登录(SingleSignOn&#xff0c;SSO)&#xff0c;就是通过用户的一次性鉴别登录。当用户在身份认证服务器上登录一次以后&#xff0c;即…

C++ //练习 11.12 编写程序,读入string和int的序列,将每个string和int存入一个pair中,pair保存在一个vector中。

C Primer&#xff08;第5版&#xff09; 练习 11.12 练习 11.12 编写程序&#xff0c;读入string和int的序列&#xff0c;将每个string和int存入一个pair中&#xff0c;pair保存在一个vector中。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#x…

【JavaWeb】Day32.MySQL概述

什么是数据库 数据库&#xff1a;英文为 DataBase&#xff0c;简称DB&#xff0c;它是存储和管理数据的仓库。 像我们日常访问的电商网站京东&#xff0c;企业内部的管理系统OA、ERP、CRM这类的系统&#xff0c;以及大家每天都会刷的头条、抖音类的app&#xff0c;那这些大家所…

苍穹外卖Day04套餐管理部分总结

写给像我一样完完全全的小白的。本人代码水平一塌糊涂&#xff0c;前几天就是机械地跟着视频敲代码。对于Day04的作业本来感觉代码抓瞎一点不会写&#xff0c;尽力去理解业务逻辑后发现好像也没那么难&#xff0c;整体代码可以仿照Day03新增菜品来进行实现&#xff01; 一、功…

面试复盘1 - 测试相关(实习)

写在前&#xff1a;hello&#xff0c;大家早中晚上好~这里是西西&#xff0c;最近有在准备测试相关的面试&#xff0c;特此开设了新的篇章&#xff0c;针对于面试中的问题来做一下复盘&#xff0c;会把我自己遇到的问题进行整理&#xff0c;除此之外还会进行对一些常见面试题的…

6.S081的Lab学习——Lab2: system calls

文章目录 前言一、System call tracing&#xff08;moderate&#xff09;解析&#xff1a; 二、Sysinfo&#xff08;moderate&#xff09;解析&#xff1a; 前言 一个本硕双非的小菜鸡&#xff0c;备战24年秋招。打算尝试6.S081&#xff0c;将它的Lab逐一实现&#xff0c;并记…