代码随想录算法训练营day 29|第七章 回溯算法part05

news/2024/2/28 11:16:59

491.递增子序列 

本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。 

代码随想录

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

这道题本身没那么难想到,但是有很多要注意点:

  1. 一旦path的size大于1,就要收集.
  2. 使用容器要记住当次for循环已经遍历过的值,这样来去重.可以使用unordered_set(集合),也可以使用数组(提前声明容量为201,然后以每次的数值为下标来验证本次for循环是否已经使用过相等的值),注意如果用数组的话,会更快更方便查找每次是否遍历过,以空间换时间,但是要提前初始化.
  3. 每次for循环要判断path内是否有数了,如果有数了那就要判断当前的数值是否不小于最后一个数(也就是最大的那个).
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums,int begin){        if(path.size()>1){res.push_back(path);}int used[201]={0};for(int i=begin;i<nums.size();i++){if(path.size()){if(nums[i]<path.back()) continue;                }if(used[nums[i]+100]) continue;path.push_back(nums[i]);backtracking(nums,i+1);path.pop_back();used[nums[i]+100]=1;}}vector<vector<int>> findSubsequences(vector<int>& nums) {res.clear();path.clear();backtracking(nums,0);return res;}
};

46.全排列 

本题重点感受一下,排列问题 与 组合问题,组合总和,子集问题的区别。 为什么排列问题不用 startIndex 

代码随想录

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

这道题总体来讲也比较简单,主要注意这几个点:

  1. path的收集在它的size恰好等于nums的大小的时候进行,并且需要在这时候直接返回,因为是最终时刻收集结果而不是像上一道题一样边递归边收集.
  2. 这时候就需要每次for循环都从0开始,全排列不是顺序收集数字的而是可能跳着收集数字,所以没有递归遍历的规律,但需要每次知道上层递归都已经使用过哪些数,所以要传入used数组来记录已经排列进去的数字.
  3. used数组可以直接设置成nums数组大小,因为已经知道nums数组不重复,所以直接可以用该数字的下标来表示它在used数组中的位置,而且for循环内设置先显示用过该数字,递归结束之后再显示没有用过该数字,因为同层递归表示不同的排列顺序,而更深层的递归用来一点一点得到这个顺序的全排列.
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]) 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;}
};

47.全排列 II 

本题 就是我们讲过的 40.组合总和II 去重逻辑 和 46.全排列 的结合,可以先自己做一下,然后重点看一下 文章中 我讲的拓展内容。 used[i - 1] == true 也行,used[i - 1] == false 也行 

代码随想录

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

去重是这道题的重点,也是区别于上一题的关键,注意:

  1. 去重采取的是先将nums数组排列然后再凭借相等的两个数必然相邻的方法,重点要理解去重是要避免两个相同的数字在同一个for循环中(表示某次排序的同一个位置)反复选用.
  2. 然后还要避免已经参与了本次排序的元素反复参与排序,具体要使用used数组来避免,和上一题一样.
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;}
};

这里还有一点值得注意,就是将下面的代码(去重的关键)变成下下面的代码也是行得通的.

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;
}

改为:

if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {continue;
}

这是因为:
例: 1 1 1 2
used[i-1]==false 这句话表达的其实是上个数并没有在本次排序中,没有在本次序列中,就意味着它一定在之前的排列序列中在相同位置出现了,如果这个数和当前的数相等的话,就意味着同样的位置选了两次相同的数字.
而下一句代码意味着和这个数相等的数(上个数)如果已经出现在了本次序列中,就不能在当前位置选择这个数,这句话就导致在第一次遇到这个数值的数的时候是永远没办法得到完整序列的,因为一旦使用了第一个数,后面和他相等的数就不能在这次排序中出现了,这样之后会导致在排序的这个位置只能使用最后一个同样数值的数才能保证得到整个序列(保证与之等值的used[i-1]永远为false),这样就相当于暗中规定了相等数字的相对排序,只能倒着选取(和sort之后nums序列的这一区段的顺序相反),这样也能保证同一位置一定不会使用相等的值,但这样无疑会导致进行更多次数的递归(尽管之前的数字必然得不到完整的序列,但还是会进行到底才能返回),所以虽然可以AC,但最好用上面的代码.(这也是文章里面提到的树枝去重法,显然数层比树枝去重效率高)

