当前位置: 首页 > news >正文

LeetCode100之括号生成(22)--Java

1.问题描述

        数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

        示例1

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

        示例2 

输入:n = 1
输出:["()"]

        提示

  • 1 <= n <= 8

        难度等级

        中等

        题目链接

        生成括号

2.解题思路

        这道题要我们求出指定括号对数所能满足的所有可能,想法很简单,把这个过程分成无数的添加左括号和右括号的小步,每一次添加之后,判断是否是合法的括号形式,是的话就继续,不是的话就撤销回退,因为我们要穷举所有的可能,所以在每一步真正执行完成之后,都要把当前这一步撤销回退(回溯)。

        这里,我们直接来看核心的递归函数是如何实现的。

        首先,我们要确定递归的结束条件。如果左括号的个数大于n,或者右括号的个数大于左括号的个数,那么情况的括号形式是非法的,递归结束,不做任何操作。如果右括号的个数等于n,说明我们找到了一种符合题意的情况,将当前这种情况加入到存储结果的List集合中,然后递归结束。

        //如果左括号数大于n、右括号数大于左括号数,直接返回if(leftSum > n || rightSum > leftSum){return;}//如果右括号个数等于n,递归结束if(rightSum == n){//将当前情况添加到data中data.add(sb.toString());//返回return;}

        接着,我们要来确定递归的结束条件。我们需要传入题目给的括号对数n,当前左括号的个数和当前右括号的个数,以及用来存储合法可能的List集合,由于每一种可能的情况都是一个字符串,这意味着我们要不断的对字符串进行增删操作,所以这里我们可以传入一个StringBuilder来提高字符串操作的效率。

