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

[Java·算法·中等]LeetCode22. 括号生成

每天一题,防止痴呆

  • 题目
  • 示例
  • 分析思路1
  • 题解1
  • 分析思路2
  • 题解2
  • 分析思路3
  • 题解3

👉️ 力扣原文

题目

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

示例

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

分析思路1

递归和回溯的方法:

  1. 定义一个函数来生成括号,该函数需要接收三个参数:剩余左括号数量、剩余右括号数量、当前生成的括号字符串。
  2. 如果剩余左括号数量和剩余右括号数量都为0,则说明已经生成了一个完整的括号字符串,将其加入结果集。
  3. 如果剩余左括号数量大于0,则可以在当前括号字符串后面添加一个左括号,并递归调用函数。
  4. 如果剩余右括号数量大于剩余左括号数量,则可以在当前括号字符串后面添加一个右括号,并递归调用函数。

题解1

class Solution {public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();gen(n , n , "", res);return res;}private void gen(int left, int right, String str, List<String> res){if(left == 0 && right == 0){res.add(str);return;}if(left > 0){gen(left - 1,right, str+"(", res );}if(right > left){gen(left, right - 1, str+")", res);}}}

执行结果
在这里插入图片描述

分析思路2

另一种递归的思路,效率不是很高。

  1. 当n=1时,只有一种合法的括号组合"()"。
  2. 当n>1时,可以在n-1对括号的基础上,将"()"插入到每一对括号中间,得到n对括号的所有合法组合。
  3. 为了避免重复,使用HashSet来存储所有的括号组合。
  4. 最后将HashSet转换成ArrayList并返回即可。

题解2

class Solution {public static List<String> generateParenthesis(int n){if (n == 1){return Arrays.asList("()");}HashSet<String> set = new HashSet<>();for (String str : generateParenthesis(n - 1)){for (int i = 0; i <= str.length()/2; i++) {set.add(str.substring(0,i) + "()" + str.substring(i,str.length()));}}return new ArrayList<>(set);}}

执行结果
在这里插入图片描述

分析思路3

动态规划

  1. 定义一个dp数组,其中dp[i]表示i对括号的所有合法组合。
  2. 初始化dp[0]为"",表示0对括号时只有一种合法组合。
  3. 对于每个i,遍历j从0到i-1,将dp[j]和dp[i-j-1]拼接在一起,组成新的括号组合。
  4. 在拼接时,需要保证左括号数量等于右括号数量,否则组合是不合法的。
  5. 最后返回dp[n]即可。

题解3

class Solution {public static List<String> generateParenthesis(int n) {List<String>[] dp = new List[n + 1];dp[0] = Arrays.asList("");for (int i = 1; i <= n; i++) {dp[i] = new ArrayList<>();for (int j = 0; j < i; j++) {for (String left : dp[j]) {for (String right : dp[i - j - 1]) {dp[i].add("(" + left + ")" + right);}}}}return dp[n];}}

执行结果
在这里插入图片描述

相关文章:

[Java·算法·中等]LeetCode22. 括号生成

每天一题&#xff0c;防止痴呆题目示例分析思路1题解1分析思路2题解2分析思路3题解3&#x1f449;️ 力扣原文 题目 数字 n 代表生成括号的对数&#xff0c;请你设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 输入&#xff1a;n 3 输出&…...

Git项目合并实践

Git项目合并实践 一、前言 环境 操作系统&#xff1a;Windows 10 专业版 代码托管平台&#xff1a;Gitee 场景 同一个项目&#xff0c;在某一个时间点&#xff0c;被另外一个团队拷贝和修改&#xff0c;并且代码不在同一个仓库&#xff0c;最后需要合并项目 不是同一个项…...

C++实战md5、base64算法实现(附源码)

C++常用功能源码系列 文章目录 C++常用功能源码系列前言一、常用加密算法1. md5是什么二、源码1. md52. base64、decode总结前言 本文是C/C++常用功能代码封装专栏的导航贴。部分来源于实战项目中的部分功能提炼,希望能够达到你在自己的项目中拿来就用的效果,这样更好的服务…...

P6专题:P6 EPPM和PPM基本概念

目录 引言 Oracles Primavera P6 Enterprise Project Portfolio Management&#xff08;P6 EPPM&#xff09; Oracles Primavera P6 Professional Project Management 引言 Oracle Primavera系列软件专注于项目密集型企业&#xff0c;其整个项目生命周期内所有项目的组合管…...

【为什么事务@Transactional会失效】

在Spring框架中&#xff0c;Transactional注解用于声明一个方法需要被包含在事务中&#xff0c;以确保数据库操作的一致性和完整性。Transactional注解通常用于Service层或DAO层的方法上。 Transactional注解失效可能是由以下原因引起的&#xff1a; 注解未被正确声明或配置&a…...

NLP中的对话机器人——模型的评估

引言 本文是七月在线《NLP中的对话机器人》的视频笔记&#xff0c;主要介绍FAQ问答型聊天机器人的实现。 模型的评估 我们如何评估模型的好坏&#xff1f;由于我们的数据集没有提供测试数据&#xff0c;所以我们很难评估模型的好 坏。如果我们要做非常严谨的评估&#xff0c…...

数据挖掘知识规整与心得体会

