LeetCode第22题:生成括号【22/1000 python 递归|动态规划】

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作icon-default.png?t=N7T8http://t.csdnimg.cn/Q59WX作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例icon-default.png?t=N7T8https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

问题描述

给定一个数字 n,要求生成所有可能的并且有效的括号组合。

有效的括号组合需要满足以下条件:

  • 左括号必须以正确的顺序闭合。
  • 左括号和右括号的数量相等。

例如,当 n = 3 时,一个可能的解集为:

[  "((()))",  "(()())",  "(())()",  "()(())",  "()()()"]

解题思路

方法一:递归

解题步骤

要生成所有有效的括号组合,我们可以使用递归来逐步构建字符串。我们维护两个变量:左括号和右括号的剩余数量。在每一步中,我们都有两个选择:

  • 如果左括号的数量不为0,我们可以添加一个左括号。
  • 如果右括号的数量大于左括号的数量,我们可以添加一个右括号。

python示例

  1. 主函数 generateParenthesis

    • 输入参数 n 代表一对括号的数量。
    • 定义了一个内部的辅助函数 backtrack,用于递归构建有效的括号组合。
    • 定义一个列表 results,用来存储所有有效的括号组合。
    • 最后,调用 backtrack 函数并返回 results
  2. 辅助函数 backtrack

    • 接收三个参数:当前累积的括号字符串 accumulated,当前开括号的数量 open_brackets,和当前闭括号的数量 close_brackets
    • 递归的基准情况是当累积的字符串长度达到2n时,此时我们找到了一个有效的括号组合,将其添加到结果列表中。
    • 如果开括号的数量小于n,我们可以添加一个开括号并递归地调用 backtrack
    • 如果闭括号的数量小于开括号的数量,这意味着我们可以添加一个闭括号而不破坏括号的有效性,因此我们再次递归地调用 backtrack,添加一个闭括号。

下面是一个Python示例代码

from typing import List

def generateParenthesis(n: int) -> List[str]:
    def backtrack(accumulated: str, open_brackets: int, close_brackets: int):
        # 当累积的字符串长度达到2n时,表示形成了一个有效的组合
        if len(accumulated) == 2 * n:
            results.append(accumulated)
            return
        # 如果开括号的数量少于n,可以添加一个开括号
        if open_brackets < n:
            backtrack(accumulated + '(', open_brackets + 1, close_brackets)
        # 如果闭括号数量少于开括号,可以添加一个闭括号
        if close_brackets < open_brackets:
            backtrack(accumulated + ')', open_brackets, close_brackets + 1)

    results = []
    backtrack('', 0, 0)
    return results

算法分析

  • 时间复杂度:O(4^n / sqrt(n)),这是基于卡塔兰数的通项公式。
  • 空间复杂度:O(n),递归栈的空间。

方法二:动态规划

动态规划是解决这类问题的另一种有效方法,其基本思想是将问题分解为一系列相关的子问题,并存储这些子问题的解,以避免重复计算。

解题步骤

  1. 定义一个列表 dp 来存储所有解,其中 dp[i] 包含了所有由 i 对括号能组成的有效组合。
  2. 初始化 dp[0] = [""],即没有括号时认为存在一个空的解。
  3. 对于每个 i1n(含),计算 dp[i] 的值:
    • 遍历 j0i-1(含),我们将 dp[i] 的解视为在 dp[j] 的解的基础上添加一对括号,然后在里面填充 dp[i-j-1] 的解。
    • 具体地,对于 dp[j] 中的每个字符串,我们在其外部添加一对括号,然后在这对括号内部尝试插入 dp[i-j-1] 中的所有可能的字符串。

python示例

def generateParenthesis(n: int) -> List[str]:
    dp = [[] for _ in range(n + 1)]
    dp[0] = [""]  # 初始化基础情况
    for i in range(1, n + 1):
        for j in range(i):
            for a in dp[j]:
                for b in dp[i-j-1]:
                    dp[i].append("(" + a + ")" + b)
    return dp[n]

算法分析

动态规划方法相较于递归回溯,具有不同的优势:

  • 时间复杂度:虽然动态规划方法的时间复杂度仍然是指数级的,因为解的数量本身就是指数增长的,但是通过避免重复计算子问题,它可能在某些情况下比纯粹的递归回溯更高效。
  • 空间复杂度:O(n * 卡塔兰数),这是因为需要存储所有由 i 对括号组成的所有有效组合。

