每日两题 / 46. 全排列 41. 缺失的第一个正数(LeetCode热题100)

46. 全排列 - 力扣(LeetCode)
image.png

经典回溯题,每次搜索选择未选择数字中的一个
当选择了n个数时,将已经选择的数加入答案

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<int> a;vector<vector<int>> ans;vector<int> st(nums.size(), 0);function<void()> dfs = [&](){if (a.size() == nums.size()){ans.push_back(a);return;}for (int i = 0; i < nums.size(); ++ i){if (!st[i]) {a.push_back(nums[i]);st[i] = 1;dfs();st[i] = 0;a.pop_back();}}};dfs();return ans;}
};

41. 缺失的第一个正数 - 力扣(LeetCode)
image.png

题目要求使用常数空间解决问题,也就是可以使用题目传入的数组
若数组长度为n,那么答案最多为n + 1
利用数组下标记录值为(值为数组下标+1)的数是否出现过
若是出现了,将其乘以-1(如果是正数),而数组中原本就存在负数,这些负数不影响答案,将它们先设置为n + 1
接着遍历整个数组,对于每个数取绝对值,若该数>n,则跳过
否则将(该数的值 - 1)作为数组下标,将该位置上的数置为负数
最后从头开始遍历数组,出现的第一个正数的(下标+1)则为答案

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int i = 0; i < n; ++ i)if (nums[i] <= 0) nums[i] = n + 1;for (int i = 0; i < n; ++ i){int num = abs(nums[i]);if (num <= n && num >= 1 && nums[num - 1] >= 0) nums[num - 1] *= -1;}for (int i = 0; i < n; ++ i)if (nums[i] >= 0)return i + 1;return n + 1;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/316677.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Transformer模型详解02-Positional Encoding(位置编码)

文章目录 什么是位置编码连续有界为什么要有界为什么要连续 位置编码的演变用整型值标记位置用[0,1]范围标记位置用二进制向量标记位置用周期函数&#xff08;sin&#xff09;来表示位置sin函数周期振幅&#xff0c;相移&#xff0c;垂直位移频率波长 sin表示位置 用sin和cos交…

QT学习之读取xml中信息

背景&#xff1a; 我们每次注册后会生成对应的启动码文件&#xff0c;格式如下&#xff0c;启动码最后要在测试工具使用的进行一个验证&#xff0c;验证通过后模块才能使用。所以我希望每次的xml都放在一个文件夹里&#xff0c;等我选择文件夹后&#xff0c;能提取所有xml中的对…

【Node.js】03 —— HTTP 模块探索

&#x1f31f;Node.js之HTTP模块探索✨ &#x1f31f;引言 在网络编程中&#xff0c;HTTP协议无处不在。在Node.js的世界里&#xff0c;我们可以通过内置的http模块来轻松创建HTTP服务器和客户端&#xff0c;实现数据的接收和发送。今天就让我们一起打开这扇门&#xff0c;探索…

【QT进阶】Qt http编程之实现websocket server服务器端

往期回顾 【QT进阶】Qt http编程之json解析的简单介绍-CSDN博客 【QT进阶】Qt http编程之nlohmann json库使用的简单介绍-CSDN博客 【QT进阶】Qt http编程之websocket的简单介绍-CSDN博客 【QT进阶】Qt http编程之实现websocket server服务器端 一、最终效果 通过ip地址和端口…

代码随想录算法训练营第二十六天||39. 组合总和、40.组合总和II、131.分割回文串

文章目录 一、39. 组合总和 思路 二、40.组合总和II 思路 三、131.分割回文串 思路 一、39. 组合总和 给定一个无重复元素的数组 candidates 和一个目标数 target &#xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的数字可以无限制重复被选取…

Vitis HLS 学习笔记--HLS入门示例集合-目录

目录 1. 示例集合概述 2. Interface 接口 2.1 Aggregation_Disaggregation 2.1.1 aggregation_of_m_axi_ports 2.1.2 aggregation_of_nested_structs 2.1.3 aggregation_of_struct 2.1.4 auto_disaggregation_of_struct 2.1.5 disaggregation_of_axis_port 2.1.6 stru…

Liunx磁盘管理(上)

一.硬盘类型 机械硬盘&#xff08;HDD&#xff09; 机械硬盘&#xff08;HDD&#xff09;是一种存储设备&#xff0c;使用旋转磁盘和读/写磁头来存储和检索数据。以下是机械硬盘的基本结构&#xff1a; 盘片&#xff08;Platters&#xff09;&#xff1a;机械硬盘通常由多个盘…

element的el-table 解决表格多页选择数据时,数据被清空

问题&#xff1a;切换页码时&#xff0c;勾选的数据会被清空 重点看我圈出来的&#xff0c;直接复制&#xff0c;注意&#xff0c;我这里 return row.productId;一般大家的是 return row.id,根据接口定的唯一变量 :row-key"getRowKeys"​​​​​​​:reserve-sele…

基于STM32和阿里云的智能台灯(STM32+ESP8266+MQTT+阿里云+语音模块)

