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

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 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()","()(())","()()(…...

Flink 实时数仓(八)【DWS 层搭建(二)流量域、用户域、交易域搭建】

前言 今天的任务是完成流量域最后一个需求、用户域的两个需求以及交易域的部分需求&#xff1b; 1、流量域页面浏览各窗口汇总表 任务&#xff1a;从 Kafka 页面日志主题读取数据&#xff0c;统计当日的首页和商品详情页独立访客数。 注意&#xff1a;一般我们谈到访客&…...

gitlab-runner /var/run/docker.sock connect permission denied

usermod -aG docker gitlab-runner sudo service docker restart参考&#xff1a;https://gitlab.com/gitlab-org/gitlab-runner/-/issues/3492...

网络安全 - 应急响应检查表

前言 本项目旨在为应急响应提供全方位辅助&#xff0c;以便快速解决问题。结合自身经验和网络资料&#xff0c;形成检查清单&#xff0c;期待大家提供更多技巧&#xff0c;共同完善本项目。愿大家在应急之路一帆风顺。 图片皆来源于网络&#xff0c;如有侵权请联系删除。 一…...

AD常用PCB设计规则介绍 (详细版)

AD09常用PCB设计规则介绍 电气设计规则用来设置在电路板布线过程中所遵循的电气方面的规则&#xff0c;包括安全间距、短路、未布线网络和未连接引脚这四个方面的规则&#xff1a; &#xff08;1&#xff09;、安全间距规则(clearance) 该规则用于设定在PCB设计中&#xff0…...

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 是什么&#xff0c;有哪些特点为什么要使用 Redis 而不仅仅依赖 MySQLRedis 是单线程吗Redis 单线程为什么还这么快 Redis 数据类型和数据结构五种基本数据结构及应用场景其他数据类型Redis 底层数据结构 Redis 持久化数据不丢失的实现AOF 日志RDB 快…...

Java与Python优劣势对比:具体例子与深入分析

在软件开发的世界里&#xff0c;Java和Python是两座不可忽视的高峰。它们各自拥有独特的优势和应用场景&#xff0c;为开发者提供了多样化的选择。本文将通过具体例子&#xff0c;深入分析Java和Python在不同方面的表现&#xff0c;以期为读者提供更为详尽的参考。 1. 语法简洁…...

C++内存泄漏介绍

C内存泄漏&#xff08;Memory Leak&#xff09;是指程序在运行过程中&#xff0c;动态分配的内存没有被适当地释放或回收&#xff0c;导致这部分内存始终被占用&#xff0c;无法再被程序或其他程序使用。这种情况通常发生在使用了new或malloc等函数动态分配内存后&#xff0c;忘…...

C++分析红黑树

目录 红黑树介绍 红黑树的性质与平衡控制关系 红黑树节点的插入 情况1&#xff1a;不需要调整 情况2&#xff1a;uncle节点为红色 情况3&#xff1a;uncle节点为黑色 总结与代码实现 红黑树的删除&#xff08;待实现&#xff09; 红黑树的效率 红黑树介绍 红黑树是第二种平衡二…...

mysql线上查询之前要性能调优

查询优化是数据库性能调优的关键方面&#xff0c;目的是减少查询的执行时间和资源消耗。以下是一些常见的查询优化技巧及其示例&#xff1a; 使用合适的索引 问题&#xff1a; 全表扫描导致查询缓慢优化&#xff1a; 为经常用于搜索条件的列添加索引示例&#xff1a; 假设有一…...

GPIO输出控制之LED闪烁、LED流水灯以及蜂鸣器应用案例

系列文章目录 STM32之GPIO&#xff08;General Purpose Input/Output&#xff0c;通用型输入输出&#xff09; 文章目录 系列文章目录前言一、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&#xff08;阻变存储器&#xff09;设备上设计可靠的深度神经网络&#xff08;DNN&#xff09;加速器的方法。文章提出了两种关键技术来解决ReRAM固有的不可靠性问题&#xff1a;动态定点&#xff08;DFP&#xff09;数据表示…...

WebStock会话

其实使用消息队列也可以实现会话&#xff0c;直接前端监听指定的队列&#xff0c;使用rabbitmq的分组还可以实现不同群聊的效果。 1、依赖搭建&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org…...

5_现有网络模型的使用

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

软件安全测试报告内容和作用简析,软件测试服务供应商推荐

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

算法板子:树形DP、树的DFS——树的重心

思想&#xff1a; 代码&#xff1a; #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语言中&#xff0c;union 是一种特殊的数据类型&#xff0c;允许在相同的内存位置存储不同的数据类型。这意味着 union 中的所有成员共享同一块内存空间&#xff0c;因此它们之间会相互覆盖。在你给出的 Acceleration_type union 定义中&#xff0c;包含了三种不同类型的成员…...

MS2201以太网收发电路

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

乐乐音乐Kotlin版

简介 乐乐音乐Kotlin版&#xff0c;主要是基于ExoPlayer框架开发的Android音乐播放器&#xff0c;它支持lrc歌词和动感歌词(ksc歌词、krc歌词、trc歌词、zrce歌词和hrc歌词等)、多种格式歌词转换器及制作动感歌词、翻译歌词和音译歌词。 编译环境 Android Studio Jellyfish | …...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...