首页 > 编程语言 >【算法题】22.括号生成-力扣(LeetCode)

【算法题】22.括号生成-力扣(LeetCode)

时间:2024-09-11 09:53:44浏览次数:13  
标签:剪枝 return 22 dfs 力扣 括号 二叉树 ans LeetCode

【算法题】22.括号生成-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

22. 括号生成

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= n <= 8

2.题解

该题我采用深度优先搜索中的回溯和剪枝

思路

这些组合就两种情况,一种是“(”,一种是“)”,可以很容易想到二叉树,而二叉树可以想到深度优先搜索,而这题的深度优先有要求,就是“(”后面必须要有“)”,不能是“)(”这样的形式。

我们观察发现,符合条件的组合必须得满足两个条件:

  • 1.括号必须两两配对

  • 2.在选择括号进行组合时,“)”的次数始终不能大于“(”的次数,比如说

    第一次选择的时候选了")",那么当前的")"的个数已经大于了"("的个数,所以后面的就不用选了,直接剪掉。
    

为了方便理解,我粗略地画了一张图,表示n=2时,也就是有四层的二叉树,红色的表示不符合条件被剪枝的

在这里插入图片描述

Python代码

class Solution(object):
    def generateParenthesis(self, n):
        global s
        """
        :type n: int
        :rtype: List[str]
        """
        ans,s=[],''
        def dfs(d,l,r):          # d表示二叉树的深度,l,r分别表示选择到当前层时"("和")"的个数
            global s
            if l>n or r>l:return # 剪枝 不符合前文所说的两种条件时直接return剪掉
            if d==2*n:           
                ans.append(s)    # 如果搜索到了最底层,那一定是符合条件的,添加到ans中去,然后停止
                return
            s+='('
            dfs(d+1,l+1,r)
            s=s[:-1]             # 二叉树搜索的基本方法
            s+=')'
            dfs(d+1,l,r+1)
            s=s[:-1]             # 回溯
        dfs(0,0,0)
        return ans

3.结语

本人资历尚浅,发博客主要是记录与学习,欢迎大佬们批评指教!大家也可以在评论区多多交流,相互学习,共同成长。

标签:剪枝,return,22,dfs,力扣,括号,二叉树,ans,LeetCode
From: https://blog.csdn.net/Janium/article/details/142112103

相关文章

  • leetcode 1809 没有广告的剧集
    表:Playback+-------------+------+|ColumnName|Type|+-------------+------+|session_id|int||customer_id|int||start_time|int||end_time|int|+-------------+------+session_id是该表中具有唯一值的列。customer_id是观看该剧集......
  • LeetCode算法—双指针
    一:普通双指针1、题目1:两数求和-1(1)方法1:普通双指针思路:定义两个指针;第一个指针放在数组的首位;第二个指针放在下一个元素的位置;然后遍历这个;如果两个元素的和为目标值就返回对对应的下标和索引值!deffuc(nums,target):foriinrange(len(nums)):forjinrange(i......
  • 72. 编辑距离(leetcode)
    https://leetcode.cn/problems/edit-distance/classSolution{publicintminDistance(Stringword1,Stringword2){//经典题编辑距离//f[i][j]表示word1前i个字符中选择进行操作,word2前j个字符进行选择进行操作相同的最少步数//以word1[......
  • 583. 两个字符串的删除操作(leetcode)
    https://leetcode.cn/problems/delete-operation-for-two-strings/solutions/两种做法,1.直接dp2.转换题意,思考成LCSclassSolution{publicintminDistance(Stringword1,Stringword2){//编辑距离的简化版//f[i][j]表示word1前i个字符中选择,wo......
  • [COCI2022-2023#2] Tramvaji
    [COCI2022-2023#2]Tramvaji题意对于每个车站\(i\),给出一条信息。从车站\(j<i\)到车站\(i\)花费了时间\(t\)。求出哪两个站之间花费的时间最少。思路考虑求出\(s_i\)表示从\(1\)到\(i\)的最少时间。答案即\(\min_{i=2}^{n}s_i-s_{i-1}\)。对于给出的信息\(......
  • LeetCode Hot100刷题记录-234.回文链表
    题目:给你一个单链表的头节点head,请你判断该链表是否为回文链表。如果是,返回true;否则,返回false。PS:回文序列是向前和向后读都相同的序列。解题思路:遍历链表,将每个元素存放入一个新的数组中。遍历完成后,再用两个指针前后遍历数组来判断两个数字是否相等。/***Def......
  • 线性dp:LeetCode122.买卖股票的最佳时机ll
    买卖股票本文所讲解的内容与LeetCode122.买卖股票的最佳时机ll,这道题题意相同,阅读完本文后可以自行挑战一下力扣链接题目叙述:给定一个长度为N的数组,数组中的第i个数字表示一个给定股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交......
  • [COCI2021-2022#6] Zemljište
    [COCI2021-2022#6]Zemljište题意给出一个矩阵,一个子矩阵的权值为\(|m-a|+|m-b|\),\(m\)为子矩阵数值和,\(a,b\)为给出的数。求该矩阵权值最小的子矩阵。思路枚举子矩阵上界和下界,左右界使用双指针枚举,令\(a<b\)。对于每个左界,不断扩展右界直到子矩阵和大于\(b\),因为再......
  • Springboot车源后台管理系统f227y--(程序+源码+数据库+调试部署+开发环境)
    本系统(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。系统程序文件列表开题报告内容一、项目背景随着汽车市场的蓬勃发展,车源信息的有效管理和高效利用成为汽车经销商、租赁公司、电商平台等企业的核心需求。为了提升车源信息的整合......
  • 代码随想录训练营day41|121. 买卖股票的最佳时机,122.买卖股票的最佳时机II,123.买卖股
    121.买卖股票的最佳时机这题和贪心中的买股票很想,但这里不用考虑局部问题,因为只用买一张卖一张。我想可以用一个数组dp来记录买入价格和卖出价格。然后遍历数组草我感觉我写的想贪心。动态规划dp[i][0]表示第i天不持股的最大收益,dp[i][1]表示第i天持股的最大收益。dp......