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", &…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
从零实现STL哈希容器:unordered_map/unordered_set封装详解
本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说,直接开始吧! 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析
Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么?它的作用是什么? Spring框架的核心容器是IoC(控制反转)容器。它的主要作用是管理对…...
EasyRTC音视频实时通话功能在WebRTC与智能硬件整合中的应用与优势
一、WebRTC与智能硬件整合趋势 随着物联网和实时通信需求的爆发式增长,WebRTC作为开源实时通信技术,为浏览器与移动应用提供免插件的音视频通信能力,在智能硬件领域的融合应用已成必然趋势。智能硬件不再局限于单一功能,对实时…...
