括号生成[中等]

优质博文: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来表示,其中ab分别是一个合法的括号序列(可以为空)。那么,要生成所有长度为2n的括号序列,我们定义一个函数generate(n)来返回所有可能的括号序列。那么在函数generate(n)的过程中:
1、我们需要枚举与第一个(对应的)的位置2i+1
2、递归调用generate(i)即可计算a的所有可能性;
3、递归调用generate(n−i−1)即可计算b的所有可能性;
4、遍历ab的所有可能性并拼接,即可得到所有长度为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),此方法除答案数组外,中间过程中会存储与答案数组同样数量级的临时数组,是我们所需要的空间复杂度。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/328721.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

山东大学机器学习实验lab9 决策树

山东大学机器学习实验lab9 决策树 所有公式来源于<<机器学习>>周志华github上有.ipynb源文件 修改&#xff1a; 2024 5.15 添加了一些Node属性&#xff0c;用于标记每个Node使用的划分feature的名称&#xff0c;修改后的版本见 github Node 类 构造函数 初始化…

ubuntu升级python

添加Python官方PPA源 sudo add-apt-repository ppa:deadsnakes/ppa 执行会显示各个版本ubuntu可以安装哪些python版本 更新软件包索引 sudo apt update 安装需要版本Python sudo apt install python3.11 检查Python版本: which python11 /usr/bin/python3.11 设置为系统默认Pyt…

命令行中,Python 想使用本地环境,但总是显示为Anaconda的虚拟环境

电脑环境 Python 本地环境&#xff08;Python3.9.5&#xff09;Anaconda 虚拟环境&#xff08;Python3.8.8&#xff09; 遇到的问题 在cmd 中&#xff0c;我想在本地环境使用 Python、pip &#xff0c;但它却是一直识别成Anaconda的虚拟环境。 解决方法 环境变量配置中&am…

Python | Leetcode Python题解之第91题解码方法

题目&#xff1a; 题解&#xff1a; class Solution:def numDecodings(self, s: str) -> int:n len(s)# a f[i-2], b f[i-1], c f[i]a, b, c 0, 1, 0for i in range(1, n 1):c 0if s[i - 1] ! 0:c bif i > 1 and s[i - 2] ! 0 and int(s[i-2:i]) < 26:c aa,…

汇中 SCL-61D2超声水表汇中通讯协议

RS-485串行通讯接口设置表 通用代码注释 读取正向仪表数据 DD的内容为 通讯示例 主机命令&#xff1a;2A 41 4A 仪表响应&#xff1a;26 41 4A 00 00 13 63 00 00 07 72 00 00 10 34 00 33 读取负向仪表数据&#xff1a;&#xff08;单向型仪表无此命令&#xff09; DD的内容…

redis-stack部署概要

第一步&#xff0c;下载redis-stack 下载链接&#xff1a;Downloads - Redis 第二步&#xff0c;redis安装包解压缩 gzip -d redis-stack-server-7.2.0-v10.rhel8.x86_64.tar.gz tar -xvf redis-stack-server-7.2.0-v10.rhel8.x86_64.tar 第三步&#xff0c;编辑etc下的redis…

【Spring security】Note01-pig登录验证过程

&#x1f338;&#x1f338; pig 登录验证 &#x1f338;&#x1f338; 一、大概执行顺序&#xff0c;便于理解 pig spring-security 二、执行过程分析 请求拦截&#xff1a; 当客户端发送请求时&#xff0c;Spring Security 的过滤器链会首先拦截该请求。过滤器链中的每个…

数据结构与算法—顺序表

目录 一、线性表 二、顺序表概念 三、实现顺序表 1、声明结构体 2、初始化 3、打印数据 4、销毁 5、尾插&头插 尾插 判断是否扩容 头插 6、尾删&头删 尾删 头删 7、 指定位置插入元素 8、 删除指定位置元素 9、 查找指定元素位置 10、修改指定位置元…

angular13 自定义组件全项目都可用 自存

