LeetCode-22题:括号生成(原创)
【题目描述】
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 【题目链接】. - 力扣(LeetCode)
【解题代码】
package dp;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class GenerateParenthesis {// 生成的有效括号字符串列表private List<String> result;// StringBuilder变量,用于生成有效括号字符串private StringBuilder sb;// 左括号数量private int count1;// 右括号数量private int count2;public static void main(String[] args) {long start = System.currentTimeMillis();List<String> result = new GenerateParenthesis().generateParenthesis(3);System.out.println("result = " + Arrays.toString(result.toArray()));System.out.println("函数执行时间:" + (System.currentTimeMillis() - start) + "MS");}public List<String> generateParenthesis(int n) {// 初始化各个变量result = new ArrayList<>();sb = new StringBuilder();count1 = 0;count2 = 0;// 有效的括号字符串肯定,第一个肯定是左括号generateParenthesis(n, 0);// 返回最终结果return result;}/*** 生成有效括号字符串* @param n 有效括号组数量* type:当前添加括号的类型,0:左括号,1:右括号**/private void generateParenthesis(int n, int type) {// 当前添加左括号if (type == 0) {sb.append('(');count1++;} else { // 当前添加右括号sb.append(')');count2++;// 右括号数量等于n,说明新的有效括号组完成,添加到结果类表中if (count2 == n) {result.add(sb.toString());return;}}// 先处理左括号,如果左括号数小于n,添加左括号if (count1 < n) {generateParenthesis(n, 0);// 回溯,删除这一层递归函数里添加的左括号,并将左括号数减一sb.deleteCharAt(sb.length() - 1);count1--;}// 再处理右括号,右括号只能数量小于左括号时才能添加if (count2 < count1) {generateParenthesis(n, 1);// 回溯,删除这一层递归函数里添加的左括号,并将左括号数减一sb.deleteCharAt(sb.length() - 1);count2--;}}}
【解题思路】
分析题目,仔细思考得到以下几个思路点:
- 所谓有效括号就是最终的左括号数和右括号数一样;
- 右括号出现时,前面至少有一个左括号能与之匹配,也就是右括号的数量必须小于等于已有的左括号数。
- 此道题目可以按照“回溯递归”的方式进行处理 ,即当前一步添加左括号->然后递归处理下一步->递归回到这一层->然后弹出左括号->然后添加右括号的->然后递归处理下一步。
- 第一步肯定要添加左括号
【解题步骤】
- 首先要给解题类添加几个成员变量:包括最终的结果字符串列表、存储过程字符串的StringBuilder、左右括号的数量等,并在构造函数中进行初始化
// 生成的有效括号字符串列表 private List<String> result; // StringBuilder变量,用于生成有效括号字符串 private StringBuilder sb; // 左括号数量 private int count1; // 右括号数量 private int count2;public GenerateParenthesis(){// 初始化各个变量result = new ArrayList<>();sb = new StringBuilder();count1 = 0;count2 = 0; } - 定义一个“回溯递归”生成有效括号字符串的函数generateParenthesis,传入参数包括有效括号组数量,当前添加括号类型
/*** 生成有效括号字符串* @param n 有效括号组数量* type:当前添加括号的类型,0:左括号,1:右括号**/ private void generateParenthesis(int n, int type) - generateParenthesis函数内部第一步:根据当前要添加括号类型,存储对应的括号字符串并进行计数处理。如果是右括号则判断当前括号组数是否等于n,如果等于则将当前字符串加入结果列表中
// 当前添加左括号 if (type == 0) {sb.append('(');count1++; } else { // 当前添加右括号sb.append(')');count2++;// 右括号数量等于n,说明新的有效括号组完成,添加到结果类表中if (count2 == n) {result.add(sb.toString());return;} } - generateParenthesis函数内部第二步:下一步递归添加左括号,递归完毕后进行回溯
// 先处理左括号,如果左括号数小于n,添加左括号 if (count1 < n) {generateParenthesis(n, 0);// 回溯,删除这一层递归函数里添加的左括号,并将左括号数减一sb.deleteCharAt(sb.length() - 1);count1--; } - generateParenthesis函数内部第二步:下一步递归添加右括号,递归完毕后进行回溯,只有在右括号数量小于左括号的情况下才能添加右括号
// 再处理右括号,右括号只能数量小于左括号时才能添加 if (count2 < count1) {generateParenthesis(n, 1);// 回溯,删除这一层递归函数里添加的左括号,并将左括号数减一 sb.deleteCharAt(sb.length() - 1);count2--; } - 最后主函数generateParenthesis里调用递归函数,从第一个左括号添加开始,最后返回结果列表即可
public List<String> generateParenthesis(int n) {// 有效的括号字符串肯定,第一个肯定是左括号generateParenthesis(n, 0);// 返回最终结果return result; }
【思考总结】
- 掌握“回溯”:回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试;
- 大的算法框架定下来后, 要细心找出业务里面的逻辑关键点,这道理题的关键点就在于“只有在右括号数量小于左括号的情况下才能添加右括号”
- 算法优化里,要掌握所运用语言库的性能最优方式,比如这里字符串处理使用了Java库里面的StringBuilder
- LeetCode解题之前,一定不要看题解,看了就“破功”了!
相关文章:
LeetCode-22题:括号生成(原创)
【题目描述】 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 【题目链接】. - 力扣(LeetCode) 【解题代码】 package dp;import java.util.ArrayList; import java.util.Arrays; im…...
如何应对IT服务交付中的问题?看了本文DevOps就懂了
👨🎓博主简介 🏅云计算领域优质创作者 🏅华为云开发者社区专家博主 🏅阿里云开发者社区专家博主 💊交流社区:运维交流社区 欢迎大家的加入! 🐋 希望大家多多支…...
Ubuntu23.10禁用Wayland
禁用前 编辑custom.conf文件 sudo vim /etc/gdm3/custom.conf 去掉WaylandEnablefalse前的#号 保存退出 重启系统 生效: 成功转换为X11...
Sora: 大型视觉模型背景、技术、局限性和机遇的综述
论文链接:https://arxiv.org/pdf/2402.17177.pdf 背景 在分析 Sora 之前,研究者首先盘点了视觉内容生成技术的沿袭。 在深度学习革命之前,传统的图像生成技术依赖于基于手工创建特征的纹理合成和纹理映射等方法。这些方法在生成复杂而生动…...
比较 2 名无人机驾驶员:借助分析飞得更高
近年来,越来越多的政府和执法机构使用无人机从空中鸟瞰。为了高效执行任务,无人机必须能够快速机动到预定目标。快速机动使它们能够在复杂的环境中航行,并高效地完成任务。成为认证的无人机驾驶员的要求因国家/地区而异,但都要求您…...
Vue开发实例(六)实现左侧菜单导航
左侧菜单导航 一、一级菜单二、二级菜单三、三级菜单1、加入相关事件 四、菜单点击跳转1. 创建新页面2. 配置路由3. 菜单中加入路由配置4、处理默认的Main窗口为空的情况 五、动态左侧菜单导航1、动态实现一级菜单2、动态实现二级菜单 一、一级菜单 在之前的Aside.vue中去实现…...
[嵌入式系统-37]:龙芯1B 开发学习套件 -6-协处理器CP0之CPU异常处理与外部中断控制器的中断处理
目录 一、CP0概述 1.1 CP0概述 1.2 龙芯异常exception与中断interrupt的区别 二、CPU协处理器的异常处理 三、外部中断与外部中断控制器 3.1 外部中断源 3.2 如何配置外部中断源 3.3 外部中断的中断向量表 3.2.1 软件中断向量表结构定义:ls1b_irq.c 3.2.2…...
前端实现一个绕圆心转动的功能
前言: 今天遇到了一个有意思的需求,如何实现一个元素绕某一个点来进行圆周运动,用到了一些初高中的数学知识,实现起来还是挺有趣的,特来分享🎁。 一. 效果展示 我们先展示效果,如下图所示&…...
【vue.js】文档解读【day 2】 | 响应式基础
如果阅读有疑问的话,欢迎评论或私信!! 本人会很热心的阐述自己的想法!谢谢!!! 文章目录 响应式基础声明响应式状态(属性)响应式代理 vs 原始值声明方法深层响应性DOM 更新时机有状态方法 响应式…...
element-ui radio 组件源码分享
今日简单分享 radio 组件的实现原理,主要从以下三个方面来分享: 1、radio 页面结构 2、radio 组件属性 3、radio 组件方法 一、radio 页面结构 1.1 页面结构如下: 二、radio 属性 2.1 value / v-model 属性,类型为 string / …...
1-安装rabbitmq
rabbitmq官网: https://www.rabbitmq.com/docs/download 本机环境:mac,使用orbstack提供的docker 使用docker部署rabbitmq docker run -it --rm --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management 然后报错…...
C/C++编程-理论学习-通信协议理论
通信协议理论 protobuf简述 protobuf 简述 作用: 1. 将结构化数据 序列化 进行信息通信、存储。意为,数据结构化管理;意为,对结构化的数据进行序列化,便于发送、存储。可类比XML、JSON。 弊端: 1. buffe…...
【Apache Camel】基础知识
【Apache Camel】基础知识 Apache Camel是什么Apache Camel基本概念和术语CamelContextEndpointsRoutesRouteBuilderComponentsMessageExchangeProcessorsDomain Specific Language(DSL) Apache Camel 应用执行步骤Apache Camel 示意图参考 Apache Camel…...
Python之访问集合的迭代器
对迭代器的理解对于我们访问数据量大是有很大的帮助,将介绍它。 一、概念 迭代:是访问集合元素的一种方式,按照某种顺序逐个访问集合中的每一项。 可迭代对象:能够被迭代的对象,称为可迭代对象 判定依据:能…...
【Spring连载】使用Spring Data访问 MongoDB----对象映射之基于类型的转换器
【Spring连载】使用Spring Data访问 MongoDB----对象映射之基于类型的转换器 一、自定义转换二、转换器消歧(Disambiguation)三、基于类型的转换器3.1 写转换3.2 读转换3.3 注册转换器 一、自定义转换 下面的Spring Converter实现示例将String对象转换为自定义Email值对象: R…...
在ubuntu上安装hadoop完分布式
准备工作 Xshell安装包 Xftp7安装包 虚拟机安装包 Ubuntu镜像源文件 Hadoop包 Java包 一、安装虚拟机 创建ubuntu系统 完成之后会弹出一个新的窗口 跑完之后会重启一下 按住首先用ctrlaltf3进入命令界面,输入root,密码登录管理员账号 按Esc 然后输入 …...
Python 语句(二)【循环语句】
循环语句允许执行一个语句或语句组多次,其程序流程图如下: 在python中有三种循环方式: while 循环 当判断条件为 true 时执行循环体,否则退出循环体。for 循环 重复执行语句嵌套循环 (在while循环体中嵌套for循环&…...
(3)(3.3) MAVLink高延迟协议
文章目录 前言 1 配置 2 说明 3 消息说明 前言 ArduPilot 支持 MAVLink 高延迟协议(MAVLink High Latency)。该协议专为卫星或 LoRA 等低带宽或高成本链路而设计。 在此协议中,每 5s 只发送一次 HIGH_LATENCY2 MAVLink 信息。对 MAVLink 命令或请求(…...
【异常处理】Vue报错 Component template should contain exactly one root element.
问题描述 启动VUE项目后控制台报错: Component template should contain exactly one root element. If you are using v-if on multiple elements, use v-else-if to chain them instead.翻译为:组件模板应该只包含一个根元素 查看vue代码࿰…...
Eth-trunk隧道
目录 Eth-trunk (划为二层) 二层trunk 三层交换机 网关冗余 Eth-trunk (划为二层) 一,...
Spring Authorization Server Redis缓存优化:构建高性能分布式授权服务的架构设计与性能调优指南
Spring Authorization Server Redis缓存优化:构建高性能分布式授权服务的架构设计与性能调优指南 【免费下载链接】spring-authorization-server Spring Authorization Server 项目地址: https://gitcode.com/gh_mirrors/sp/spring-authorization-server 在现…...
掌握通达信数据接口:量化分析从入门到精通
掌握通达信数据接口:量化分析从入门到精通 【免费下载链接】mootdx 通达信数据读取的一个简便使用封装 项目地址: https://gitcode.com/GitHub_Trending/mo/mootdx 解决量化数据获取难题:MOOTDX的技术方案与实战应用 如何突破量化分析的数据获取…...
[Android S] 深入解析statsd的log统计机制与实现
1. 认识Android系统中的statsd statsd是Android系统中一个非常重要的后台服务,它的主要职责是收集系统和应用的各类统计信息。你可能不知道,每次你在Android设备上执行操作时,statsd都在默默记录着各种数据。这些数据对于系统优化、性能分析和…...
MIKE21桥墩模拟避坑指南:从‘默认糙率倒置’到‘软启动设置’的完整配置流程
MIKE21桥墩模拟避坑指南:从糙率倒置到软启动的实战精要 当第一次打开MIKE21的桥墩模拟模块时,大多数工程师都会面临三个灵魂拷问:为什么输入的糙率值比教科书大几十倍?软启动参数究竟该设多长?桥墩断面分段数对结果影响…...
YALMIP求解器报错看不懂?从verbose到debug,教你快速定位并解决优化问题
YALMIP求解器报错看不懂?从verbose到debug,教你快速定位并解决优化问题 当你满怀期待地运行YALMIP优化代码,却看到命令行突然跳出一片红色报错信息时,那种挫败感每个优化工程师都深有体会。"No feasible solution found"…...
从草图到文档:我用这5个Miro/PlantUML模板,高效搞定团队架构设计评审
从草图到文档:5个高效架构设计模板与团队协作实战指南 在敏捷开发环境中,架构设计往往陷入两难困境——既要快速响应需求变化,又要保证设计文档的准确性与可维护性。Tech Lead们经常面临这样的场景:在白板前与团队激情讨论出的架构…...
2026 国内源码网站 TOP10:高速稳定 + 中文友好,开发者收藏版
对于国内开发者、站长、学生与创业团队来说,稳定高速、全中文、资源靠谱、无冗余广告的源码平台,能大幅降低开发成本、提升项目落地效率。2026 年实测筛选出国内综合体验 TOP10 源码站点,兼顾免费学习、商用部署、快速建站等场景,…...
爱毕业aibye智能改写工具推荐五个方法,30%重复率的论文快速达标不是问题
嘿,大家好!我是AI菌。今天咱们来聊聊一个让无数学生头疼的问题:论文重复率飙到30%以上怎么办?别慌,我这就分享5个实用降重技巧,帮你一次搞定,轻松压到合格线以下。这些方法都是我亲身试验过的&a…...
嵌入式系统命令模式实现撤销功能
嵌入式误操作救星:基于命令模式的撤销方案设计与实现1. 项目概述在嵌入式系统开发中,配置参数管理是一个常见但容易出错的场景。当用户误操作导致重要配置被重置时,如何快速恢复到之前的状态成为系统设计的关键需求。本文介绍一种基于命令模式…...
Cadence Virtuoso新手避坑:DC和Tran仿真到底该用哪个?附inv反相器实例
Cadence Virtuoso仿真实战:DC与Tran仿真的本质差异与工程选择指南 在集成电路设计的入门阶段,许多工程师都会对仿真类型的选择感到困惑。就像我第一次使用Cadence Virtuoso时,面对DC和Tran这两个基础仿真选项,完全不知道从何下手。…...
