括号生成[中等]
优质博文: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创建一张新的数据表简单(设置)表复杂(设置)表 填充测试…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
