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

Python面试宝典第25题:括号生成

题目

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

        备注:1 <= n <= 8。

        示例 1:

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

        示例 2:

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

递归法

        使用递归法求解此问题的基本思想是:将生成有效括号序列的问题分解为更小的子问题。对于每一对括号,我们都可以看作是在已有的有效括号序列基础上,或者在其前后分别添加一个左括号和右括号。为了保证序列的有效性,我们需要确保任何时候左括号的数量都不少于右括号的数量。因此,可以采用递归的方式,逐步构建所有可能的序列。使用递归法求解本题的主要步骤如下。

        1、定义递归函数。函数接受两个参数,left 表示还可以使用的左括号数量,right 表示还可以使用的右括号数量,以及当前已经构造的括号序列curr_str。

        2、递归终止条件。当left和right都为0时,说明当前序列是一个有效的括号组合,将其加入结果列表。

        3、递归生成左括号。如果还有左括号可用(left > 0),则在当前序列后添加一个左括号,然后递归调用自身,减小left的计数。

        4、递归生成右括号。如果右括号的数量少于等于左括号(right <= left),则不能添加右括号,因为这会导致序列无效。否则,在当前序列后添加一个右括号,然后递归调用自身,减小right的计数。

        5、回溯。在每次递归调用返回后,撤销之前的选择,即回到上一层继续尝试其他可能性。

        根据上面的算法步骤,我们可以得出下面的示例代码。

def generate_brackets_by_recursion(n):def backtrack(left, right, curr_str, result):if left == 0 and right == 0:result.append(curr_str)returnif left > 0:backtrack(left - 1, right, curr_str + '(', result)if right > left:backtrack(left, right - 1, curr_str + ')', result)result = []backtrack(n, n, '', result)return resultprint(generate_brackets_by_recursion(3))
print(generate_brackets_by_recursion(1))

总结

        递归法求解本题的时间复杂度主要取决于生成的括号组合的数量。对于n对括号,有效的括号组合数量遵循卡特兰数,其公式为C_n = (1/(n+1)) * (2n choose n)。卡特兰数的增长速度非常快,大约是 4^n / (sqrt(pi*n)*n^(3/2))。因此,时间复杂度为 O(C_n),即:O(4^n / sqrt(n))。空间复杂度主要由递归栈的深度决定,最坏情况下,递归栈的深度为2n,故空间复杂度为O(n)。

        递归法特别适合括号生成类问题,因为它能自然地表达出问题的结构,即通过逐步构建解的空间树来寻找所有可能的解。然而,当n接近上限(比如:n=8)时,生成的组合数量会非常庞大,这可能会对程序的执行时间和内存使用提出较高的要求。因此,在实际应用中需要考虑递归的深度和效率问题。

相关文章:

Python面试宝典第25题:括号生成

题目 数字n代表生成括号的对数&#xff0c;请设计一个函数&#xff0c;用于能够生成所有可能的并且有效的括号组合。 备注&#xff1a;1 < n < 8。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;["((()))","(()())","(())()"…...

计算机毕业设计选题推荐-社区停车信息管理系统-Java/Python项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…...

Python面试整理-自动化运维

在Python中,自动化运维是一个重要的应用领域。Python凭借其简单易用的语法和强大的库支持,成为了运维工程师的首选工具。以下是一些常见的自动化运维任务以及如何使用Python来实现这些任务: 1. 文件和目录操作 Python的os和shutil模块提供了丰富的文件和目录操作功能。 impo…...

自动化测试与手动测试的区别!

自动化测试与手动测试之间存在显著的区别&#xff0c;这些区别主要体现在以下几个方面&#xff1a; 测试目的&#xff1a; 自动化测试的目的在于“验证”系统没有bug&#xff0c;特别是在系统处于稳定状态时&#xff0c;用于执行重复性的测试任务。 手工测试的目的则在于通过…...

下属“软对抗”,工作阳奉阴违怎么办?4大权谋术,让他不敢造次

下属“软对抗”&#xff0c;工作阳奉阴违怎么办&#xff1f;4大权谋术&#xff0c;让他不敢造次 第一个&#xff1a;强势管理 在企业管理中&#xff0c;领导必须展现足够的强势。 所谓强势的管理&#xff0c;并不仅仅指态度上的强硬&#xff0c;更重要的是在行动中坚持原则和规…...

爬猫眼电ying

免责声明:本文仅做分享... 未优化,dp简单实现 from DrissionPage import ChromiumPage import time urlhttps://www.maoyan.com/films?showType2&offset60 pageChromiumPage()page.get(url) time.sleep(2) for i in range(1,20):# 爬取的页数for iu_list in page.eles(.…...

政安晨:【Keras机器学习示例演绎】(五十七)—— 基于Transformer的推荐系统

目录 介绍 数据集 设置 准备数据 将电影评分数据转换为序列 定义元数据 创建用于训练和评估的 tf.data.Dataset 创建模型输入 输入特征编码 创建 BST 模型 开展培训和评估实验 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 希望政安晨的…...

15.4 zookeeper java client之Curator使用(❤❤❤❤❤)

