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

代码随想录算法训练营第二十九天| 491 递增子序列 46 全排列

目录

491 递增子序列

46 全排列


491 递增子序列

在dfs中进行判断,如果path的长度大于1,则将其添加到res中。

本题nums中的元素的值处于-100与100之间,可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过,如果在此树层使用过,则应该跳过本层循环来避免重复,如果未使用过则可以将该元素添加到path中。

class Solution {List<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList();public List<List<Integer>> findSubsequences(int[] nums) {dfs(0,nums);return res;}private void dfs(int cnt,int[] nums){if(path.size() >= 2){res.add(new LinkedList(path));//这里不返回}boolean st[] = new boolean[205];//nums中的元素位于-100到100之间,可以将其映射到0到200中,st用来记录此层元素是否被遍历过for(int i = cnt;i < nums.length;i++){if(path.size() > 0 && path.get(path.size() - 1) > nums[i])continue;//如果不能形成递增序列则跳过此层循环if(st[nums[i] + 100])continue;//该树层出现过该元素,会导致重复,应该跳过此层循环st[nums[i] + 100] = true;path.add(nums[i]);dfs(i + 1,nums);path.remove(path.size() - 1);}}
}

时间复杂度O(2^{n}×n)

空间复杂度O(n)

46 全排列

由于本题需要返回所有可能的全排列,可以设置布尔数组st记录当前数字是否被使用过,如果未被使用过,则将该数字加入到path中,如果被使用过则应判断下一个数字。 

class Solution {List<List<Integer>>res = new ArrayList<>();List<Integer>path = new LinkedList<>();boolean st[];public List<List<Integer>> permute(int[] nums) {st = new boolean[nums.length];dfs(nums);return res;}private void dfs(int nums[]){if(path.size() == nums.length){res.add(new LinkedList(path));return;}for(int i = 0;i < nums.length;i++){if(st[i])continue;st[i] = true;path.add(nums[i]);dfs(nums);path.remove(path.size() - 1);st[i] = false;}}
}

时间复杂度O(n×n!)

空间复杂度O(n)

相关文章:

代码随想录算法训练营第二十九天| 491 递增子序列 46 全排列

目录 491 递增子序列 46 全排列 491 递增子序列 在dfs中进行判断&#xff0c;如果path的长度大于1&#xff0c;则将其添加到res中。 本题nums中的元素的值处于-100与100之间&#xff0c;可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过&#xff0c;…...

(动手学习深度学习)第13章 实战kaggle竞赛:CIFAR-10

导入相关库 import collections import math import os import shutil import pandas as pd import torch import torchvision from torch import nn from d2l import torch as d2l下载数据集 d2l.DATA_HUB[cifar10_tiny] (d2l.DATA_URL kaggle_cifar10_tiny.zip,2068874e4…...

Go 语言中的map和内存泄漏

map在内存中总是会增长&#xff1b;它不会收缩。因此&#xff0c;如果map导致了一些内存问题&#xff0c;你可以尝试不同的选项&#xff0c;比如强制 Go 重新创建map或使用指针。 在 Go 中使用map时&#xff0c;我们需要了解map增长和收缩的一些重要特性。让我们深入探讨这一点…...

前缀和(c++,超详细,含二维)

前缀和与差分 当给定一段整数序列a1,a2,a3,a4,a5…an; 每次让我们求一段区间的和&#xff0c;正常做法是for循环遍历区间起始点到结束点&#xff0c;进行求和计算&#xff0c;但是当询问次数很多并且区间很长的时候 比如&#xff0c;10^5 个询问和10^6区间长度&#xff0c;相…...

详解FreeRTOS:二值信号量和计数信号量(高级篇—2)

目录 1、二值信号量 1.1、二值信号量运行机制 1.2、创建二值信号量 1...

持续集成交付CICD:Jenkins通过API触发流水线

目录 一、理论 1.HTTP请求 2.调用接口的方法 3.HTTP常见错误码 二、实验 1.Jenkins通过API触发流水线 三、问题 1.如何拿到上一次jenkinsfile文件进行自动触发流水线 一、理论 1.HTTP请求 &#xff08;1&#xff09;概念 HTTP超文本传输协议&#xff0c;是确保服务器…...

【Python】12 GPflow安装

概述 GPflow 是一个基于TensorFlow 在 Python 中构建高斯过程模型的包。高斯过程是一种监督学习模型。 高斯过程的一些优点是&#xff1a; 不确定性是高斯过程的固有部分。高斯过程可以在不知道答案时告诉您。适用于小型数据集。如果您的数据有限&#xff0c;高斯过程可以从…...

Ubuntu源码编译gdal3.6.2

在华为云申请了一台Ubuntu v18的机器,乱七八糟的不要装。 apt install build-essential pkg-config -y cmake-3.21.1 apt-get install openssl libssl-dev 过程参考&#xff1a;Yukon for PostgreSQL_格來羙、日出的博客-CSDN博客 zlib-1.2.9(不需要) 如果用系统的后面gd…...

【LeetCode】160. 相交链表

160. 相交链表 难度&#xff1a;简单 题目 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中…...

数据集笔记:NGSIM (next generation simulation)

1 数据集介绍 数据介绍s Next Generation Simulation (NGSIM) Open Data (transportation.gov) 数据地址&#xff1a;Next Generation Simulation (NGSIM) Vehicle Trajectories and Supporting Data | Department of Transportation - Data Portal 时间2005年到2006年间地…...

解决docker运行elastic服务端启动不成功

现象&#xff1a; 然后查看docker日志&#xff0c;发现有vm.max_map_count报错 ERROR: [1] bootstrap checks failed [1]: max virtual memory areas vm.max_map_count [65530] is too low, increase to at least [262144] 解决办法&#xff1a; 1. 宿主机&#xff08;运行doc…...

mysql数据库中mysql database 数据被破坏产生的一系列问题

在执行sql脚本时&#xff0c;没有注意到sql脚本文件包含了对mysql 原始数据库的操作&#xff0c;执行了脚本。 脚本执行成功之后&#xff0c;登录或链接数据库查看数据时报错&#xff1a; The user specified as a definer (‘mysql.infoschema’‘localhost’) does not exis…...

基于变形卷积和注意机制的带钢表面缺陷快速检测网络DCAM-Net(论文阅读笔记)

原论文链接->DCAM-Net: A Rapid Detection Network for Strip Steel Surface Defects Based on Deformable Convolution and Attention Mechanism | IEEE Journals & Magazine | IEEE Xplore DCAM-Net: A Rapid Detection Network for Strip Steel Surface Defects Base…...

05-Spring Boot工程中简化开发的方式Lombok和dev-tools

简化开发的方式Lombok和dev-tools Lombok常用注解 Lombok用标签方式代替构造器、getter/setter、toString()等重复代码, 在程序编译的时候自动生成这些代码 注解名功能NoArgsConstructor生成无参构造方法AllArgsConstructor生产含所有属性的有参构造方法,如果不希望含所有属…...

AIGC 技术在淘淘秀场景的探索与实践

本文介绍了AIGC相关领域的爆发式增长&#xff0c;并探讨了淘宝秀秀(AI买家秀)的设计思路和技术方案。文章涵盖了图像生成、仿真形象生成和换背景方案&#xff0c;以及模型流程串联等关键技术。 文章还介绍了淘淘秀的使用流程和遇到的问题及处理方法。最后&#xff0c;文章展望…...

ANSYS网格无关性检查

网格精度对应力结果存在很大的影响&#xff0c;有时候可以发现&#xff0c;随着网格精度逐渐提高&#xff0c;所求得的最大应力值逐渐趋于收敛。 默认网格&#xff1a; 从默认网格下计算出的应力云图可以发现&#xff0c;出现了的三处应力奇异点&#xff0c;此时算出的应力值是…...

设计模式-责任链-笔记

动机&#xff08;Motivation&#xff09; 在软件构建过程中&#xff0c;一个请求可能被多个对象处理&#xff0c;但是每个请求在运行时只能有个接受者&#xff0c;如果显示指定&#xff0c;将必不可少地带来请求者与接受者的紧耦合。 如何使请求的发送者不需要指定具体的接受…...

SpringMvc请求原理流程

springmvc是用户和服务沟通的桥梁&#xff0c;官网提供了springmvc的全面使用和解释&#xff1a;DispatcherServlet :: Spring Framework 流程 1.Tomcat启动 2.解析web.xml文件&#xff0c;根据servlet-class找到DispatcherServlet&#xff0c;根据init-param来获取spring的…...

【开源】基于Vue.js的音乐偏好度推荐系统的设计和实现

项目编号&#xff1a; S 012 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S012&#xff0c;文末获取源码。} 项目编号&#xff1a;S012&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、系统设计2.1 功能模块设计2.1.1 音乐档案模块2.1…...

采集1688整店商品(店铺所有商品、店铺列表api)

返回数据&#xff1a; 请求链接 {"user": [],"items": {"item": [{"num_iid": "738354436678","title": "国产正品i13 promax全网通5G安卓智能手机源头厂家批发手机","pic_url": "http…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

MPNet:旋转机械轻量化故障诊断模型详解python代码复现

目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

全面解析各类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…...