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

代码随想录算法训练营第二十九天|LeetCode491 非递减子序列、LeetCode46 全排列、LeetCode47 全排列Ⅱ

题1:

指路:491. 非递减子序列 - 力扣(LeetCode)
思路与代码:

对于这个题我们应该想起我们做过的子集问题,就是在原来的问题上加一个去重操作。我们用unordered_set集合去重,集合中使用过的元素,我们要对结果集进行横向去重:集合中有的元素就已经被用过,弃之。代码如下:

class Solution {private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {if (path.size() >= 2 && path.size() <= nums.size()) {result.push_back(path);}unordered_set<int> uset;  // 元素去重集合    for (int i = startIndex; i < nums.size(); i++) {if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end())continue;uset.insert(nums[i]);path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();  }}
public:vector<vector<int>> findSubsequences(vector<int>& nums) {backtracking(nums, 0);return result;}
};

题2:

指路:46. 全排列 - 力扣(LeetCode)
思路与代码:

排列与组合的不同点在于:组合无顺序,排列有顺序。例如:[1, 2, 3] 和[3, 2, 1],对于组合来说二者无区别,对于排列来说,二者有区别。所以这也是单层循环逻辑中的不同所在:我们每次从数组i = 0的地方开始遍历,如果遇到未遍历过的元素则加入路径集,反之如果是已经遍历过的元素则跳过本轮循环继而寻找下一元素。其中,我们用used数组来标识元素是否用过。初始化为false,用过则赋值为true。最终当路径集大小与原数组集相等时加入最终结果集。代码如下:

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++) {  // 0开始,全排列if (used[i] == true) continue;  // 用过的元素跳过,直接取下一个元素used[i] = true;path.push_back(nums[i]);backtracking(nums, used);used[i] = false;  // 回溯path.pop_back();}}
public:vector<vector<int>> permute(vector<int>& nums) {vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

题3:

指路:47. 全排列 II - 力扣(LeetCode)
思路与代码:

相似于上题排列,本题不同点在于有了重复元素,这就意味着会出现重复子序列,所以需要我们做的就是去重。相似于组合总和Ⅱ的去重操作。我们将数组排序得到一个升序数组,如果相邻两个元素相等时,只需要得到一个数的子序列即可。代码如下:

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++) {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) {vector<bool> used (nums.size(), false);sort(nums.begin(), nums.end());backtracking(nums, used);return result;}
};

相关文章:

代码随想录算法训练营第二十九天|LeetCode491 非递减子序列、LeetCode46 全排列、LeetCode47 全排列Ⅱ

题1&#xff1a; 指路&#xff1a;491. 非递减子序列 - 力扣&#xff08;LeetCode&#xff09; 思路与代码&#xff1a; 对于这个题我们应该想起我们做过的子集问题&#xff0c;就是在原来的问题上加一个去重操作。我们用unordered_set集合去重&#xff0c;集合中使用过的元…...

初识C++ · 优先级队列

目录 前言&#xff1a; 1 优先级队列的使用 2 优先级队列的实现 3 仿函数 前言&#xff1a; 栈和队列相对其他容器来说是比较简单的&#xff0c;在stl里面&#xff0c;有一种容器适配器是优先级队列&#xff08;priority_queue&#xff09;&#xff0c;它也是个队列&#…...

php反序列化入门

一&#xff0c;php面向对象。 1.面向对象&#xff1a; 以“对象”伪中心的编程思想&#xff0c;把要解决的问题分解成对象&#xff0c;简单理解为套用模版&#xff0c;注重结果。 2.面向过程&#xff1a; 以“整体事件”为中心的编程思想&#xff0c;把解决问题的步骤分析出…...

嵌入式 Linux LED 驱动开发实验学习

I.MX6U-ALPHA 开发板上的 LED 连接到 I.MX6ULL 的 GPIO1_IO03 这个引脚上&#xff0c;进行这个驱动开发实验之前&#xff0c;需要了解下地址映射。 地址映射 MMU 全称叫做 MemoryManage Unit&#xff0c;也就是内存管理单元。在老版本的 Linux 中要求处理器必须有 MMU&#x…...

C++:多态

文章目录 多态的概念多态的定义及实现多态的构成条件虚函数虚函数的重写override 和 final重载、重写&#xff08;覆盖&#xff09;、重定义&#xff08;隐藏&#xff09;的对比 抽象类概念接口继承和实现继承 多态的原理虚函数表多态的原理 单继承和多继承关系的虚函数表单继承…...

Java事务入门:从基础概念到初步实践

Java事务入门&#xff1a;从基础概念到初步实践 引言1. Java事务基础概念1.1 什么是事务&#xff1f;1.2 为什么需要事务&#xff1f; 2. Java事务管理2.1 JDBC 的事务管理2.2 Spring 事务管理2.2.1 Spring JDBC2.2.1.1 添加 Spring 配置2.2.1.2 添加业务代码并测试验证 2.2.2…...

鸿蒙轻内核M核源码分析系列七 动态内存Dynamic Memory

内存管理模块管理系统的内存资源&#xff0c;它是操作系统的核心模块之一&#xff0c;主要包括内存的初始化、分配以及释放。 在系统运行过程中&#xff0c;内存管理模块通过对内存的申请/释放来管理用户和OS对内存的使用&#xff0c;使内存的利用率和使用效率达到最优&#x…...

