括号生成[中等]
优质博文:IT-BLOG-CN
一、题目
数字n
代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
1 <= n <= 8
二、代码
【1】暴力法: 我们可以生成所有2^2n
个(
和)
字符构成的序列,然后我们检查每一个是否有效即可。为了生成所有序列,我们可以使用递归。长度为n
的序列就是在长度为n−1
的序列前加一个(
或)
。为了检查序列是否有效,我们遍历这个序列,并使用一个变量balance
表示左括号的数量减去右括号的数量。如果在遍历过程中balance
的值小于零,或者结束时balance
的值不为零,那么该序列就是无效的,否则它是有效的。
class Solution {public List<String> generateParenthesis(int n) {List<String> combinations = new ArrayList<String>();generateAll(new char[2 * n], 0, combinations);return combinations;}public void generateAll(char[] current, int pos, List<String> result) {if (pos == current.length) {if (valid(current)) {result.add(new String(current));}} else {current[pos] = '(';generateAll(current, pos + 1, result);current[pos] = ')';generateAll(current, pos + 1, result);}}public boolean valid(char[] current) {int balance = 0;for (char c: current) {if (c == '(') {++balance;} else {--balance;}if (balance < 0) {return false;}}return balance == 0;}
}
时间复杂度: O(2^2n * n)
,对于2^2n
个序列中的每一个,我们用于建立和验证该序列的复杂度为O(n)
。
空间复杂度: O(n)
,除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)
的空间,最多递归2n
层,因此空间复杂度为O(n)
。
【2】回溯法: 方法一还有改进的余地:我们可以只在序列仍然保持有效时才添加(
或)
,而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点,如果左括号数量不大于n
,我们可以放一个左括号。如果右括号数量小于左括号的数量,我们可以放一个右括号。
class Solution {public List<String> generateParenthesis(int n) {List<String> ans = new ArrayList<String>();backtrack(ans, new StringBuilder(), 0, 0, n);return ans;}public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {if (cur.length() == max * 2) {ans.add(cur.toString());return;}if (open < max) {cur.append('(');backtrack(ans, cur, open + 1, close, max);cur.deleteCharAt(cur.length() - 1);}if (close < open) {cur.append(')');backtrack(ans, cur, open, close + 1, max);cur.deleteCharAt(cur.length() - 1);}}
}
我们的复杂度分析依赖于理解generateParenthesis(n)
中有多少个元素。这个分析超出了本文的范畴,但事实证明这是第n
个卡特兰数1/(n+1)(2n/n)
,这是由4n/n
渐近界定的。
时间复杂度: O(4n/n)
,在回溯过程中,每个答案需要O(n)
的时间复制到答案数组中。
空间复杂度: O(n)
,除了答案数组之外,我们所需要的空间取决于递归栈的深度,每一层递归函数需要O(1)
的空间,最多递归2n
层,因此空间复杂度为O(n)
。
【3】按括号序列的长度递归: 任何一个括号序列都一定是由(
开头,并且第一个(
一定有一个唯一与之对应的)
。这样一来,每一个括号序列可以用(a)b
来表示,其中a
与b
分别是一个合法的括号序列(可以为空)。那么,要生成所有长度为2n
的括号序列,我们定义一个函数generate(n)
来返回所有可能的括号序列。那么在函数generate(n)
的过程中:
1、我们需要枚举与第一个(
对应的)
的位置2i+1
;
2、递归调用generate(i)
即可计算a
的所有可能性;
3、递归调用generate(n−i−1)
即可计算b
的所有可能性;
4、遍历a
与b
的所有可能性并拼接,即可得到所有长度为2n
的括号序列。
为了节省计算时间,我们在每次generate(i)
函数返回之前,把返回值存储起来,下次再调用generate(i)
时可以直接返回,不需要再递归计算。
class Solution {ArrayList[] cache = new ArrayList[100];public List<String> generate(int n) {if (cache[n] != null) {return cache[n];}ArrayList<String> ans = new ArrayList<String>();if (n == 0) {ans.add("");} else {for (int c = 0; c < n; ++c) {for (String left: generate(c)) {for (String right: generate(n - 1 - c)) {ans.add("(" + left + ")" + right);}}}}cache[n] = ans;return ans;}public List<String> generateParenthesis(int n) {return generate(n);}
}
时间复杂度: O(4^n/n)
,该分析与方法二类似。
空间复杂度: O(4^n/n)
,此方法除答案数组外,中间过程中会存储与答案数组同样数量级的临时数组,是我们所需要的空间复杂度。
相关文章:

括号生成[中等]
优质博文:IT-BLOG-CN 一、题目 数字n代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:["((()))","(()())","(())(…...
配置ubuntu的VNC时遇到报错_XSERVTransmkdir: Mode of /tmp/.X11-unix should be set to 1777
现在win11内嵌了ubuntu系统,我在根据打造基于 VNC 的 Ubuntu 20.04 的远程桌面 配置VNC server时,到了 vncserver :1 这一步,遇到报错: vncserver: /usr/bin/Xtigervnc did not start up, please look into /root/.vnc/xxxxx.:1.…...

openstack部署nova中出现的问题:
[rootcontroller nova]# su -s /bin/sh -c “nova-manage db sync” nova /usr/lib/python2.7/site-packages/pymysql/cursors.py:170: Warning: (1831, u’Duplicate index block_device_mapping_instance_uuid_virtual_name_device_name_idx. This is deprecated and will be…...
【OpenCV 基础知识 3】边缘检测
文章目录 cvCanny完整示例代码 cvCanny 这行代码使用OpenCV库中的 cvCanny 函数对灰度图像进行边缘检测。让我解释一下: cvCanny(gray, dst, 10, 100, 3);gray: 这是输入的灰度图像,即要进行边缘检测的图像。dst: 这是输出的边缘图像,即将结…...
拓宽知识储备量(指数级成长)
对于增强自己的知识储备,不是什么知识都往脑袋里去塞,最好的办法就是让自己的心态回到自己初心的时候,始终保值一颗学者的心,你像那些成功人士,比如格力,华为,腾讯等这样的大公司创始人哪个不是…...

x264 帧类型代价计算原理:slicetype_mb_cost 函数分析
slicetype_mb_cost 函数 函数功能 计算每个宏块 MB 的代价 cost。函数参数分析 x264_t *h:全局编码结构体x264_mb_analysis_t *a:宏块分析结构体x264_frame_t **frames:系列帧数据结构体int p0:帧序号之一,一般指向靠前帧int p1:帧序号之一,一般指向靠后帧int b:帧标志…...

战网国际服加速器哪个好用 暴雪战网免费加速器分享
战网国际服(Battle.net International或Battle.net Global)是由暴雪娱乐公司(Blizzard Entertainment)运营的面向全球玩家的多人在线游戏平台。与专注于特定地区的版本不同,国际服允许玩家不受地域限制地访问暴雪的多款…...

Java入门基础学习笔记26——break,continue
跳转关键字: break: 跳出并结束当前所在循环的执行。 continue: 用于跳出当前循环中的当次执行,直接进入循环中的下一次执行。 package cn.ensource.loop;public class BreakContinueDemo8 {public static void main(String[] a…...

HNU-算法设计与分析-作业6
第六次作业【分支限界法】 文章目录 第六次作业【分支限界法】<1> 算法实现题6-2 最小权顶点覆盖问题<2> 算法实现题6-6 n后问题<3> 算法实现题6-7 布线问题 <1> 算法实现题6-2 最小权顶点覆盖问题 ▲问题重述 问题描述: 给定一个赋权无向…...

2D Chests Assets - Mega Pack
科幻/奇幻/经典主题的箱子和容器。AAA质量,高分辨率,VFX,源PSD文件。 这是一个带有手绘套装的大包装: -【梦幻之栗】 -【科幻钱包】 AAA质量。高分辨率。一切都已准备就绪,可供使用。包括PSD文件。 在1.1版本中添加了VFX并将项目更新为URP。请注意,新的VFX仅适用于URP/HD…...

一种基于电场连续性的高压MOSFET紧凑模型,用于精确表征电容特性
来源:A Compact Model of High-Voltage MOSFET Based on Electric Field Continuity for Accurate Characterization of Capacitance(TED 24年) 摘要 本文提出了一种新的高压MOSFET(HV MOS)紧凑模型,以消…...
vue阶段性测试题,内容丰富,案例典型,题目配有答案
阶段性测试 理论题实践题 1)理论题 请简述Vue、Node.js、Vscode是什么,以及有什么关系 1. vue是一个轻量级、比较灵活的且支持组件开发的网络框架 2. node.js是让JavaScript运行在服务器上的一直环境 3. Vscode是一款有着丰富插件的代码编辑器 4. 关系…...

如何查看PC电脑已经已经连接上的网络WiFi密码?
运行ncpa.cpl...
Java 语言的特点分析及应用
Java语言自问世以来,因其独特的设计理念和广泛的应用领域,成为了编程语言中的一颗璀璨明星。以下是对Java语言特点的详细分析及其实际应用场景,希望能帮助面试者更好地理解和掌握Java的优势。 1. 简单易学 Java的语法简单,类似于…...

Golang | Leetcode Golang题解之第84题柱状图中最大的矩形
题目: 题解: func largestRectangleArea(heights []int) int {n : len(heights)left, right : make([]int, n), make([]int, n)for i : 0; i < n; i {right[i] n}mono_stack : []int{}for i : 0; i < n; i {for len(mono_stack) > 0 &&am…...

linux实用命令
一、常用命令 mkdir -p mkdir -p 命令用于在Unix和Linux系统中创建目录。其中,-p参数确保目录名称存在,如果目录不存在的就新创建一个。换句话说,-p参数允许创建一个目录和它不存在的父目录,确保了指定的整个目录路径都会被…...

创建和管理数据库
1. 一条数据的存储过程 存储数据是处理数据的第一步.只有正确的把数据存储起来,我们才能进行有效的处理和分析.否则,只能是一团乱麻.在MySQL中,一个完整的数据存储过程一共有四步 : 创建数据库,确认字段,创建数据表&a…...
Spring STOMP-发送消息
如果你想要从应用程序的任何地方向连接的客户端发送消息,要怎么做?任何应用程序组件都可以向brokerChannel发送消息。要这样做,最简单方法是注入一个SimpMessagingTemplate并使用它来发送消息。通常,你会按类型注入它,…...

kubernetes多master集群架构
一、完成master02节点的初始化操作 master02环境准备,详细过程参考上一期博客环境准备 #添加主机映射 vim /etc/hosts 192.168.88.3 master01 192.168.88.8 master02 192.168.88.4 node01 192.168.88.5 node021、准备master02节点需要的文件 从 master01 节点上拷…...

MySQL数据库的初始化(创建库、创建表、向数据库添加测试数据)
MySQL数据库的初始化(创建库、创建表、修改数据库访问密码、向数据库添加测试数据) MySQL数据库简介MySQL创建一个新的数据库修改数据库访问密码 MySQL创建一张新的数据表简单(设置)表复杂(设置)表 填充测试…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...

消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...

论文阅读:Matting by Generation
今天介绍一篇关于 matting 抠图的文章,抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法,已经有很多的工作和这个任务相关。这两年 diffusion 模型很火,大家又开始用 diffusion 模型做各种 CV 任务了&am…...
Monorepo架构: Nx Cloud 扩展能力与缓存加速
借助 Nx Cloud 实现项目协同与加速构建 1 ) 缓存工作原理分析 在了解了本地缓存和远程缓存之后,我们来探究缓存是如何工作的。以计算文件的哈希串为例,若后续运行任务时文件哈希串未变,系统会直接使用对应的输出和制品文件。 2 …...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...