Follow Carl To Grow|【LeetCode】491.递增子序列,46.全排列,47.全排列 II
【LeetCode】491.递增子序列
题意:给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素,如出现两个整数相等,也可以视作递增序列的一种特殊情况。
思路:首先每层元素不能重复使用,所以回溯需要idx参数。其次选择树种对于同层不能重复选,但是又不能改变序列顺序,所以只在循环前用set记录本层元素是否重复使用即可。然后就是如果遍历值比末尾大,则跳过。最后递归出口长度要求至少为2,并且收集所有结点不return。
代码:
class Solution {
public:vector<int> m_path;vector<vector<int>> m_res;void backtracking(vector<int> &nums, int idx){if (1 < m_path.size()){m_res.push_back(m_path);}unordered_set<int> uset;for (int i = idx; i < nums.size(); ++i){if (uset.count(nums[i])){continue;}else if (!m_path.empty() && m_path.back() > nums[i]){continue;}m_path.push_back(nums[i]);uset.insert(nums[i]);backtracking(nums, i + 1);//不要还原usetm_path.pop_back();}}vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums, 0);return m_res;}
};
【LeetCode】46.全排列
题意:给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
思路:首先排列有顺序,也就是不需要idx来保证唯一。其次,可以使用used数组来标记当前层已经使用过的元素。
代码:
class Solution {
public:vector<int> m_path;vector<vector<int> >m_res;void backtracking(vector<int> &nums, vector<bool> &used){if (nums.size() == m_path.size()){m_res.push_back(m_path);return;}for (int i = 0; i < nums.size(); ++i){if (used[i]){continue;}m_path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;m_path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return m_res;}
};
【LeetCode】47.全排列 II
题意:给定一个可包含重复数字的序列 nums ,按任意顺序 返回所有不重复的全排列。
思路:首先包含重复数字时要求不重复的全排列,需要对原数组排序然后利用used数组去重。其次,求排列本身也要用到used数组。
代码:
class Solution {
public:vector<int> m_path;vector<vector<int>> m_res;void backtracking(vector<int> &nums, vector<bool> &used){if (m_path.size() == nums.size()){m_res.push_back(m_path);return;}for (int i = 0; i < nums.size(); ++i){if (0 < i && nums[i - 1] == nums[i] && !used[i - 1]){continue;}if (!used[i]){m_path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;m_path.pop_back();}}}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());vector<bool> used(nums.size(), false);backtracking(nums, used);return m_res;}
};
心态:“第七章 回溯算法part04” 拿下!
参考资料
相关文章:
Follow Carl To Grow|【LeetCode】491.递增子序列,46.全排列,47.全排列 II
【LeetCode】491.递增子序列 题意:给你一个整数数组 nums ,找出并返回所有该数组中不同的递增子序列,递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素,如出现两个整数相等,也可以…...
pytorch nn.Embedding 用法和原理
nn.Embedding 是 PyTorch 中的一个模块,用于将离散的输入(通常是词或子词的索引)映射到连续的向量空间。它在自然语言处理和其他需要处理离散输入的任务中非常常用。以下是 nn.Embedding 的用法和原理。 用法 初始化 nn.Embedding nn.Embed…...
Python中常用的有7种值(数据)的类型及type()语句的用法
目录 0.Python中常用的有7种值(数据)的类型Python中的数据类型主要有:Number(数字)、Boolean(布尔)、String(字符串)、List(列表)、Tuple…...
某配送平台未授权访问和弱口令(附赠nuclei默认密码验证脚本)
找到一个某src的子站,通过信息收集插件,发现ZABBIX-监控系统,可以日一下 使用谷歌搜索历史漏洞:zabbix漏洞 通过目录扫描扫描到后台,谷歌搜索一下有没有默认弱口令 成功进去了,挖洞就是这么简单 搜索文章还…...
01.总览
目录 简介Course 1: Natural Language Processing with Classification and Vector SpaceWeek 1: Sentiment Analysis with Logistic RegressionWeek 2: Sentiment Analysis with Nave BayesWeek 3: Vector Space ModelsWeek 4: Machine Translation and Document Search Cours…...
Linux换源
前言 安装完Linux系统,尽量更换源以提高安装软件的速度。 步骤 备份原始源列表sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak修改sources.list sudo vim /etc/apt/sources.list将内容替换成对应的源 **PS:清华源地址:https:…...
【高考志愿】 化学工程与技术
目录 一、专业概述 二、就业前景 三、就业方向 四、报考注意 五、专业发展与深造 六、化学工程与技术专业排名 七、总结 一、专业概述 化学工程与技术专业,这是一门深具挑战与机遇的综合性学科。它融合了工程技术的实用性和化学原理的严谨性,为毕…...
2024上半年网络与数据安全法规政策、国标、报告合集
事关大局,我国数据安全立法体系已基本形成并逐步细化。数据基础制度建设事关国家发展和安全大局,数据安全治理贯穿构建数据基础制度体系全过程。随着我国数字经济建设进程加快,数据安全立法实现由点到面、由面到体加速构建,目前已…...
基于SpringBoot扶农助农政策管理系统设计和实现(源码+LW+调试文档+讲解等)
💗博主介绍:✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者,博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌💗 🌟文末获取源码数据库🌟 感兴趣的可以先收藏起来,…...
淘宝商铺电话怎么获取?使用爬虫工具采集
访问淘宝商铺是一个合法的行为,你可以使用爬虫工具来提取淘宝商铺的信息。下面是一个基本的Python程序示例,用于使用爬虫工具访问淘宝商铺: import requestsdef get_store_info(store_id):url fhttps://shop{id}.taobao.comresponse reque…...
ModStart:开源免费的PHP企业网站开发建设管理系统
大家好!今天我要给大家介绍一款超级强大的开源工具——ModStart,它基于Laravel框架,是PHP企业网站开发建设的绝佳选择! 为什么选择ModStart? 模块化设计:ModStart采用模块化设计,内置了众多基…...
npm安装依赖报错——npm ERR gyp verb cli的解决方法
1. 问题描述 1.1 npm安装依赖报错——npm ERR! gyp verb cli npm MARN deprecated axiosQ0.18.1: critical security vuLnerability fixed in v0.21.1. For more information, npm WARN deprecated svg001.3.2: This SVGO version is no Longer supported. upgrade to v2.x.x …...
公网环境使用Potplayer远程访问家中群晖NAS搭建的WebDAV听歌看电影
文章目录 前言1 使用环境要求:2 配置webdav3 测试局域网使用potplayer访问webdav4 内网穿透,映射至公网5 使用固定地址在potplayer访问webdav 前言 本文主要介绍如何在Windows设备使用potplayer播放器远程访问本地局域网的群晖NAS中的影视资源ÿ…...
Forecasting from LiDAR via Future Object Detection
Forecasting from LiDAR via Future Object Detection 基础信息 论文:cvpr2022paper https://openaccess.thecvf.com/content/CVPR2022/papers/Peri_Forecasting_From_LiDAR_via_Future_Object_Detection_CVPR_2022_paper.pdfgithub:https://github.co…...
【unity笔记】五、UI面板TextMeshPro 添加中文字体
Unity 中 TextMeshPro不支持中文字体,下面为解决方法: 准备字体文件,从Windows系统文件的Fonts文件夹里拖一个.ttf文件(C盘 > Windows > Fonts ) 准备字库文件,新建一个文本文件,命名为“字库”&…...
如何在Windows 11上设置默认麦克风和相机?这里有详细步骤
如果你的Windows 11计算机上连接了多个麦克风或网络摄像头,并且希望自动使用特定设备,而不必每次都在设置中乱动,则必须将首选设备设置为默认设备。我们将向你展示如何做到这一点。 如何在Windows 11上更改默认麦克风 有两种方法可以将麦克…...
Flutter循序渐进==>数据结构(列表、映射和集合)和错误处理
导言 填鸭似的教育确实不行,我高中时学过集合,不知道有什么用,毫无兴趣,等到我学了一门编程语言后,才发现集合真的很有用;可以去重,可以看你有我没有的,可以看我有你没有的…...
泛微E9开发 限制明细表列的值重复
限制明细表列的值重复 1、需求说明2、实现方法3、扩展知识点3.1 修改单个字段值(不支持附件类型)3.1.1 格式3.1.2 参数3.1.3 案例 3.2 获取明细行所有行标示3.2.1 格式3.2.2 参数说明 1、需求说明 限制明细表的“类型”字段,在同一个流程表单…...
magicapi导出excel
参考:Hutool参考文档 response模块 | magic-api import response;import java.util.ArrayList; import java.util.LinkedHashMap; import java.util.List; import java.util.Map;import cn.hutool.core.collection.CollUtil; import cn.hutool.core.date.DateUtil; …...
【秋招突围】2024届秋招笔试-科大讯飞笔试题-03-三语言题解(Java/Cpp/Python)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系计划跟新各公司春秋招的笔试题 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📧 清隆这边…...
【JavaEE】-- HTTP
1. HTTP是什么? HTTP(全称为"超文本传输协议")是一种应用非常广泛的应用层协议,HTTP是基于TCP协议的一种应用层协议。 应用层协议:是计算机网络协议栈中最高层的协议,它定义了运行在不同主机上…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
爬虫基础学习day2
# 爬虫设计领域 工商:企查查、天眼查短视频:抖音、快手、西瓜 ---> 飞瓜电商:京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空:抓取所有航空公司价格 ---> 去哪儿自媒体:采集自媒体数据进…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
