Java中等题-括号生成(力扣)
数字 n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1 输出:["()"]
这道题我没有思路,我直接看的力扣官方的解题思路
回溯法:
class Solution {public List<String> generateParenthesis(int n) {List<String> ans=new ArrayList<>();StringBuilder str=new StringBuilder();int start=0;int end=0;generateTree(ans,str,start,end,n);return ans;}public static void generateTree(List<String> ans,StringBuilder str,int start,int end,int n){if (str.length()==n*2) {ans.add(String.valueOf(str));return;}if(start<n){str.append('(');generateTree(ans,str,start+1,end,n);str.deleteCharAt(str.length()-1);}if(end<start){str.append(')');generateTree(ans,str,start,end+1,n);str.deleteCharAt(str.length()-1);}}
}
让AI来为我们详细解释一下:
class Solution { // 公开方法,用于生成所有可能的括号组合 public List<String> generateParenthesis(int n) { List<String> ans = new ArrayList<>(); StringBuilder str = new StringBuilder(); // 创建一个StringBuilder对象,用于构建当前的括号组合 // 通常我们会用两个计数器来跟踪左括号和右括号的数量 generateTree(ans, str, 0, 0, n); // 调用递归方法开始生成括号组合,start和end初始都为0 return ans; // 返回包含所有括号组合的列表 } // 静态递归方法,用于生成括号组合 // ans: 存储所有有效组合的列表 // str: 当前正在构建的括号组合 // start: 表示已添加的左括号数量 // end: 表示已添加的右括号数量 // n: 需要生成的括号对数 public static void generateTree(List<String> ans, StringBuilder str, int start, int end, int n) { if (str.length() == n * 2) { // 如果当前组合的长度等于2n,说明已经生成了一个完整的括号组合 ans.add(String.valueOf(str)); return; } if (start < n) { // 如果还可以添加左括号(即已添加的左括号数量小于n) str.append('('); // 向当前组合中添加一个左括号 generateTree(ans, str, start + 1, end, n); // 递归调用,尝试添加下一个字符str.deleteCharAt(str.length() - 1); // 回溯,撤销上一步添加的左括号 } if (end < start) { // 如果还可以添加右括号(即已添加的右括号数量小于已添加的左括号数量) str.append(')'); // 向当前组合中添加一个右括号 generateTree(ans, str, start, end + 1, n); // 递归调用,尝试添加下一个字符str.deleteCharAt(str.length() - 1); // 回溯,撤销上一步添加的右括号 } }
}
第一个 if
循环(添加左括号)
当 open < max
时,算法会尝试添加一个左括号到当前的括号组合中(cur.append('(');
)。然后,它递归地调用自己(backtrack(...)
),在添加了左括号的基础上继续生成括号组合。递归调用返回后,算法需要撤销刚才添加的左括号,以便在当前的 open
计数下尝试添加右括号或其他可能的操作。这就是 cur.deleteCharAt(cur.length() - 1);
在第一个 if
循环之后的作用。
第二个 if
循环(添加右括号)
当 close < open
时,算法会尝试添加一个右括号到当前的括号组合中(cur.append(')');
)。与添加左括号的情况类似,它也递归地调用自己,在添加了右括号的基础上继续生成括号组合。递归调用返回后,同样需要撤销刚才添加的右括号,以便在当前的状态下尝试其他可能的操作(比如继续添加右括号,或者在添加更多左括号之后再次尝试添加右括号)。因此,cur.deleteCharAt(cur.length() - 1);
也被用在了第二个 if
循环之后。
总结
cur.deleteCharAt(cur.length() - 1);
的使用是回溯算法的一个典型特征。它允许算法在尝试了一条路径之后,能够撤销上一步的操作,并回到之前的状态,以便尝试其他可能的路径。在生成括号组合的问题中,这确保了算法能够系统地探索所有可能的括号组合,而不会陷入无限循环或错过任何有效的组合。
相关文章:
Java中等题-括号生成(力扣)
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((()))","(()())","(())()","()(())","()()(…...

Flink 实时数仓(八)【DWS 层搭建(二)流量域、用户域、交易域搭建】
前言 今天的任务是完成流量域最后一个需求、用户域的两个需求以及交易域的部分需求; 1、流量域页面浏览各窗口汇总表 任务:从 Kafka 页面日志主题读取数据,统计当日的首页和商品详情页独立访客数。 注意:一般我们谈到访客&…...

gitlab-runner /var/run/docker.sock connect permission denied
usermod -aG docker gitlab-runner sudo service docker restart参考:https://gitlab.com/gitlab-org/gitlab-runner/-/issues/3492...

网络安全 - 应急响应检查表
前言 本项目旨在为应急响应提供全方位辅助,以便快速解决问题。结合自身经验和网络资料,形成检查清单,期待大家提供更多技巧,共同完善本项目。愿大家在应急之路一帆风顺。 图片皆来源于网络,如有侵权请联系删除。 一…...
AD常用PCB设计规则介绍 (详细版)
AD09常用PCB设计规则介绍 电气设计规则用来设置在电路板布线过程中所遵循的电气方面的规则,包括安全间距、短路、未布线网络和未连接引脚这四个方面的规则: (1)、安全间距规则(clearance) 该规则用于设定在PCB设计中࿰…...
mysql主从服务配置
主从MySQL服务器 [rootlocalhost ~]# yum -y install ntpdate [rootlocalhost ~]# ntpdate cn.ntp.org.cn [rootlocalhost ~]# yum -y install rsync [rootlocalhost ~]# vim mysql.sh #!/bin/bash yum list installed |grep libaio if [ $? ne 0 ]; then yum -y install…...

Redis基础总结、持久化、主从复制、哨兵模式、内存淘汰策略、缓存
文章目录 Redis 基础Redis 是什么,有哪些特点为什么要使用 Redis 而不仅仅依赖 MySQLRedis 是单线程吗Redis 单线程为什么还这么快 Redis 数据类型和数据结构五种基本数据结构及应用场景其他数据类型Redis 底层数据结构 Redis 持久化数据不丢失的实现AOF 日志RDB 快…...
Java与Python优劣势对比:具体例子与深入分析
在软件开发的世界里,Java和Python是两座不可忽视的高峰。它们各自拥有独特的优势和应用场景,为开发者提供了多样化的选择。本文将通过具体例子,深入分析Java和Python在不同方面的表现,以期为读者提供更为详尽的参考。 1. 语法简洁…...
C++内存泄漏介绍
C内存泄漏(Memory Leak)是指程序在运行过程中,动态分配的内存没有被适当地释放或回收,导致这部分内存始终被占用,无法再被程序或其他程序使用。这种情况通常发生在使用了new或malloc等函数动态分配内存后,忘…...

C++分析红黑树
目录 红黑树介绍 红黑树的性质与平衡控制关系 红黑树节点的插入 情况1:不需要调整 情况2:uncle节点为红色 情况3:uncle节点为黑色 总结与代码实现 红黑树的删除(待实现) 红黑树的效率 红黑树介绍 红黑树是第二种平衡二…...
mysql线上查询之前要性能调优
查询优化是数据库性能调优的关键方面,目的是减少查询的执行时间和资源消耗。以下是一些常见的查询优化技巧及其示例: 使用合适的索引 问题: 全表扫描导致查询缓慢优化: 为经常用于搜索条件的列添加索引示例: 假设有一…...

GPIO输出控制之LED闪烁、LED流水灯以及蜂鸣器应用案例
系列文章目录 STM32之GPIO(General Purpose Input/Output,通用型输入输出) 文章目录 系列文章目录前言一、LED和蜂鸣器简介1.1 LED1.2 蜂鸣器1.3 面包板 二、LED硬件电路2.1 低电平驱动电路2.2 高电平驱动电路 三、蜂鸣器硬件电路3.1 PNP型三…...

体系结构论文导读(三十四):Design of Reliable DNN Accelerator with Un-reliable ReRAM
文章核心 这篇文章主要讨论了一种在不可靠的ReRAM(阻变存储器)设备上设计可靠的深度神经网络(DNN)加速器的方法。文章提出了两种关键技术来解决ReRAM固有的不可靠性问题:动态定点(DFP)数据表示…...
WebStock会话
其实使用消息队列也可以实现会话,直接前端监听指定的队列,使用rabbitmq的分组还可以实现不同群聊的效果。 1、依赖搭建: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org…...

5_现有网络模型的使用
教程:现有网络模型的使用及修改_哔哩哔哩_bilibili 官方网址:https://pytorch.org/vision/stable/models.html#classification 初识网络模型 pytorch为我们提供了许多已经构造好的网络模型,我们只要将它们加载进来,就可以直接使…...

软件安全测试报告内容和作用简析,软件测试服务供应商推荐
在数字化时代,软件安全问题愈发凸显,安全测试显得尤为重要。软件安全测试报告是对软件系统在安全性方面进行评估和分析后的书面文件。该报告通常包含测试过程、测试发现、漏洞描述、风险评估及改进建议等重要信息。报告的目的是为了帮助开发团队及时发现…...

算法板子:树形DP、树的DFS——树的重心
思想: 代码: #include <iostream> #include <cstring> using namespace std;const int N 1e5 10;// vis标记当前节点是否被访问过; vis[1]true代表编号为1的节点被访问过 bool vis[N]; // h数组为邻接表; h数组上的每个坑位都串了一个单链…...
在C语言中,联合体或共用体(union )是一种特殊的数据类型,允许在相同的内存位置存储不同的数据类型。
在C语言中,union 是一种特殊的数据类型,允许在相同的内存位置存储不同的数据类型。这意味着 union 中的所有成员共享同一块内存空间,因此它们之间会相互覆盖。在你给出的 Acceleration_type union 定义中,包含了三种不同类型的成员…...

MS2201以太网收发电路
MS2201 是吉比特以太网收发器电路,可以实现超高速度的 全双工数据传输。它的通信遵从 IEEE 802.3 Gigabit Ethernet 协议 中的 10 比特接口的时序要求协议。 MS2201 支持数据传输速率从 1Gbps 到 1.85Gbps 。 主要特点 ◼ 电源电压: 2.5V 、 3.3V …...

乐乐音乐Kotlin版
简介 乐乐音乐Kotlin版,主要是基于ExoPlayer框架开发的Android音乐播放器,它支持lrc歌词和动感歌词(ksc歌词、krc歌词、trc歌词、zrce歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 编译环境 Android Studio Jellyfish | …...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...

Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
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…...

技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会
在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...
Kafka主题运维全指南:从基础配置到故障处理
#作者:张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1:主题删除失败。常见错误2:__consumer_offsets占用太多的磁盘。 主题日常管理 …...
用鸿蒙HarmonyOS5实现中国象棋小游戏的过程
下面是一个基于鸿蒙OS (HarmonyOS) 的中国象棋小游戏的实现代码。这个实现使用Java语言和鸿蒙的Ability框架。 1. 项目结构 /src/main/java/com/example/chinesechess/├── MainAbilitySlice.java // 主界面逻辑├── ChessView.java // 游戏视图和逻辑├──…...