总结

去重的方法有两个:

  1. 如果必须保证nums序列的各个元素的相对顺序的话,没法自行让相等的值挨着,就要使用辅助数组法,也就是使用每个元素的值作为下标,来迅速查询这个值是否在当前for循环中被重复使用了.
  2. 如果不必保证nums原本的顺序,那就直接sort排序nums,这样就能让相等的值必然相邻,保证当前遍历到的值不和上一个值相等即可,这样去重效率超高.

http://www.ppmy.cn/news/1350384.html

相关文章

unity2017 遇到visual studio 2017(社区版) 30日试用期到了

安装unity2017 遇到visual studio 2017 30日试用期到了&#xff0c;网上百度搜了好多方法都没有成功。 最后用了这个方法&#xff1a; 1)启动vs2017&#xff0c;在弹出要登录的窗口之前&#xff0c;迅速的点击工具-》选项-》账户&#xff0c;勾选在添加账户或对账户重新进行身…

〔025〕Stable Diffusion 之 接口开发 篇

✨ 目录 ▷ 启动接口▷ 接口文档▷ 接口开发▷ 代码解释 ▷ 启动接口 想要在各种其他服务中对接 Stable Diffusion 的绘画功能&#xff0c;需要开启 Stable Diffusion 的 api 功能开发接口需要有一定的技术功底才可以&#xff0c;非技术人员其实不用学习直接在 webui-user.bat…

【Java程序设计】【C00264】基于Springboot的原创歌曲分享平台(有论文)

基于Springboot的原创歌曲分享平台&#xff08;有论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 项目简介 这是一个基于Springboot的原创歌曲分享平台 本系统分为平台功能模块、管理员功能模块以及用户功能模块。 平台功能模块&#xff1a;在平台首页可以查看首…

分布式系统架构介绍

1、为什么需要分布式架构&#xff1f; 增大系统容量&#xff1a;单台系统的性能瓶颈&#xff0c;多台机器才能应对大规模的应用场景&#xff0c;所以就需要我们的应用支撑平台具备分布式架构。 加强系统的可用&#xff1a;为了满足业务的SLA要求&#xff0c;需要通过分布式架构…

【LeetCode】37. 解数独(困难)——代码随想录算法训练营Day30

题目链接&#xff1a;37. 解数独 题目描述 编写一个程序&#xff0c;通过填充空格来解决数独问题。 数独的解法需 遵循如下规则&#xff1a; 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&…

C++泛型编程:模板偏特化

模板偏特化为模板提供特殊的实现&#xff0c;针对特定的模板参数或参数组合。 在模板全特化&#xff0c;所有的模板参数都被指定了具体的类型。 我们可以在泛化设计中提供一个特化版本&#xff0c;针对其中某个或者数个模板参数进行特化&#xff0c;我们可以指定一部分模板参…

STM32自学☞定时器定时中断案例

timer_interrupt.c文件 /* 初始化函数编写步骤&#xff1a; 1.打开时钟 2.选择时基单元的时钟源&#xff08;内部时钟源&#xff09; 3.配置时基单元 4.NVIC配置 5.启动定时器 */ #include "stm32f10x.h" #include "stm32f10x_tim.h" #include …

​​​​​​C#系列-C#EF框架实现分库分表(21)

在C#中使用Entity Framework (EF)框架实现分库分表&#xff08;也称为数据库分片或水平切分&#xff09;是一个相对复杂的过程&#xff0c;因为EF本身并不直接支持分库分表。分库分表通常是为了解决单一数据库的性能瓶颈、数据量过大、高并发等问题而采取的一种策略。 实现分库…

速盾:cdn集群防御空间dns服务器

在当今数字化时代&#xff0c;网络安全和性能成为了企业关注的焦点。速盾的CDN集群防御空间DNS服务器技术为网站提供了更高水平的安全性和性能优化。本文将深入探讨这一技术的关键特点和优势。 1. 集群防御&#xff1a; 速盾的CDN集群防御通过分布在全球的节点集群&#xff0c;…

【Python】单元测试unittest框架

note 使用unittest框架进行单元测试是Python标准库的一部分&#xff0c;提供了编写测试用例、测试套件以及运行测试的能力。测试用例是继承自unittest.TestCase的类。在这个类中&#xff0c;你可以定义一系列的方法来测试不同的行为。每个测试方法都应该以test开头。 文章目录…

