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

day29|leetcode|C++|491. 非递减子序列|46. 全排列|47. 全排列 II

Leetcode 491. 非递减子序列

链接:491. 非递减子序列

thought:

  • 设 stack 中最后一个值的位置为 last。如果 stack 为空,则 last = -1。
    设当前正在处理的位置为 pos。
  • 如果在 nums 的子区间 [last+1, pos) 中,存在和 nums[pos] 相同的值,则当前 nums[pos] 必须丢弃,不然会产生重复的子序列。

在这里插入图片描述

完整C++代码如下

class Solution {
public:vector<vector<int>> findSubsequences(vector<int>& nums) {vector<vector<int>> res;vector<int> path;backtracking(res, nums, path, 0);return res;}private:void backtracking(vector<vector<int>>& res, vector<int>& nums, vector<int>& path, int start) {if (path.size() >= 2) // 如果当前递增子序列长度大于等于2,则将其加入结果集res.push_back(path);unordered_set<int> seen; // 用一个集合来记录当前层已经使用过的数字,避免重复//注意为当前层for (int i = start; i < nums.size(); ++i) {if ((!path.empty() && nums[i] < path.back()) || seen.count(nums[i])) // 如果当前数字小于上一个数字(不符合递增)或者已经使用过,则跳过continue;seen.insert(nums[i]); // 将当前数字加入集合path.push_back(nums[i]); // 将当前数字加入递增序列backtracking(res, nums, path, i + 1); // 递归搜索下一个位置path.pop_back(); // 回溯,将当前数字从递增序列中删除}}
};

Leetcode 46. 全排列

链接:46. 全排列

thought:

设置bool数组记录当前位置数是否已经使用过,若使用过直接跳过

完整C++代码如下

class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<int>path;vector<vector<int>>res;vector<bool>used(nums.size(),false);backtracking(nums,path,res,used);return res;}void backtracking(vector<int>& nums,vector<int>&path,vector<vector<int>>&res,vector<bool>&used){if(path.size()==nums.size()){res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(used[i])continue;used[i]=true;path.push_back(nums[i]);backtracking(nums,path,res,used);//递归path.pop_back();//回溯used[i]=false;//回溯}}
};

Leetcode 47. 全排列 II

链接:47. 全排列 II

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++) {// used[i - 1] == true,说明同一树枝nums[i - 1]使用过// used[i - 1] == false,说明同一树层nums[i - 1]使用过// 如果同一树层nums[i - 1]使用过则直接跳过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) {result.clear();path.clear();sort(nums.begin(), nums.end()); // 排序vector<bool> used(nums.size(), false);backtracking(nums, used);return result;}
};

相关文章:

day29|leetcode|C++|491. 非递减子序列|46. 全排列|47. 全排列 II

Leetcode 491. 非递减子序列 链接&#xff1a;491. 非递减子序列 thought: 设 stack 中最后一个值的位置为 last。如果 stack 为空&#xff0c;则 last -1。 设当前正在处理的位置为 pos。如果在 nums 的子区间 [last1, pos) 中&#xff0c;存在和 nums[pos] 相同的值&…...

[Java、Android面试]_12_java访问修饰符、抽象类和接口

文章目录 1. java访问修饰符2. 抽象类和接口2.1 抽象类2.2 接口2.3 抽象类和接口的区别 本人今年参加了很多面试&#xff0c;也有幸拿到了一些大厂的offer&#xff0c;整理了众多面试资料&#xff0c;后续还会分享众多面试资料。 整理成了面试系列&#xff0c;由于时间有限&…...

Linux:Prometheus的源码包安装及操作(2)

环境介绍 三台centos 7系统&#xff0c;运行内存都2G 1.prometheus监控服务器&#xff1a;192.168.6.1 主机名&#xff1a;pm 2.grafana展示服务器:192.168.6.2 主机名&#xff1a;gr 3.被监控服务器&#xff1a;192.168.6.3 …...

MongoDB聚合运算符:$integral

文章目录 语法使用举例 $integral聚合运算符只能用在$setWindowField阶段&#xff0c;返回曲线下面积的近似值&#xff0c;该曲线是使用梯形规则计算的&#xff0c;其中每组相邻文档使用以下公式形成一个梯形&#xff1a; $setWindowFields阶段中用于积分间隔的sortBy字段值$i…...

手撕算法-买卖股票的最佳时机 II(买卖多次)

描述 分析 使用动态规划。dp[i][0] 代表 第i天没有股票的最大利润dp[i][1] 代表 第i天持有股票的最大利润 状态转移方程为&#xff1a;dp[i][0] max(dp[i-1][0], dp[i-1][1] prices[i]); // 前一天没有股票&#xff0c;和前一天有股票今天卖掉的最大值dp[i][1] max(dp[i-1…...

技术创新与产业升级

在政府工作报告中,新兴技术如云计算、大数据、人工智能等被多次提及,这反映了政府高度重视新一代信息技术在推动经济社会发展中的重要作用。对于计算机行业而言,抓住这些新兴技术的发展机遇,推动技术创新和产业升级,将是未来发展的关键所在。 云计算作为一种新兴的计算模式,正…...

透视未来工厂:山海鲸可视化打造数字孪生新篇章