Curator使用 1. 为什么使用Curator对比Zookeeper原生2. 集成Curator2.1 依赖引入curator-frameworkcurator-recipes2.2 `yml`配置连接信息2.3 CuratorConfig配置类2.4 Curator实现Zookeeper分布式锁业务2.4.1 业务:可重入锁和不可重入锁可重入锁和不可重入锁InterProcessMutex …...

哈默纳科HarmonicDrive谐波减速机的使用寿命计算

在机械传动系统中&#xff0c;减速机的应用无处不在&#xff0c;而HarmonicDrive哈默纳科谐波减速机以其独特的优势&#xff0c;如轻量、小型、传动效率高、减速范围广、精度高等特点&#xff0c;成为了众多领域的选择。然而&#xff0c;任何机械设备都有其使用寿命&#xff0c…...

前后端完全分离实现登录和退出

前后端分离的整合 使用springsecurity前端项目redis完成认证授权的代码 1. 搭建一个前端工程 使用 vue ui搭建&#xff0c;使用webstrom操作 2. 创建一个登录页面 <template><div class"login_container"><!-- 登录盒子 --><div class"l…...

生信技能55 - WisecondorX分析结果过滤和质控

WisecondorX分析CNV,对每条染色的CNV loss和gain进行分组,对每个组求ratio平均值和zscore平均值,基于该数值对CNV进行质控和过滤,并对连续的CNV进行合并,获得可信的CNV。 WisecondorX基本使用方法以及npz文件转换和reference构建参考文章: 生信技能53 - wiseconrdoX自动…...

待办管理软件电脑版哪个好?待办事项清单app

在快节奏的现代社会中&#xff0c;有效地管理时间和任务变得越来越重要。很多人喜欢使用待办管理软件来协助整理琐碎事务、规划工作任务&#xff0c;以此提升工作效率。特别是对于上班族来说&#xff0c;一款能在电脑上便捷使用的待办软件&#xff0c;更是提升工作效率的得力助…...

【Mind+】掌控板入门教程01 “秀”出我创意

我们的好朋友麦乐佳即将举办一场派对&#xff0c;她要求每个参加派对的人都要佩戴一个可以彰显自己独特创意的装置。可以是会发光的帽子&#xff0c;可以是复古的电子表&#xff0c;还可以是其他有创意的作品。而现在&#xff0c;我们的手边刚好有一块掌控板&#xff0c;它自带…...

操作系统篇--八股文学习第十一天|进程调度算法你了解多少,进程间有哪些通信方式,解释一下进程同步和互斥,以及如何实现进程同步和互斥

进程调度算法你了解多少&#xff1f; 答&#xff1a; 先来先服务&#xff1a;按照请求的顺序进行调度。 这种调度方式简单&#xff0c;但是能导致较长作业阻塞较短作业。最短作业优先&#xff1a;非抢占式的调度算法&#xff0c;按估计运行时间最短的顺序进行调度。 但是如果…...

慢慢欣赏arm64内核启动6 primary_entry之el2_setup代码第三部分

分析代码 解析完虚拟化部分&#xff0c;我们继续分析启动过程中&#xff0c;对中断控制器的处理 #ifdef CONFIG_ARM_GIC_V3/* GICv3 system register access */mrs x0, id_aa64pfr0_el1ubfx x0, x0, #ID_AA64PFR0_GIC_SHIFT, #4cbz x0, 3fmrs_s x0, SYS_ICC_SRE_EL2orr x0, x…...

初谈Linux多线程--线程控制

文章目录 线程的概述理解线程Linux中的线程重新理解的进程Windows的线程线程的优点线程的缺点理解线程调度成本低 进程VS线程 线程控制创建线程等待线程线程函数传参线程的返回值新线程的返回值新线程返回值错误返回值为类对象 创建多线程线程的终止线程的分离pthread_detach 线…...

文件工具类 - FileUtils

Slf4j Component public class FileUtils {/*** 文件夹复制到指定的文件夹*/SneakyThrowspublic static void copyDir(File source, File target) {if (!target.exists()) {boolean mkdirs target.mkdirs();}if (source.isDirectory()) {File[] files source.listFiles();if …...

Kafka源码剖析-Producer基于内存缓存池分配ByteBuffer

文章目录 在将消息发送到内存缓中区之前做的准备工作发送消息前的准备工作代码示例源码分析1. **消息序列化**2. **元数据准备**3. **分区选择**4. **批处理准备**总结大致浏览一下源码中将消息写入内存缓冲的运行流程源码分析1. **消息序列化和创建记录批次**2. **确定分区**3…...

实习十九:学习笔记

上午 1、构建vue发行版本 [rootserver ~]# cd eleme_web/ [rootserver eleme_web]# npm run buid //项目未执行时运行该命令&#xff0c;创建发行版本 [rootserver eleme_web]# cd dist/ //dist中包含发行版本的所有文件 [rootserver dist]# ls css favicon.ico i…...

OrionX:革新GPU资源管理,助力AI开发团队高效运作

您的AI开发团队是否经常陷入这样的窘境&#xff1a; 人多卡少&#xff0c;GPU资源难以满足每个成员的需求&#xff1f; 当开发环境中需要变更GPU卡配置时&#xff0c;流程繁琐不堪&#xff0c;不得不关闭容器、重新配置再重启&#xff1f; 是否曾因GPU卡分配后未被充分利用而…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

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

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

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

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…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...