从头搭hadoop集群--分布式hadoop集群搭建

模板虚拟机安装配置见博文&#xff1a;https://blog.csdn.net/weixin_66158110/article/details/139236148 配置文件信息如下&#xff1a;https://pan.baidu.com/s/1074eD5aNVugEPcjwVvi9jA?pwdl1xq&#xff08;提取码&#xff1a;l1xq&#xff09; hadoop版本&#xff1a;h…...

odoo10 权限控制用户只允许看到自己的字段

假设一个小区管理员用户&#xff0c;只想看到自己小区的信息。 首先添加一个用户信息选项卡界面&#xff0c;如下图的 用户 > 隶属信息&#xff1a; 我们在自己创建的user模块中&#xff0c;views文件夹下添加base_user.xml <?xml version"1.0" encoding&q…...

图解Mysql索引原理

概述 是什么 索引像是一本书的目录列表&#xff0c;能根据目录快速的找到具体的书本内容&#xff0c;也就是加快了数据库的查询速度索引本质是一个数据结构索引是在存储引擎层&#xff0c;而不是服务器层实现的&#xff0c;所以&#xff0c;并没有统一的索引标准&#xff0c;…...

Arduino网页服务器:如何将Arduino开发板用作Web服务器

大家好&#xff0c;我是咕噜铁蛋&#xff01;今天&#xff0c;我将和大家分享一个有趣且实用的项目——如何使用Arduino开发板搭建一个简易的网页服务器。通过这个项目&#xff0c;你可以将Arduino连接到互联网&#xff0c;并通过网页控制或查询Arduino的状态。 一、项目背景与…...

大模型日报2024-06-05

大模型日报 2024-06-05 大模型资讯 AI气象预测取得重大进展&#xff1a;单台桌面电脑即可运行全球天气模型 摘要: 一项新的人工智能天气预测模型已经取得重大进展&#xff0c;该模型能够在一台普通的桌面电脑上运行&#xff0c;预测全球天气。这意味着即使没有复杂的物理计算&a…...

LLM 大模型学习必知必会系列(二):提示词工程-Prompt Engineering 以及实战闯关

角色扮演&#xff1a;在系统指令中告诉千问你需要它扮演的角色&#xff0c;即可沉浸式和该角色对话交流语言风格&#xff1a;简单调整 LLM 的语言风格任务设定&#xff1a;比如旅行规划&#xff0c;小红书文案助手这样的专项任务处理System message 也可以被用于规定 LLM 的答复…...

Spring系统学习 - Spring入门

什么是Spring&#xff1f; Spring翻译过来就是春天的意思&#xff0c;字面意思&#xff0c;冠以Spring的意思就是想表示使用这个框架&#xff0c;代表程序员的春天来了&#xff0c;实际上就是让开发更加简单方便&#xff0c;实际上Spring确实做到了。 官网地址&#xff1a;ht…...

Priority_queue

一、priority_queue的介绍和使用 1.1 priority_queue的介绍 1.优先队列是一种容器适配器&#xff0c;根据严格的弱排序标准&#xff0c;它的第一个元素总是它所包含的元素中最大的。 2.优先队列类似于堆&#xff0c; 在堆中可以随时插入元素&#xff0c; 并且只能检索最大堆…...

SpringMVC:获取请求数据

1. 通过RequestParma注解接收 /**** value和name都可以使用&#xff0c;互为别名* 如果此处设置了需要什么参数而前端请求时没有提供则会报400&#xff08;请求参数不一致错误&#xff09;* required参数用于设置该参数是否为必须传递参数&#xff0c;默认为true必须传递* defa…...

深度学习 --- stanford cs231 编程作业(assignment1,Q2: SVM分类器)

stanford cs231 编程作业之SVM分类器 写在最前面&#xff1a; 深度学习&#xff0c;或者是广义上的任何学习&#xff0c;都是“行千里路”胜过“读万卷书”的学识。这两天光是学了斯坦福cs231n的一些基础理论&#xff0c;越往后学越觉得没什么。但听的云里雾里的地方也越来越多…...

【scikit-learn010】sklearn算法模型清单实战及经验总结(已更新)

1.一直以来想写下基于scikit-learn训练AI算法的系列文章,作为较火的机器学习框架,也是日常项目开发中常用的一款工具,最近刚好挤时间梳理、总结下这块儿的知识体系。 2.熟悉、梳理、总结下scikit-learn框架模型算法包相关技术点及经验。 3.欢迎批评指正,欢迎互三,跪谢一键…...

Rethinking overlooked aspects in vision-language models

探讨多模态视觉语言模型的一些有趣结论欢迎关注 CVHub!https://mp.weixin.qq.com/s/zouNu-g-33_7JoX3Uscxtw1.Introduction 多模态模型架构上的变化不大,数据的差距比较大,输入分辨率和输入llm的视觉token大小是比较关键的,适配器,VIT和语言模型则不是那么关键。InternVL-…...

【漯河市人才交流中心_登录安全分析报告-Ajax泄漏滑动距离导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...