public void backtrack(int n,int leftSum,int rightSum,List<String> data,StringBuilder sb)

        然后,我们就可以来确定单层的递归逻辑了。其实很简单,在当前情况的基础上,添加左括号,然后递归调用当前方法,同时左括号个数+1,获取当前情况基础上所有的可能情况,获取到所有可能情况之后,将左括号从当前情况的字符串中移除(撤销回滚)。右括号的步骤和上述差不多,我就不多赘述了。

        //单层递归逻辑//添加左括号sb.append('(');backtrack(n,leftSum+1,rightSum,data,sb);sb.delete(sb.length()-1,sb.length());//添加右括号sb.append(')');backtrack(n,leftSum,rightSum+1,data,sb);sb.delete(sb.length()-1,sb.length());

        最后,只需要在主方法中调用我们上面实现的函数并将答案返回即可。

    public List<String> generateParenthesis(int n) {//存储结果的ListList<String> data = new ArrayList<>();//递归函数获取生成括号的对数backtrack(n,0,0,data,new StringBuilder());//返回最终答案return data;}

3.代码展示

class Solution {public List<String> generateParenthesis(int n) {//存储结果的ListList<String> data = new ArrayList<>();//递归函数获取生成括号的对数backtrack(n,0,0,data,new StringBuilder());//返回最终答案return data;}public void backtrack(int n,int leftSum,int rightSum,List<String> data,StringBuilder sb){//如果左括号数大于n、右括号数大于左括号数,直接返回if(leftSum > n || rightSum > leftSum){return;}//如果右括号个数等于n,递归结束if(rightSum == n){//将当前情况添加到data中data.add(sb.toString());//返回return;}//单层递归逻辑//添加左括号sb.append('(');backtrack(n,leftSum+1,rightSum,data,sb);sb.delete(sb.length()-1,sb.length());//添加右括号sb.append(')');backtrack(n,leftSum,rightSum+1,data,sb);sb.delete(sb.length()-1,sb.length());}
}

4.总结

        这道题的核心的思想其实就是递归穷举,再加上一些限制条件的逻辑判断就解决了。这道题就简单的水到这里,祝大家刷题愉快~

相关文章:

LeetCode100之括号生成(22)--Java

1.问题描述 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例1 输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()","()(())","()()()&qu…...

阿里云ios镜像源

阿里云镜像源&#xff1a;阿里巴巴开源镜像站-OPSX镜像站-阿里云开发者社区 下载centos7...

芯片:为何英伟达的GPU能在AI基础设施领域扮演重要角色?

英伟达的GPU之所以能在AI基础设施领域扮演重要角色&#xff0c;主要源于其硬件架构的优势以及其与深度学习算法的高度兼容性。以下是几个关键因素&#xff1a; 1. 并行计算能力 GPU&#xff08;图形处理单元&#xff09;本质上是为处理大量并行计算任务而设计的。与CPU相比&a…...

Linux系统之hostname相关命令基本使用

Linux系统之hostname相关命令基本使用 一、检查本地系统版本二、hostname命令的帮助说明中文帮助说明 三、hostname命令的基本使用1. 查看计算机名2. 查看本机上所有IP地址3. 查看主机FQDN4. 查看短主机名 四、hostnamectl命令的使用1. 查看主机详细信息2. 设置主机名3. hostna…...

Domain Adaptation(李宏毅)机器学习 2023 Spring HW11 (Boss Baseline)

1. 领域适配简介 领域适配是一种迁移学习方法,适用于源领域和目标领域数据分布不同但学习任务相同的情况。具体而言,我们在源领域(通常有大量标注数据)训练一个模型,并希望将其应用于目标领域(通常只有少量或没有标注数据)。然而,由于这两个领域的数据分布不同,模型在…...

在php中,Fiber、Swoole、Swow这3个协程都是如何并行运行的?

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons&#xff1a;JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram&#xff0c;自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 &#xff1f; 5 IDEA必装的插件&…...

SQLite PRAGMA

SQLite的PRAGMA命令是一种特殊的命令&#xff0c;用于在SQLite环境中控制各种环境变量和状态标志。PRAGMA值可以被读取&#xff0c;也可以根据需求进行设置【0†source】。 PRAGMA命令的语法格式如下&#xff1a; 要查询当前的PRAGMA值&#xff0c;只需提供该PRAGMA的名字&am…...

使用python调用JIRA6 REST API及遇到的问题

JIRA认证方式简述 JIRA接口调用有两种认证方式访问Jira Rest API&#xff0c;基本认证⽅式(⽤户名和密码)和OAuth1认证方式。 基本认证⽅式&#xff1a;因为⽤户名和密码会被浏览器重复地请求和发送&#xff0c;即使采⽤ SSL/TLS 发送&#xff0c;也会有安全隐患&#xff0c;…...

基于STM32的智能电表可视化设计:ESP8266、AT指令集、python后端Flask(代码示例)

一、项目概述 随着智能家居的普及&#xff0c;智能电表作为家庭用电管理的重要工具&#xff0c;能够实时监测电流、电压及功率&#xff0c;并将数据传输至后台进行分析和可视化。本项目以STM32C8T6为核心&#xff0c;结合交流电压电流监测模块、ESP8266 Wi-Fi模块、OLED显示屏…...

图片和短信验证码(头条项目-06)

1 图形验证码接口设计 将后端⽣成的图⽚验证码存储在redis数据库2号库。 结构&#xff1a; {img_uuid:0594} 1.1 创建验证码⼦应⽤ $ cd apps $ python ../../manage.py startapp verifications # 注册新应⽤ INSTALLED_APPS [django.contrib.admin,django.contrib.auth,…...

2501,wtl显示html

原文 在MFC程序中有专门封装的CHTMLView来显示超文本文件,如果在对话框中显示网页可用CDHTMLDialog,甚至可实现多页超文本向导风格的对话框,但是在WTL中却没有单独封装超文本的对应控件,这是因为COM组件的使用和编写本来就是ATL的强项,WTL扩展的是ATL欠缺的桌面应用的功能部分…...

嵌入式C语言:什么是指针?

目录 一、指针的基本概念 1.1. 定义指针 1.2. 赋值给指针 1.3. 解引用指针 1.4. 指针运算 1.5. 空指针 1.6. 函数参数 1.7. 数组和指针 1.8. 示例代码 二、指针在内存中的表示 2.1. 内存地址存储 2.2. 内存模型 2.3. 指针与硬件交互 2.4. 示例代码 三 、指针的重…...

解锁 KaiwuDB 数据库工程师,开启进阶之路

解锁 KaiwuDB 数据库工程师试题,开启进阶之路 一、KaiwuDB 数据库全方位洞察 (一)核心特性深度解析 原生分布式架构:摒弃传统集中式存储的局限,KaiwuDB 采用原生分布式架构,将数据分散存于多个节点。这不仅能有效避免单点故障风险,保障数据的高可用性,还能凭借并行处…...

ffmpeg7.0 aac转pcm

#pragma once #define __STDC_CONSTANT_MACROS #define _CRT_SECURE_NO_WARNINGSextern "C" { #include "libavcodec/avcodec.h" }//缓冲区大小&#xff08;缓存5帧数据&#xff09; #define AUDIO_INBUF_SIZE 40960 /*name depthu8 8s16 …...

【Pandas】pandas Series rdiv

Pandas2.2 Series Binary operator functions 方法描述Series.add()用于对两个 Series 进行逐元素加法运算Series.sub()用于对两个 Series 进行逐元素减法运算Series.mul()用于对两个 Series 进行逐元素乘法运算Series.div()用于对两个 Series 进行逐元素除法运算Series.true…...

线程安全问题介绍

文章目录 **什么是线程安全&#xff1f;****为什么会出现线程安全问题&#xff1f;****线程安全问题的常见场景****如何解决线程安全问题&#xff1f;**1. **使用锁**2. **使用线程安全的数据结构**3. **原子操作**4. **使用volatile关键字**5. **线程本地存储**6. **避免死锁*…...

为AI聊天工具添加一个知识系统 之27 支持边缘计算设备的资源存储库及管理器

本文问题 现在我们回到 ONE/TWO/TREE 的资源存储库 的设计--用来指导 足以 支持 本项目&#xff08;为AI聊天工具增加一套知识系统&#xff09;的 核心能力 “语言处理” 中 最高难度系数的“自然语言处理” 中最具挑战性的“含糊性” 问题的解决。--因为足以解决 自然语言中最…...

初识verilog HDL

为什么选择用Verilog HDL开发FPGA&#xff1f;&#xff1f;&#xff1f; 硬件描述语言&#xff08;Hardware Descriptipon Lagnuage&#xff0c;HDL&#xff09;通过硬件的方式来产生与之对应的真实的硬件电路&#xff0c;最终实现所设计的预期功能&#xff0c;其设计方法与软件…...

VS2015 + OpenCV + OnnxRuntime-Cpp + YOLOv8 部署

近期有个工作需求是进行 YOLOv8 模型的 C 部署&#xff0c;部署环境如下 系统&#xff1a;WindowsIDE&#xff1a;VS2015语言&#xff1a;COpenCV 4.5.0OnnxRuntime 1.15.1 0. 预训练模型保存为 .onnx 格式 假设已经有使用 ultralytics 库训练并保存为 .pt 格式的 YOLOv8 模型…...

Notepad++上NppFTP插件的安装和使用教程

一、NppFTP插件下载 图示是已经安装好了插件。 在搜索框里面搜NppFTP&#xff0c;一般情况下&#xff0c;自带的下载地址容易下载失败。这里准备了一个下载连接&#xff1a;Release v0.29.10 ashkulz/NppFTP GitHub 这里我下载的是x86版本 下载好后在nodepad的插件里面选择打…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...