一.大数据的特点&#xff1a; 数据多&#xff0c;类型多&#xff0c;更新快&#xff0c;更新内容多。 二.分类&#xff08;classification&#xff09;与混淆矩阵&#xff08;confusion matrix&#xff09; 这里的分类说的是二分类问题&#xff0c;比如说把人分为好人和坏人&a…...

修正一些formdesigner的一些bug与操作

之前集成了formdesigner表单设计器&#xff0c;但还是有些问题&#xff0c;所以进行一些bug修复与功能修正 一、之前组件布局的图标不见了 在main.js里增加下面一行 import /components/formdesigner/assets/iconfont/iconfont.js 效果如下&#xff1a; 二、选择列表没有数…...

前端网络安全

什么是同源策略同源指的是&#xff1a;协议、端口号、域名必须一致。他是浏览器的一个用于隔离潜在恶意文件的重要安全机制。限制了从同一个源加载的文档或脚本&#xff0c;与另一个源的资源进行交互。同源策略主要限制了三个方面&#xff1a;当前域下的js脚本不能够访问其他域…...

docker内存统计

在docker里top和在docker外top看内存都是没有变化的&#xff0c;但是用docker stats看mem uasge就一直在涨top命令和docker stats命令采集内存使用的方式不同所致。top命令采集的是当前进程的内存使用情况&#xff0c;而docker stats命令采集的是整个Docker容器的内存使用情况。…...

【IDEA】IDEA使用有道翻译引擎—详细配置步骤

目录 前言 步骤一&#xff1a;下载翻译工具Translate 步骤二&#xff1a;注册登录有道云平台 步骤三&#xff1a;配置有道翻译 前言 2022年10月 谷歌翻译已经不在中国了&#xff0c;所以IDEA配置谷歌翻译会出错。 步骤一&#xff1a;下载翻译工具Translate 打开idea设置set…...

js求解《初级算法》56.最长公共前缀

一、题目描述 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀&#xff0c;返回空字符串 ""。 输入&#xff1a;strs ["flower","flow","flight"] 输出&#xff1a;"fl" 输入&#xff1a;strs ["…...

嵌入式Linux(二十四)系统烧写

将uboot&#xff0c;linux kernel&#xff0c;.dtb&#xff0c;rootfs烧写到板子上的EMMC上&#xff0c;避免断网导致不能运行。 1. MfgTool工具介绍 一路解压之后&#xff0c;得到以下两项&#xff1a; ①Profiles文件夹&#xff1a;后续烧写文件放到这个文件夹。  其中关注…...

【ECNU】3496. 贪吃的 xjj 和贪心的 oxx(C++)

目录 题目 输入格式 输出格式 样例 提示 思路 代码 题目 单点时限: 2.0 sec 内存限制: 256 MB oxx 与 xjj 终于到了 Xiamen&#xff0c;他们第一件事就是去吃当地著名的特产椰子饼。 他们共买了 n 盒礼盒&#xff0c;第 i 盒含 ai 块椰子饼。oxx 与 xjj 约定让 oxx …...

【iOS】设置背景渐变色

drawRect函数 主要负责iOS的绘图操作&#xff0c;程序会自动调用此方法进行绘图。我在这个函数中绘制渐变背景色。 方法定义&#xff1a; -(void)drawRect:(CGRect)rect; 重写此方法&#xff0c;执行重绘任务-(void)setNeedsDisplay; 标记为需要重绘&#xff0c;异步调用dra…...

Scrapy框架(高效爬虫)

文章目录一、环境配置二、创建项目三、scrapy数据解析四、基于终端指令的持久化存储1、基于终端指令2、基于管道3、数据同时保存至本地及数据库4、基于spider爬取某网站各页面数据5、爬取本页和详情页信息&#xff08;请求传参&#xff09;6、图片数据爬取ImagesPipeline五、中…...

程序设计语言-软件设计(二十一)

数据结构与算法&#xff08;二十&#xff09;快速排序、堆排序(四)https://blog.csdn.net/ke1ying/article/details/129269655 这篇主要讲的是 编译与解释、文法、正规式、有限自动机、表达式、传值与传址、多种程序语言特点。 编译的过程 解释型 和 编译型 编译型过程&#…...

【小破站下载工具】Python tkinter 实现网站下载工具,所有数据一键获取

目录前言开发环境本次项目案例步骤先展示下完成品的效果界面导入模块先创建个窗口功能按键主要功能代码编写功能一功能二功能三前言 最近很多同学想问我&#xff0c;怎么把几个代码的功能集合到一起&#xff1f; 很简单&#xff0c;写一个界面就行了&#xff0c;想要哪个代码…...

C51---IO口状态翻转

1.example #include "reg52.h" #include "intrins.h" //main.c(11): error C264: intrinsic _nop_: declaration/activation error,?????????? sbit led1 P3^7;//????,??????? sbit key1 P2^1; sbit key2 P2^0; void Delay50ms()…...

2023年春【移动计算技术】文献精读(一)-1 ||| 附:【Markdow语法】向上取整 向下取整。

沉默着走了有 // 多遥远 // 抬起头 // 蓦然间 // 才发现 // 一直倒退 // 倒退到原点 // 倔强坚持 // 对抗时间 “在光芒万丈之前,我们都要欣然接受眼下的难堪和不易,接受一个人的孤独和偶然无助,认真做好眼前的每件事,你想要的都会有。”——毕淑敏 🎯作者主页:追光者♂…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

PL0语法,分析器实现!

简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...