当前位置: 首页 > 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的插件里面选择打…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...