应用场景

这个问题不仅是编程面试中的常见问题,也有着广泛的应用场景,例如在编译原理中处理括号匹配问题,在数学中研究卡塔兰数的性质等。

结论

生成所有有效的括号组合是一类经典的算法问题,常见于编程面试和算法竞赛。对于这个问题,主要有两种解决方案:递归回溯和动态规划。每种方法都有其独特的优势和考量。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【I/O】基于事件驱动的 I/O 模型---Reactor

Reactor 模型 BIO 到 I/O 多路复用 为每个连接都创建一个线程 假设我们现在有一个服务器&#xff0c;想要对接多个客户端&#xff0c;那么最简单的方法就是服务端为每个连接都创建一个线程&#xff0c;处理完业务逻辑后&#xff0c;随着连接关闭线程也要销毁&#xff0c;但是…

Meta的新AI深度伪造策略:增加标签,减少下架

每周跟踪AI热点新闻动向和震撼发展 想要探索生成式人工智能的前沿进展吗&#xff1f;订阅我们的简报&#xff0c;深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同&#xff0c;从行业内部的深度分析和实用指南中受益。不要错过这个机会&#xff0c;成为AI领…

【MYSQL锁】透彻地理解MYSQL锁

&#x1f525;作者主页&#xff1a;小林同学的学习笔录 &#x1f525;mysql专栏&#xff1a;小林同学的专栏 目录 1.锁 1.1 概述 1.2 全局锁 1.2.1 语法 1.2.1.1 加全局锁 1.2.1.2 数据备份 1.2.1.3 释放锁 1.2.1.4 特点 1.2.1.5 演示 1.3 表级锁 1.3.1 介绍 …

spring-cloud微服务openfeign

Spring Cloud openfeign对Feign进行了增强&#xff0c;使其支持Spring MVC注解&#xff0c;另外还整合了Ribbon和Nacos&#xff0c;从而使得Feign的使用更加方便 优势&#xff0c;openfeign可以做到使用HTTP请求远程服务时就像洞用本地方法一样的体验&#xff0c;开发者完全感…

计算机视觉 | 基于 ORB 特征检测器和描述符的全景图像拼接算法

Hi&#xff0c;大家好&#xff0c;我是半亩花海。本项目实现了基于 ORB 特征检测器和描述符的全景图像拼接算法&#xff0c;能够将两张部分重叠的图像拼接成一张无缝连接的全景图像。 文章目录 一、随机抽样一致算法二、功能实现三、代码解析四、效果展示五、完整代码 一、随机…

如何合理利用Vue 3中的ref和reactive

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

uni-app实现分页--(1)准备工作,首页下拉触底加载更多

实现流程如下: 分析&#xff1a;需要在滚动容器中添加滚动触底&#xff0c;在猜你喜欢中获取数据。难点&#xff1a;如何在父页面调用子组件内的方法。父组件中用ref&#xff0c;并定义组件实例类型&#xff0c;子组件中暴露方法 具体代码如下&#xff1a; 1.在父组件中添加…

去中心化社交媒体:分析 Facebook 在区块链平台上的角色

在当今数字时代&#xff0c;社交媒体已经成为人们日常生活中不可或缺的一部分。然而&#xff0c;随着人们对数据隐私和信息控制的关注不断增加&#xff0c;传统的中心化社交媒体平台也面临着越来越多的质疑和挑战。为了应对这些挑战&#xff0c;越来越多的人开始探索去中心化社…

关于Renesas R7 的选项字节开关看门狗

Renesas看门狗的模式是在选项字节中进行配置的&#xff0c;OPBT0的寄存器说明如下&#xff0c; 关于看门狗模式 &#xff1a; 和看门狗喂狗方式&#xff1a; 我们选择关闭看门狗&#xff08;也就是配置31位为软件触发看门狗开始&#xff0c;然后不启动就相当于关闭&#xff09…

【动手学深度学习】15_汉诺塔问题

注&#xff1a; 本系列仅为个人学习笔记&#xff0c;学习内容为《算法小讲堂》&#xff08;视频传送门&#xff09;&#xff0c;通俗易懂适合编程入门小白&#xff0c;需要具备python语言基础&#xff0c;本人小白&#xff0c;如内容有误感谢您的批评指正 汉诺塔&#xff08;To…

2024谷歌Google广告推广投放怎么做?如何收费?