在信息化浪潮的推动下&#xff0c;数字孪生工厂项目正成为工业制造领域的新宠。作为一名山海鲸可视化的资深用户&#xff0c;我深感其强大的数据可视化能力和数字孪生技术在工厂管理中的应用价值&#xff0c;同时我们公司之前也和山海鲸可视化合作制作了一个智慧工厂项目&#…...

三.寄存器(内存访问)

1.内存中字的存储 2.并不是所有cpu都支持将数据段送入段寄存器&#xff0c;所以有时候用个别的寄存器先把数据段存储起来&#xff0c;再把该寄存器mov到段寄存器。 3.字的传送 4.栈 5.栈机制 举例说明 6.栈顶超界问题 push超界 pop超界 7.栈段...

Day31 贪心算法

Day31 贪心算法 455.分发饼干 我的思路&#xff1a; 小孩数组g指针一直前移&#xff0c;只有饼干数组s满足条件时&#xff0c;才前移&#xff0c;并且更新num 解答&#xff1a; class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.…...

【WEEK4】 【DAY5】AJAX - Part Two【English Version】

2024.3.22 Friday Following the previous article 【WEEK4】 【DAY4】AJAX - Part One【English Version】 Contents 8.4. Ajax Asynchronous Data Loading8.4.1. Create User.java8.4.2. Add lombok and jackson support in pom.xml8.4.3. Change Tomcat Settings8.4.4. Mo…...

力扣100热题[哈希]:最长连续序列

原题&#xff1a;128. 最长连续序列 题解&#xff1a; 官方题解&#xff1a;. - 力扣&#xff08;LeetCode&#xff09;题解&#xff0c;最长连续序列 &#xff1a;哈希表 官方解题思路是先去重&#xff0c;然后判断模板长度的数值是否存在&#xff0c;存在就刷新&#xff0c…...

python笔记基础--文件和存储数据(7)

目录 1.从文件中读取数据 2.写入文件 3.存储数据 3.1使用json.dump()和json.load() 3.2保存和读取用户生成的数据 3.3重构 1.从文件中读取数据 读取整个文件 with open(data.txt) as file_object: contents file_object.read()print(contents)print(contents.rstrip…...

Vue黑马笔记(最新)

VUE vue是一个用于构建用户界面的渐进式框架 创建一个VUE实例 核心步骤&#xff1a; 准备容器引包&#xff08;官网&#xff09;-开发版本/生产版本创建一个vue实例 new vue()指定配置项->渲染数据 el指定挂载点&#xff08;选择器&#xff09;,指定管理的是哪个容器。dat…...

安全工具介绍 SCNR/Arachni

关于SCNR 原来叫Arachni 是开源的&#xff0c;现在是SCNR&#xff0c;商用工具了 可试用一个月 Arachni Web Application Security Scanner Framework 看名字就知道了&#xff0c;针对web app 的安全工具&#xff0c;DASTIAST吧 安装 安装之前先 sudo apt-get update sudo…...

赋能数据收集:从机票网站提取特价优惠的JavaScript技巧

背景介绍 在这个信息时代&#xff0c;数据的收集和分析对于旅游行业至关重要。在竞争激烈的市场中&#xff0c;实时获取最新的机票特价信息能够为旅行者和旅游企业带来巨大的优势。 随着机票价格的频繁波动&#xff0c;以及航空公司和旅行网站不断推出的限时特价优惠&#xff…...

【大模型】在VS Code(Visual Studio Code)上安装中文汉化版插件

文章目录 一、下载安装二、配置显示语言&#xff08;一&#xff09;调出即将输入命令的搜索模式&#xff08;二&#xff09;在大于号后面输入&#xff1a;Configure Display Language&#xff08;三&#xff09;重启 三、总结 【运行系统】win 11 【本文解决的问题】 1、英文不…...

自定义WordPress顶部的菜单的方法

要自定义WordPress顶部的菜单&#xff0c;你需要使用WordPress的菜单系统。首先&#xff0c;你需要创建自定义菜单&#xff0c;然后将其设置为顶部导航菜单。 以下是创建自定义菜单并设置其为顶部导航菜单的步骤&#xff1a; 登录到WordPress管理界面。转到“外观”>“菜单…...

独孤思维:流量暴涨,却惨遭违规

最近独孤操作虚拟资料短视频&#xff0c;有个很深的感悟。 每天发10条短视频&#xff0c;积累到20天左右&#xff0c;播放量和粉丝数开始暴涨。 虽然很多牛比的比我数据好&#xff0c;但是对于刚做短视频的独孤来说&#xff0c;我已经满足了。 但是又发了10来天&#xff0c;…...

【python 装饰器 - 重试】做一个简易重试装饰器,如果函数执行错误则会自动重新执行,可设置重试次数,对爬虫比较友好

文章日期&#xff1a;2024.03.19 使用工具&#xff1a;Python 类型&#xff1a;装饰器 文章全程已做去敏处理&#xff01;&#xff01;&#xff01; 【需要做的可联系我】 AES解密处理&#xff08;直接解密即可&#xff09;&#xff08;crypto-js.js 标准算法&#xff09;&…...

Linux线程补充之——同步

一、Linux线程同步 ​ 同步是相对于竞争的概念&#xff1b; ​ 同步就是在保证安全的前提下啊&#xff0c;按照一定的顺序访问临界资源&#xff1b; ​ 所有的资源一定是先访问的临界资源&#xff0c;申请失败然后才进行排队的&#xff1b;互斥锁保证的是来访问的进程只允许…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...