一、主要完成功能 1、冷光模式和暖光模式两种灯光 主要支持冷光和暖光模式两种&#xff0c;可以通过语音模块或手机app远程切换冷暖光 2、自动模式和手动模式 主要支持手动模式和自动两种模式&#xff08;app或语音助手切换&#xff09; (1)自动模式&#xff1a;根据环境光照…

通信原理(2)--随机过程

通信原理(2)–随机过程 3.1随机过程的基本概念 随机过程{x(t)}由一族时间函数 x i ( t ) x_i(t) xi​(t)&#xff0c;i1,2.3…组成&#xff0c;每一个时间函数 x i ( t ) x_i(t) xi​(t)称为随机过程{x(t)}的一个样本函数&#xff08;一个实现&#xff09; 每个样本函数在时间…

http1.1和http2.0的同源请求数限制

判断协议版本 :scheme: 在请求头中表示使用的是HTTP/2协议。即 出现 :开头的请求头Chrome 只支持查看 HTTP/1.x 的 Raw Headers&#xff0c;对这种请求&#xff0c;会给出 view source 选项。HTTP2.0不给出。可继续学习 https://www.cnblogs.com/kirito-c/p/10360868.html抓包…

笔记:编写程序,分别采用面向对象和 pyplot 快捷函数的方式绘制正弦曲线 和余弦曲线。 提示:使用 sin()或 cos()函数生成正弦值或余弦值。

文章目录 前言一、面向对象和 pyplot 快捷函数的方式是什么&#xff1f;二、编写代码面向对象的方法&#xff1a;使用 pyplot 快捷函数的方法&#xff1a; 总结 前言 本文将探讨如何使用编程语言编写程序&#xff0c;通过两种不同的方法绘制正弦曲线和余弦曲线。我们将分别采用…

DSP开发实战教程--EPWM模块的影子寄存器详细讲解原理和代码实例

EPWM模块影子寄存器的原理 在TI&#xff08;Texas Instruments&#xff09;的DSP28335中&#xff0c;EPWM&#xff08;Enhanced Pulse Width Modulator&#xff09;模块提供了高精度、高灵活性的PWM信号生成功能。为了能在不影响当前PWM波形输出的情况下预装载新的PWM参数&…

cocos-lua资源管理

本文介绍cocos-lua项目的资源管理和工作流&#xff0c;适用人群包括初学者和有经验开发者&#xff0c;故读者可根据自己的需要有选择性的查阅自己需要的内容&#xff0c;下文以ccs代指Cocos Studio 一.简单案例解析 下文通过介绍一个简单demo&#xff0c;介绍合图和资源目录结…

[C++][算法基础]最大不相交区间数量(贪心 + 区间问题2)

给定 &#x1d441; 个闭区间 [&#x1d44e;&#x1d456;,&#x1d44f;&#x1d456;]&#xff0c;请你在数轴上选择若干区间&#xff0c;使得选中的区间之间互不相交&#xff08;包括端点&#xff09;。 输出可选取区间的最大数量。 输入格式 第一行包含整数 &#x1d4…

【算法基础实验】图论-UnionFind连通性检测之quick-union

Union-Find连通性检测之quick-union 理论基础 在图论和计算机科学中&#xff0c;Union-Find 或并查集是一种用于处理一组元素分成的多个不相交集合&#xff08;即连通分量&#xff09;的情况&#xff0c;并能快速回答这组元素中任意两个元素是否在同一集合中的问题。Union-Fi…

PHP源码_最新在线工具箱网站系统源码

项目运行截图 源码贡献 https://githubs.xyz/boot?app41 部分数据库表 SET NAMES utf8mb4; SET FOREIGN_KEY_CHECKS 0;-- ---------------------------- -- Table structure for toolbox_category -- ---------------------------- DROP TABLE IF EXISTS toolbox_category…

StarRocks x Paimon 构建极速实时湖仓分析架构实践

Paimon 介绍 Apache Paimon 是新一代的湖格式&#xff0c;可以使用 Flink 和 Spark 构建实时 Lakehouse 架构&#xff0c;以进行流式处理和批处理操作。Paimon 创新性地使用 LSM&#xff08;日志结构合并树&#xff09;结构&#xff0c;将实时流式更新引入 Lakehouse 架构中。 …

医学vr虚拟仿真综合实验教学平台为科研教学提供了坚实的基础

在兽医专业的广袤领域中&#xff0c;动物解剖学作为基石学科&#xff0c;为组织胚胎学、生理学、病理解剖学、外科手术学、临床诊断学等科研教学提供了坚实的基础。而如今&#xff0c;随着科技的飞速发展&#xff0c;我们迎来了一个全新的学习时代——3D数字动物解刨虚拟仿真实…

[iOS]使用CocoaPods发布公开库

1.检查库名是否已被占用 选择库名时&#xff0c;尽量选择具有描述性并且独特的名字&#xff0c;这不仅可以避免命名冲突&#xff0c;还可以帮助用户更好地理解库的用途和功能。 在实际创建和发布 CocoaPods 库之前&#xff0c;确实应该检查库名是否已经被占用&#xff0c;以避…