当前位置: 首页 > news >正文

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.递增子序列 题意&#xff1a;给你一个整数数组 nums &#xff0c;找出并返回所有该数组中不同的递增子序列&#xff0c;递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。 数组中可能含有重复元素&#xff0c;如出现两个整数相等&#xff0c;也可以…...

pytorch nn.Embedding 用法和原理

nn.Embedding 是 PyTorch 中的一个模块&#xff0c;用于将离散的输入&#xff08;通常是词或子词的索引&#xff09;映射到连续的向量空间。它在自然语言处理和其他需要处理离散输入的任务中非常常用。以下是 nn.Embedding 的用法和原理。 用法 初始化 nn.Embedding nn.Embed…...

Python中常用的有7种值(数据)的类型及type()语句的用法

目录 0.Python中常用的有7种值&#xff08;数据&#xff09;的类型Python中的数据类型主要有&#xff1a;Number&#xff08;数字&#xff09;、Boolean&#xff08;布尔&#xff09;、String&#xff08;字符串&#xff09;、List&#xff08;列表&#xff09;、Tuple&#xf…...

某配送平台未授权访问和弱口令(附赠nuclei默认密码验证脚本)

找到一个某src的子站&#xff0c;通过信息收集插件&#xff0c;发现ZABBIX-监控系统&#xff0c;可以日一下 使用谷歌搜索历史漏洞&#xff1a;zabbix漏洞 通过目录扫描扫描到后台&#xff0c;谷歌搜索一下有没有默认弱口令 成功进去了&#xff0c;挖洞就是这么简单 搜索文章还…...

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系统&#xff0c;尽量更换源以提高安装软件的速度。 步骤 备份原始源列表sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak修改sources.list sudo vim /etc/apt/sources.list将内容替换成对应的源 **PS&#xff1a;清华源地址&#xff1a;https:…...

【高考志愿】 化学工程与技术

目录 一、专业概述 二、就业前景 三、就业方向 四、报考注意 五、专业发展与深造 六、化学工程与技术专业排名 七、总结 一、专业概述 化学工程与技术专业&#xff0c;这是一门深具挑战与机遇的综合性学科。它融合了工程技术的实用性和化学原理的严谨性&#xff0c;为毕…...

2024上半年网络与数据安全法规政策、国标、报告合集

事关大局&#xff0c;我国数据安全立法体系已基本形成并逐步细化。数据基础制度建设事关国家发展和安全大局&#xff0c;数据安全治理贯穿构建数据基础制度体系全过程。随着我国数字经济建设进程加快&#xff0c;数据安全立法实现由点到面、由面到体加速构建&#xff0c;目前已…...

基于SpringBoot扶农助农政策管理系统设计和实现(源码+LW+调试文档+讲解等)

&#x1f497;博主介绍&#xff1a;✌全网粉丝10W,CSDN作者、博客专家、全栈领域优质创作者&#xff0c;博客之星、平台优质作者、专注于Java、小程序技术领域和毕业项目实战✌&#x1f497; &#x1f31f;文末获取源码数据库&#x1f31f; 感兴趣的可以先收藏起来&#xff0c;…...

淘宝商铺电话怎么获取?使用爬虫工具采集

访问淘宝商铺是一个合法的行为&#xff0c;你可以使用爬虫工具来提取淘宝商铺的信息。下面是一个基本的Python程序示例&#xff0c;用于使用爬虫工具访问淘宝商铺&#xff1a; import requestsdef get_store_info(store_id):url fhttps://shop{id}.taobao.comresponse reque…...

ModStart:开源免费的PHP企业网站开发建设管理系统

大家好&#xff01;今天我要给大家介绍一款超级强大的开源工具——ModStart&#xff0c;它基于Laravel框架&#xff0c;是PHP企业网站开发建设的绝佳选择&#xff01; 为什么选择ModStart&#xff1f; 模块化设计&#xff1a;ModStart采用模块化设计&#xff0c;内置了众多基…...

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 使用环境要求&#xff1a;2 配置webdav3 测试局域网使用potplayer访问webdav4 内网穿透&#xff0c;映射至公网5 使用固定地址在potplayer访问webdav 前言 本文主要介绍如何在Windows设备使用potplayer播放器远程访问本地局域网的群晖NAS中的影视资源&#xff…...

Forecasting from LiDAR via Future Object Detection

Forecasting from LiDAR via Future Object Detection 基础信息 论文&#xff1a;cvpr2022paper https://openaccess.thecvf.com/content/CVPR2022/papers/Peri_Forecasting_From_LiDAR_via_Future_Object_Detection_CVPR_2022_paper.pdfgithub&#xff1a;https://github.co…...

【unity笔记】五、UI面板TextMeshPro 添加中文字体

Unity 中 TextMeshPro不支持中文字体&#xff0c;下面为解决方法&#xff1a; 准备字体文件&#xff0c;从Windows系统文件的Fonts文件夹里拖一个.ttf文件&#xff08;C盘 > Windows > Fonts &#xff09; 准备字库文件,新建一个文本文件&#xff0c;命名为“字库”&…...

如何在Windows 11上设置默认麦克风和相机?这里有详细步骤

如果你的Windows 11计算机上连接了多个麦克风或网络摄像头&#xff0c;并且希望自动使用特定设备&#xff0c;而不必每次都在设置中乱动&#xff0c;则必须将首选设备设置为默认设备。我们将向你展示如何做到这一点。 如何在Windows 11上更改默认麦克风 有两种方法可以将麦克…...

Flutter循序渐进==>数据结构(列表、映射和集合)和错误处理

导言 填鸭似的教育确实不行&#xff0c;我高中时学过集合&#xff0c;不知道有什么用&#xff0c;毫无兴趣&#xff0c;等到我学了一门编程语言后&#xff0c;才发现集合真的很有用&#xff1b;可以去重&#xff0c;可以看你有我没有的&#xff0c;可以看我有你没有的&#xf…...

泛微E9开发 限制明细表列的值重复

限制明细表列的值重复 1、需求说明2、实现方法3、扩展知识点3.1 修改单个字段值&#xff08;不支持附件类型&#xff09;3.1.1 格式3.1.2 参数3.1.3 案例 3.2 获取明细行所有行标示3.2.1 格式3.2.2 参数说明 1、需求说明 限制明细表的“类型”字段&#xff0c;在同一个流程表单…...

magicapi导出excel

参考&#xff1a;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)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系计划跟新各公司春秋招的笔试题 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f4e7; 清隆这边…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...