当前位置: 首页 > 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语法】向上取整 向下取整。

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

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...