1.定义自定义组件 使用命令创建一个组件 但删除它在你的module里的声明&#xff0c;因为会报错只能引用一次 在本组件中创建一个module文件&#xff0c;引入刚才的组件component.ts import { NgModule } from angular/core; import { CommonModule } from angular/common; im…

简化路径[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个字符串path&#xff0c;表示指向某一文件或目录的Unix风格 绝对路径 &#xff08;以/开头&#xff09;&#xff0c;请你将其转化为更加简洁的规范路径。在Unix风格的文件系统中&#xff0c;一个点.表示当前目录本身&#x…

vue3 自定义组件

在项目中&#xff0c;我们会遇到一些没有现成的组件&#xff0c;那这个时候我们就需要自己去写一个满足我们需求的组件。 比如&#xff0c;我需要一个上下排布&#xff0c;上面显示标题&#xff0c;下面显示内容的组件。封装完成后方便复用。 1、布局组件 我定义一个上下结构的…

2024生日快乐祝福HTML源码

源码介绍 2024生日快乐祝福HTML源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;记事本打开源码文件可以进行内容文字之类的修改&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面&#xff0c; 源码截图 源码下载 2024生日快乐祝福HTML源码

Gradio 案例——将 dicom 文件转为 nii文件

文章目录 Gradio 案例——将 dicom 文件转为 nii文件界面截图依赖安装项目目录结构代码 Gradio 案例——将 dicom 文件转为 nii文件 利用 SimpleITK 库&#xff0c;将 dicom 文件转为 nii文件更完整、丰富的示例项目见 GitHub - AlionSSS/dcm2niix-webui: The web UI for dcm2…

一种请求头引起的跨域问题记录(statusCode = 400/CORS)

问题表象 问题描述 当我们需要在接口的headers中添加一个自定义的变量的时候&#xff0c;前端的处理是直接在拦截器或者是接口配置的地方直接进行写&#xff0c;比如下面的这段比较基础的写法&#xff1a; $http({method: "post",url:constants.backend.SERVER_LOGIN…

selenium发展史

Selenium Core 2004 年&#xff0c;Thoughtworks 的工程师 Jason Huggins 正在负责一个 Web 应用的测试工作&#xff0c;由于这个项目需要频繁回归&#xff0c;这导致他不得不每天做着重复且低效的工作。为了解决这个困境&#xff0c;Jason 开发了一个运行在 JavaScript 沙箱中…

React框架-Next 学习-1

创建一个 Next.js 应用,node版本要高&#xff0c;16.5以上 npm淘宝镜像切为https://registry.npmmirror.com npm config set registry https://registry.npmmirror.com npx create-next-applatest//安装后 使用npm run dev 启动 Next.js 是围绕着 页面&#xff08;pages&am…

我21岁玩“撸货”,被骗1000多万

最近&#xff0c;撸货业界内发生了一些颇受瞩目的事件。 在郑州&#xff0c;数码档口下面抢手团长跑路失联&#xff0c;涉及金额几百万&#xff0c;在南京&#xff0c;一家知名的电商平台下的收货站点突然失联&#xff0c;涉及金额高达一千多万&#xff0c;令众多交易者震惊不已…

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测

回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测 目录 回归预测 | Matlab实现GA-LSSVM遗传算法优化最小二乘支持向量机多输入单输出回归预测预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 Matlab实现GA-LSSVM遗传算法优化最小…

基于 Spring Boot 博客系统开发(十)

基于 Spring Boot 博客系统开发&#xff08;十&#xff09; 本系统是简易的个人博客系统开发&#xff0c;为了更加熟练地掌握 SprIng Boot 框架及相关技术的使用。&#x1f33f;&#x1f33f;&#x1f33f; 基于 Spring Boot 博客系统开发&#xff08;九&#xff09;&#x1f…

【考研数学】张宇《1000题》强化阶段正确率多少算合格?

张宇1000题真的很练人心态.... 基础不好&#xff0c;建议别碰1000题 基础好&#xff0c;1000题建议在两个月以内刷完 如果自己本身在基础阶段学的比较水&#xff0c;自己的薄弱点刷了一小部分题没有针对性完全解决&#xff0c;转身去刷1000题就会发现&#xff0c;会的题目刷…