当今全球市场&#xff0c;谷歌作为全球最大的搜索引擎&#xff0c;其广告服务——Google Ads&#xff0c;已成为企业触达全球消费者、提升品牌知名度、驱动业务增长的首选渠道之一。尤其是在2024年&#xff0c;随着数字营销环境的持续演进&#xff0c;精准、高效地运用Google A…

MySQL-创建和管理表:基础知识、创建和管理数据库、创建表、修改表、重命名表、删除表、清空表、拓展

创建和管理表 1. 基础知识1.1 一条数据存储的过程1.2 标识符命名规则1.3 MySQL中的数据类型 2. 创建和管理数据库2.1 创建数据库2.2 使用数据库2.3 修改数据库2.4 删除数据库 3. 创建表3.1 创建方式13.2 创建方式23.3 查看数据表结构 4. 修改表4.1 追加一个列4.2 修改一个列4.3…

Prometheus+Grafana监控K8S集群(基于K8S环境部署)

目录 一.环境信息二.部署提前工作三.部署Prometheus监控系统四.部署Node_exporter组件五.部署Kube_state_metrics组件六.部署Grafana可视化平台七.Grafana接入Prometheus数据八.Grafana添加监控模板九.拓展 一.环境信息 1.服务器及k8s版本信息 IP地址主机名称角色版本192.168…

SAM功能改进VRP-SAM论文解读VRP-SAM: SAM with Visual Reference Prompt

现已总结SAM多方面相关的论文解读&#xff0c;具体请参考该专栏的置顶目录篇 一、总结 1. 简介 发表时间&#xff1a;2024年3月30日 论文&#xff1a; 2402.17726.pdf (arxiv.org)https://arxiv.org/pdf/2402.17726.pdf代码&#xff1a; syp2ysy/VRP-SAM (github.com)htt…

JVM面试整理--对象的创建和堆

文章目录 对象的创建过程是怎样的?对象在内存中的结构是怎样的&#xff08;专业的叫法&#xff1a;对象的内存布局&#xff09;对象在内存分配时使用的哪种方式&#xff08;有的地方也称为&#xff1a;分配算法&#xff09;知道什么是“指针碰撞”吗&#xff1f;知道什么是“空…

电商技术揭秘十八:电商平台的云计算与大数据应用小结

电商技术揭秘相关系列文章 电商技术揭秘一&#xff1a;电商架构设计与核心技术 电商技术揭秘二&#xff1a;电商平台推荐系统的实现与优化 电商技术揭秘三&#xff1a;电商平台的支付与结算系统 电商技术揭秘四&#xff1a;电商平台的物流管理系统 电商技术揭秘五&#xf…

【产品】ANET智能通信管理机 物联网网关 电力监控/能耗监测/能源管理系统

产品概述 本系列智能通信管理机是一款采用嵌入式硬件计算机平台&#xff0c;具有多个下行通信接口及一个或者多个上行网络接口&#xff0c;用于将一个目标区域内所有的智能监控/保护装置的通信数据整理汇总后&#xff0c;实时上传主站系统&#xff0c;完成遥信、遥测等能源数据…

遥感图像处理:从畸变消除到专题信息提取

​ ​ ​在遥感技术的应用中&#xff0c;图像处理是不可或缺的关键步骤。从消除各种辐射畸变和几何畸变&#xff0c;到利用增强技术突出景物的光谱和空间特征&#xff0c;再到进一步理解、分析和判别处理后的图像&#xff0c;这一过程为我们呈现了一幅幅更为真实、清晰的…

Elasticsearch:从 ES|QL 到 PHP 对象

作者&#xff1a;来自 Elastic Enrico Zimuel 从 elasticsearch-php v8.13.0 开始&#xff0c;你可以执行 ES|QL 查询并将结果映射到 stdClass 或自定义类的 PHP 对象。 ES|QL ES|QL 是 Elasticsearch 8.11.0 中引入的一种新的 Elasticsearch 查询语言。 目前&#xff0c;它在…

基于GRU实现评论文本情感分析

一、问题建模 在线评论的细粒度情感分析对于深刻理解商家和用户、挖掘用户情感等方面有至关重要的价值&#xff0c;并且在互联网行业有极其广泛的应用&#xff0c;主要用于个性化推荐、智能搜索、产品反馈、业务安全等。此博文&#xff0c;共包含6大类20个细粒度要素的情感倾…