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 (划为二层) 一,...
ESP32 FreeRTOS任务状态全解析:从就绪态到挂起态的深度理解与应用
ESP32 FreeRTOS任务状态全解析:从就绪态到挂起态的深度理解与应用 在嵌入式系统开发中,任务调度是实时操作系统(RTOS)的核心功能之一。对于ESP32开发者而言,深入理解FreeRTOS的任务状态模型,能够帮助我们编写出更高效、更可靠的多…...
OpenClaw二次开发指南:修改Qwen3-VL:30B的飞书交互协议
OpenClaw二次开发指南:修改Qwen3-VL:30B的飞书交互协议 1. 为什么需要定制飞书交互协议 去年11月第一次尝试用OpenClaw对接飞书时,我遇到了一个典型问题:标准协议下发送的Markdown消息在Qwen3-VL:30B多轮对话中频繁出现格式错乱。这个30B参…...
DeepSeek-R1-Distill-Qwen-7B效果展示:复杂问题推理实测
DeepSeek-R1-Distill-Qwen-7B效果展示:复杂问题推理实测 1. 模型能力概览 DeepSeek-R1-Distill-Qwen-7B是DeepSeek团队基于Qwen架构开发的7B参数推理模型,通过强化学习训练和知识蒸馏技术优化,在数学推理、代码生成和逻辑分析任务上展现出卓…...
Lattice Diamond 3.11安装到实战:一个FPGA小白的避坑血泪史(附完整问题清单)
Lattice Diamond 3.11安装到实战:一个FPGA小白的避坑血泪史(附完整问题清单) 如果你正准备踏入Lattice FPGA的世界,手里攥着Diamond 3.11安装包,既兴奋又忐忑——这篇文章就是为你准备的。作为过来人,我深知…...
掌握BepInEx:Unity游戏扩展全家桶的零门槛实践指南
掌握BepInEx:Unity游戏扩展全家桶的零门槛实践指南 【免费下载链接】BepInEx Unity / XNA game patcher and plugin framework 项目地址: https://gitcode.com/GitHub_Trending/be/BepInEx 🔍 游戏模组管理的行业痛点与解决方案 在Unity游戏生态…...
云效Codeup代码评审功能深度体验:如何用它提升团队代码质量(附真实项目案例)
云效Codeup代码评审实战指南:从规范制定到CI/CD集成 在当今快节奏的软件开发环境中,代码质量直接决定了产品的稳定性和可维护性。作为技术负责人,我经历过无数次因代码质量问题导致的深夜加班和紧急修复。直到团队开始系统化使用云效Codeup的…...
OpenClaw备份恢复:Qwen3-VL:30B飞书配置迁移指南
OpenClaw备份恢复:Qwen3-VL:30B飞书配置迁移指南 1. 为什么需要备份恢复OpenClaw配置 上周我的主力开发机突然硬盘故障,导致所有数据丢失。最让我头疼的不是代码仓库——它们都有远程备份,而是那套精心调校的OpenClaw飞书助手配置。这个助手…...
HarmonyOS开发入门:DevEco Studio工程目录结构详解与实战配置
HarmonyOS开发实战:深度解析DevEco Studio工程架构与高效配置策略 当你第一次在DevEco Studio中创建HarmonyOS项目时,是否曾被复杂的目录结构弄得一头雾水?作为华为全场景智能生态的核心开发工具,DevEco Studio采用了一套精心设计…...
别再手动改MTL文件了!一个Python脚本搞定ENVI打开Landsat 8/9 L2影像的报错问题
用Python自动化修复Landsat L2影像的ENVI兼容性问题 遥感数据处理中,Landsat 8/9的L2级别影像在ENVI软件中打开时经常遇到兼容性问题。传统的手动修改MTL文件方法不仅效率低下,还容易出错。本文将介绍一个Python自动化解决方案,帮助您彻底摆脱…...
OFA-Image-Caption赋能Android应用:移动端图像智能描述实战
OFA-Image-Caption赋能Android应用:移动端图像智能描述实战 你有没有想过,手机拍下一张照片,它就能立刻告诉你照片里有什么?对于视障朋友来说,这不仅仅是便利,更是打开世界的一扇窗。而对于内容平台&#…...