华为配置车地通信快速切换实验

配置车地通信快速切换示例 组网图形 图1 配置车地通信快速切换业务示意图 组网需求配置思路配置注意事项操作步骤配置文件 组网需求 某轨交企业为了降低网络部署成本&#xff0c;提升服务质量&#xff0c;希望通过WLAN技术实现车地通信&#xff0c;使部署在地面网络的组播服务器…

已解决org.springframework.web.HttpMediaTypeNotAcceptableException异常的正确解决方法,亲测有效!!!

已解决org.springframework.web.HttpMediaTypeNotAcceptableException异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 文章目录 问题分析 报错原因 解决思路 解决方法 总结 问题分析 在Spring MVC应用中处理HTTP请求时&#xff0c;我们有…

JavaI/O流 File类(文件)

目录 File类实例 File类 Java的File类是java.io.File的一个类&#xff0c;它表示文件或目录的路径名。这个类在处理文件和目录时非常有用&#xff0c;它提供了很多静态方法来操作文件和目录。 以下是一些File类的常见方法&#xff1a; 构造方法&#xff1a;创建表示文件或目…

洛谷: P1308 [NOIP2011 普及组] 统计单词数

前言: 这道题没理解清题目表达意思&#xff0c;我开始想的是用map来记录个数&#xff0c;然后一个变量记录一开始出现的单词位置&#xff0c;不挺简单的吗&#xff0c;然后....就AC了2个..从错误提示能看到个数没啥问题&#xff0c;但是第一个单词位置不对&#xff0c;看了新样…

【原创 附源码】Flutter安卓及iOS海外登录--Google登录最详细流程

最近接触了几个海外登录的平台&#xff0c;踩了很多坑&#xff0c;也总结了很多东西&#xff0c;决定记录下来给路过的兄弟坐个参考&#xff0c;也留着以后留着回顾。更新时间为2024年2月8日&#xff0c;后续集成方式可能会有变动&#xff0c;所以目前的集成流程仅供参考&#…

三、案例 - MySQL数据迁移至ClickHouse

MySQL数据迁移至ClickHouse 一、生成测试数据表和数据1.在MySQL创建数据表和数据2.在ClickHouse创建数据表 二、生成模板文件1.模板文件内容2.模板文件参数详解2.1 全局设置2.2 数据读取&#xff08;Reader&#xff09;2.3 数据写入&#xff08;Writer&#xff09;2.4 性能设置…

15 ABC基于状态机的按键消抖原理与状态转移图

1. 基于状态机的按键消抖 1.1 什么是按键&#xff1f; 从按键结构图10-1可知&#xff0c;按键按下时&#xff0c;接点&#xff08;端子&#xff09;与导线接通&#xff0c;松开时&#xff0c;由于弹簧的反作用力&#xff0c;接点&#xff08;端子&#xff09;与导线断开。 从…

Linux操作系统基础(三):虚拟机与Linux系统安装

文章目录 虚拟机与Linux系统安装 一、系统的安装方式 二、虚拟机概念 三、虚拟机的安装 四、Linux系统安装 1、解压人工智能虚拟机 2、找到解压目录中的node1.vmx 3、启动操作系统 虚拟机与Linux系统安装 一、系统的安装方式 Linux操作系统也有两种安装方式&#xf…

STM32控制JQ8400语音播报模块

时间记录&#xff1a;2024/2/7 一、JQ8400引脚介绍 标示说明ONE LINE一线操作引脚BUSY忙信号引脚&#xff0c;正在播放语音时输出高电平RX串口两线操作接收引脚TX串口两线操作发送引脚GND电源地引脚DC-5V电源引脚&#xff0c;3.3-5VDAC-RDAC输出右声道引脚DAC-LDAC输出左声道…

安装node-sass时遇到了编译错误如何解决

问题描述 npm ERR! code 1 npm ERR! path D:\ALearnBlog\shiyi-blog\blog-web\node_modules\node-sass npm ERR! command failed npm ERR! command C:\Windows\system32\cmd.exe /d /s /c node scripts/build.js npm ERR! Building: E:\Program_Files\nodejs\node.exe D:\ALea…
最新文章