代码随想录算法训练营第二十九天| 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(×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中进行判断,如果path的长度大于1,则将其添加到res中。 本题nums中的元素的值处于-100与100之间,可以将元素映射0到199之间并且通过布尔数组st来记录此层中元素是否被使用过,…...
(动手学习深度学习)第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在内存中总是会增长;它不会收缩。因此,如果map导致了一些内存问题,你可以尝试不同的选项,比如强制 Go 重新创建map或使用指针。 在 Go 中使用map时,我们需要了解map增长和收缩的一些重要特性。让我们深入探讨这一点…...
前缀和(c++,超详细,含二维)
前缀和与差分 当给定一段整数序列a1,a2,a3,a4,a5…an; 每次让我们求一段区间的和,正常做法是for循环遍历区间起始点到结束点,进行求和计算,但是当询问次数很多并且区间很长的时候 比如,10^5 个询问和10^6区间长度,相…...
详解FreeRTOS:二值信号量和计数信号量(高级篇—2)
目录 1、二值信号量 1.1、二值信号量运行机制 1.2、创建二值信号量 1...
持续集成交付CICD:Jenkins通过API触发流水线
目录 一、理论 1.HTTP请求 2.调用接口的方法 3.HTTP常见错误码 二、实验 1.Jenkins通过API触发流水线 三、问题 1.如何拿到上一次jenkinsfile文件进行自动触发流水线 一、理论 1.HTTP请求 (1)概念 HTTP超文本传输协议,是确保服务器…...
【Python】12 GPflow安装
概述 GPflow 是一个基于TensorFlow 在 Python 中构建高斯过程模型的包。高斯过程是一种监督学习模型。 高斯过程的一些优点是: 不确定性是高斯过程的固有部分。高斯过程可以在不知道答案时告诉您。适用于小型数据集。如果您的数据有限,高斯过程可以从…...
Ubuntu源码编译gdal3.6.2
在华为云申请了一台Ubuntu v18的机器,乱七八糟的不要装。 apt install build-essential pkg-config -y cmake-3.21.1 apt-get install openssl libssl-dev 过程参考:Yukon for PostgreSQL_格來羙、日出的博客-CSDN博客 zlib-1.2.9(不需要) 如果用系统的后面gd…...
【LeetCode】160. 相交链表
160. 相交链表 难度:简单 题目 给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中…...
数据集笔记:NGSIM (next generation simulation)
1 数据集介绍 数据介绍s Next Generation Simulation (NGSIM) Open Data (transportation.gov) 数据地址:Next Generation Simulation (NGSIM) Vehicle Trajectories and Supporting Data | Department of Transportation - Data Portal 时间2005年到2006年间地…...
解决docker运行elastic服务端启动不成功
现象: 然后查看docker日志,发现有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] 解决办法: 1. 宿主机(运行doc…...
mysql数据库中mysql database 数据被破坏产生的一系列问题
在执行sql脚本时,没有注意到sql脚本文件包含了对mysql 原始数据库的操作,执行了脚本。 脚本执行成功之后,登录或链接数据库查看数据时报错: 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相关领域的爆发式增长,并探讨了淘宝秀秀(AI买家秀)的设计思路和技术方案。文章涵盖了图像生成、仿真形象生成和换背景方案,以及模型流程串联等关键技术。 文章还介绍了淘淘秀的使用流程和遇到的问题及处理方法。最后,文章展望…...
ANSYS网格无关性检查
网格精度对应力结果存在很大的影响,有时候可以发现,随着网格精度逐渐提高,所求得的最大应力值逐渐趋于收敛。 默认网格: 从默认网格下计算出的应力云图可以发现,出现了的三处应力奇异点,此时算出的应力值是…...
设计模式-责任链-笔记
动机(Motivation) 在软件构建过程中,一个请求可能被多个对象处理,但是每个请求在运行时只能有个接受者,如果显示指定,将必不可少地带来请求者与接受者的紧耦合。 如何使请求的发送者不需要指定具体的接受…...
SpringMvc请求原理流程
springmvc是用户和服务沟通的桥梁,官网提供了springmvc的全面使用和解释:DispatcherServlet :: Spring Framework 流程 1.Tomcat启动 2.解析web.xml文件,根据servlet-class找到DispatcherServlet,根据init-param来获取spring的…...
【开源】基于Vue.js的音乐偏好度推荐系统的设计和实现
项目编号: S 012 ,文末获取源码。 \color{red}{项目编号:S012,文末获取源码。} 项目编号:S012,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、系统设计2.1 功能模块设计2.1.1 音乐档案模块2.1…...
采集1688整店商品(店铺所有商品、店铺列表api)
返回数据: 请求链接 {"user": [],"items": {"item": [{"num_iid": "738354436678","title": "国产正品i13 promax全网通5G安卓智能手机源头厂家批发手机","pic_url": "http…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
C++:多态机制详解
目录 一. 多态的概念 1.静态多态(编译时多态) 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1).协变 2).析构函数的重写 5.override 和 final关键字 1&#…...
解决:Android studio 编译后报错\app\src\main\cpp\CMakeLists.txt‘ to exist
现象: android studio报错: [CXX1409] D:\GitLab\xxxxx\app.cxx\Debug\3f3w4y1i\arm64-v8a\android_gradle_build.json : expected buildFiles file ‘D:\GitLab\xxxxx\app\src\main\cpp\CMakeLists.txt’ to exist 解决: 不要动CMakeLists.…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
数据库——redis
一、Redis 介绍 1. 概述 Redis(Remote Dictionary Server)是一个开源的、高性能的内存键值数据库系统,具有以下核心特点: 内存存储架构:数据主要存储在内存中,提供微秒级的读写响应 多数据结构支持&…...
