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大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📧 清隆这边…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
高防服务器能够抵御哪些网络攻击呢?
高防服务器作为一种有着高度防御能力的服务器,可以帮助网站应对分布式拒绝服务攻击,有效识别和清理一些恶意的网络流量,为用户提供安全且稳定的网络环境,那么,高防服务器一般都可以抵御哪些网络攻击呢?下面…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
篇章二 论坛系统——系统设计
目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...
