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

server/2024/11/15 0:27:26/

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.ppmy.cn/server/16797.html

相关文章

图论应用——拓扑排序

拓扑排序的原理和宽度优先搜索差不多 #include <iostream> #include <cstring> #include <algorithm> using namespace std;const int N 100010; int n,m; int h[N],e[N],ne[N],idx; int q[N],d[N];void add(int a,int b) {e[idx]b,ne[idx]h[a],h[a]idx; }…

外包干了9天,技术退步明显。。。。。

时光荏苒&#xff0c;转眼我已是一个拥有近四年功能测试经验的大专生。19年&#xff0c;我满怀激情地通过校招进入湖南某知名软件公司&#xff0c;期待在这里开启我的职业生涯。然而&#xff0c;长时间的舒适环境让我渐渐失去了前进的动力&#xff0c;技术停滞不前&#xff0c;…

李沐66_使用注意力机制的seq2seq——自学笔记

加入注意力 1.编码器对每次词的输出作为key和value 2.解码器RNN对上一个词的输出是query 3.注意力的输出和下一个词的词嵌入合并进入RNN 一个带有Bahdanau注意力的循环神经网络编码器-解码器模型 总结 1.seq2seq通过隐状态在编码器和解码器中传递信息 2.注意力机制可以根…

linux DNS域名解析服务

目录 一.DNS DNS系统的作用 域名结构&#xff1a; 根域 顶级域 二级域 子域 主机 二.DNS解析过程 迭代查询&#xff1a; 递归查询&#xff1a; 三.实验模拟 主、从服务器设置 1.搭建本地DNS服务器------(主服务器配置) 1&#xff09;初始化系统 ​编辑2&#xf…

redis模糊查询redis中的key

redis模糊查询redis中的key 方式一&#xff1a;使用keys命令 /*** 查找匹配的key** param pattern* return*/ public Set<String> keys(String pattern) {return redisTemplate.keys(pattern); }方式二&#xff1a;使用san命令 /*** 查找匹配的key** param pattern* r…

一个网络空间安全的小游戏

为了编写一个网络空间安全的小游戏&#xff0c;我们可以模拟一些基本的网络安全概念&#xff0c;如防火墙、入侵检测、病毒清理等。以下是一个简单的Python小游戏示例&#xff0c;其中玩家需要保护自己的网络免受攻击。 python复制代码 import random class Network: def __…

R可视化:桑基图展示数据层流动

介绍 以桑基图形式展示数据分布情况 加载R包 knitr::opts_chunk$set(message = FALSE, warning = FALSE) library(tidyverse) library(ggalluvial)# rm(list = ls()) options(stringsAsFactors = F) options(future.globals.maxSize = 10000 * 1024^2) 导入数据 metadata…

CSS常用背景属性

CSS常用背景属性 背景属性背景色背景图背景图平铺方式背景图位置背景图缩放背景图片固定背景图复合属性 背景属性 描述属性背景色background-color背景图background-image背景图平铺方式background-repeat背景图位置background-position背景图缩放background-size背景图固定ba…