leetcode 46. Permutations(排列)

返回数组nums中数字的所有可能的排列组合。
思路:
排列组合这种一般会想到DFS。
这个排列中每个数字只能用一次,
可用如下DFS流程
stack.push(num);
dfs(nums, num);
stack.pop();
退出条件:
当stack的size和nums数组一样时,说明已经完成了一个排列组合,保存结果退出当前dfs。
否则遍历数组,进入新一轮dfs.
每个数字只能用一次,所以用一个visited数组记录数字是否已经使用过。
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {Stack<Integer> st = new Stack<>();boolean[] visited = new boolean[nums.length];dfs(nums, st, visited);return res;}void dfs(int[] nums, Stack<Integer> st, boolean[] visited){if(st.size() == nums.length) {List<Integer> list = new ArrayList<>(st);res.add(list);return;}//combinationfor(int i = 0; i < nums.length; i++) {if(visited[i]) continue;st.push(nums[i]);visited[i] = true;dfs(nums, st, visited);st.pop();visited[i] = false;}}
}
也可以不用stack. 直接在nums数组上模拟stack.
把需要装入stack的数字交换到前面,用一个指针模拟栈顶。
此方法更快。
class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> permute(int[] nums) {solve(nums, 0);return res;}void solve(int[] nums, int start){if(start == nums.length-1) {List<Integer> list = new ArrayList<>();for(int num : nums) list.add(num);res.add(list);return;}//combinationfor(int i = start; i < nums.length; i++) {swap(nums, start, i);solve(nums, start+1);swap(nums, start, i);}}void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}
相关文章:
leetcode 46. Permutations(排列)
返回数组nums中数字的所有可能的排列组合。 思路: 排列组合这种一般会想到DFS。 这个排列中每个数字只能用一次, 可用如下DFS流程 stack.push(num); dfs(nums, num); stack.pop();退出条件: 当stack的size和nums数组一样时,说…...
5、二叉树
二叉树遍历 递归序 public static void f(Node head) {if (head == null) {return;}f(head.left);f(head.right); }前中后遍历_递归 public static void preOrderRecur(Node head) {if (head == null) {return;}System.out.print(head.value + " ");preOrderRecur…...
Doris比MySQL快的原因
简介 在数据存储和数据分析领域,MySQL和Doris是比较流行的数据库管理系统的代表。 在如今的大数据时代,数据量和数据分析的速度是很重要的。 在数据分析和数据处理中,Doris比MySQL快,这个问题一直是许多人关心的问题。 Doris的数…...
Prometheus + Grafana安装
Prometheus是一款基于时序数据库的开源监控告警系统,非常适合Kubernetes集群的监控。Prometheus的基本原理是通过HTTP协议周期性抓取被监控组件的状态,任意组件只要提供对应的HTTP接口就可以接入监控。不需要任何SDK或者其他的集成过程。这样做非常适合做…...
二十三种设计模式第二十一篇--解释器模式
解释器模式(Interpreter Pattern)是一种行为设计模式,它用于定义一种语言的语法结构和解释器,使得可以解释并执行特定的语法规则。该模式可以将复杂的语言表达式分解为更小的语法单元,并定义其解释过程。 解释器模式的…...
PHP8的数据类型转换-PHP8知识详解
什么是数据类型转换? 答:数据从一个类型转换成另外一个类型,就是数据类型转换。 在PHP8中,变量的类型就是由赋值决定的,也就是说,如果 string 赋值给 $var,然后 $var 的类型就是 string。之后…...
2023 电赛 E 题 K210 方案
第一章:K210 介绍 K210芯片是一款基于RISC-V架构的嵌入式人工智能芯片,具备低功耗、高性能的特点。它拥有强大的图像处理和机器学习能力,适用于边缘计算设备和物联网应用。为了方便开发者,K210芯片提供了丰富的外设接口ÿ…...
Python的正则表达式re模块的compile()方法有什么作用?
re模块是Python标准库中的正则表达式模块,它提供了对正则表达式的支持。re.compile()是re模块的一个方法,用于将正则表达式编译成可复用的正则对象。 正则表达式是用来匹配和处理文本模式的强大工具。当你需要在字符串中查找、替换或者提取符合特定模式…...
SQL 语句中 left join 后用 on 还是 where,区别大了!
目录 情况 小结 举例 情况 前天写SQL时本想通过 A left B join on and 后面的条件来使查出的两条记录变成一条,奈何发现还是有两条。 后来发现 join on and 不会过滤结果记录条数,只会根据and后的条件是否显示 B表的记录,A表的记录一定会显…...
uni-app 微信小程序自定义导航栏
一、效果图 二、导航栏的组成 上面的导航栏主要由状态栏(就是手机电量显示栏)和小程序的导航栏组成,android手机一般为48px,ios手机一般为44px 三、开发步骤 1、设置navigationStyle:custom {"path": "pages/v…...
电缆故障检测仪技术参数
一、电缆故障测试仪的技术参数 1.采样方法:低压脉冲法、冲击闪络法、速度测量法 2.电缆长度:50m、300m、1km、2km、5km、10km、30km、60km 3.波速设置:交联乙烯、聚氯乙烯、油浸纸、不滴油和未知类型自设定 4.冲击高压:35kV及以下…...
固定资产管理软件
固定资产全生命周期管理软件采用先进的RFID技术,从采购、入库、借用、总结、清理到损坏等方面准确统计资产,突破过去手工统计的复杂性,节省资产资源,减少调查时间,确保资产管理工作的准确性和快速性。 固定资产管理软…...
云安全攻防(四)之 云原生技术
云原生技术 容器技术 容器与虚拟化 虚拟化(Virtualization)和容器(Container)都是系统虚拟化的实现技术,可实现系统资源的”一虚多“共享。容器技术可以理解成一种”轻量的虚拟化“方式,此处的”轻量“主…...
线上通过Nginx部署前端工程,并且配置SSL
介绍、为了更好的帮助大家学习,减少歧义,IP地址我就不隐藏了,公司也是我自己的公司。你们就别来攻击了。 下面给出步骤: 一、前期准备工作 通过在目标服务器上安装宝塔面板、安装redis、mysql、nginx、jdk环境等 1、 2、前端工程通过npm run build 打…...
直播预告 | 开源运维工具使用现状以及可持续产品的思考
运维平台自上世纪90年代开始进入中国市场,曾形成以传统四大外企:IBM、BMC、CA、HP为代表的头部厂商,还有一众从网管起家的国内厂商。2010年前后,出现了以Zabbix、Nagios、Cacti为代表的开源工具,后来又陆续出现了Prome…...
GPT带我学-设计模式-工厂模式
1 你好,请问你知道设计模式的工厂模式吗 当然知道,工厂模式是一种创建型设计模式,它提供了一种创建对象的方式,而不需要暴露对象创建的逻辑细节。工厂模式通过使用工厂类来创建对象,从而将对象的实例化逻辑与客户端代…...
Docker 安装 Tomcat
目录 一、查看 tomcat 版本 二、拉取 Tomcat Docker 镜像 三、创建 Tomcat 容器 四、访问 Tomcat 五、停止和启动容器 一、查看 tomcat 版本 访问 tomcat 镜像库地址:https://hub.docker.com/_/tomcat,可以通过 Tags 查看其他版本的 tomcat; 二、拉…...
seata注册到nacos(docker)
1、安装:docker run --name seata-server2 -p 8091:8091 -p 7091:7091 seataio/seata-server:1.5.1 复制seata-server2到服务器,然后过河拆桥 2、创建挂载目录 mkdir -p /ssy/seata_docker 3、将容器 resources文件挂载到宿主机 docker cp seata-server2…...
ffmpeg综合应用示例(五)——多路视频合并(Linux版本)
本文的目的为方便Linux下编译运行多路视频合成Demo 原文:ffmpeg综合应用示例(五)——多路视频合并 Ubuntu 20.04 ffmpeg version ffmpeg-4.4-x86_64 编译 export LD_LIBRARY_PATH$LD_LIBRARY_PATH:/home/workspace/dengzr/linux-x64/lib…...
Node.js-http模块服务端请求与响应操作,请求报文与响应报文
简单案例创建HTTP服务端: // 导入 http 模块 const http require("http"); // 创建服务对象 const server http.createServer((request, response) > {// 设置编码格式,解决中文乱码问题response.setHeader("content-type", &…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
解锁数据库简洁之道:FastAPI与SQLModel实战指南
在构建现代Web应用程序时,与数据库的交互无疑是核心环节。虽然传统的数据库操作方式(如直接编写SQL语句与psycopg2交互)赋予了我们精细的控制权,但在面对日益复杂的业务逻辑和快速迭代的需求时,这种方式的开发效率和可…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
