注册网站会有哪些风险,wordpress站点获利,各大网站开发语言,有赞和凡科小程序哪个好文章目录 1. 题目2. 思路及代码实现#xff08;Python#xff09;2.1 暴力法2.2 回溯法 1. 题目
数字 n n n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。
示例 1#xff1a;
输入#xff1a; n 3 n 3 … 文章目录 1. 题目2. 思路及代码实现Python2.1 暴力法2.2 回溯法 1. 题目
数字 n n n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入 n 3 n 3 n3 输出 [ ( ( ( ) ) ) , ( ( ) ( ) ) , ( ( ) ) ( ) , ( ) ( ( ) ) , ( ) ( ) ( ) ] [((())),(()()),(())(),()(()),()()()] [((())),(()()),(())(),()(()),()()()]
示例 2
输入 n 1 n 1 n1 输出 [ ( ) ] [()] [()] 提示 1 ≤ n ≤ 8 1 \leq n \leq 8 1≤n≤8
2. 思路及代码实现Python
2.1 暴力法
该思路先生成所有的 2 2 n 2^{2n} 22n 个 “” 和 “” 字符串构成的序列然后检查生成的序列是否有效一共有 n n n 对括号共 2 n 2n 2n 个字符每个位置存在两种不同的选择因此总共有 2 2 n 2^{2n} 22n 种序列。
为了生成所有序列可以使用递归。长度为 n n n 的序列就是在长度为 n − 1 n−1 n−1 的序列后加一个 “(” 或 “)”。为了检查序列是否有效我们遍历这个序列并使用一个变量 b a l bal bal 表示左括号的数量减去右括号的数量。如果在遍历过程中 b a l bal bal 的值小于零或者结束时 b a l bal bal 的值不为零那么该序列就是无效的否则它是有效的。前者说明遍历一段字符串时出现 “)” 大于 “(” 的数量显然说明该子串不能成对而后者说明整个字符串的左右括号数并不相等。
该算法的时间复杂度为 O ( 2 2 n n ) O(2^{2n}n) O(22nn)对于 2 2 n 2^{2n} 22n 个序列中的每一个对其进行有效性的验证的复杂度为 O ( n ) O(n) O(n)。而空间复杂度除了存储答案组之外还需要存储探索答案的栈深复杂度为 O ( n ) O(n) O(n)。
class Solution:def generateParenthesis(self, n: int):def generate(A):if len(A) 2*n:if valid(A):ans.append(.join(A))else:A.append(()generate(A)A.pop()A.append())generate(A)A.pop()def valid(A):bal 0for c in A:if c (: bal 1else: bal - 1if bal 0: return Falsereturn bal 0ans []generate([])return ans执行用时71 ms 消耗内存16.54 MB
2.2 回溯法
上述方法是遍历生成所有的可能的序列然后再进行判断这里我们发现有可以改进的地方就是在生成序列时提前跟踪序列的左右括号的数据来决定扩展序列时所选择的括号。例如已有子序列的左括号数量不大于 n n n则可以放置左括号如果右括号数量小于左括号数量可以放置一个右括号。
该算法的复杂度分析依赖于该有效序列可以回溯出 的元素个数。这证明是第 n n n 个卡特兰数 1 n 1 ( 2 n n ) \dfrac{1}{n1}\dbinom{2n}{n} n11(n2n) 这是由 4 n n n \dfrac{4^n}{n\sqrt{n}} nn 4n 渐近界定的。因此时间复杂度为 O ( 4 n n ) O(\dfrac{4^n}{\sqrt{n}}) O(n 4n)。空间复杂度为保存答案和保存栈深的消耗为 O ( n ) O(n) O(n)。
class Solution:def generateParenthesis(self, n: int):ans []def backtrack(S, left, right):if len(S) 2 * n:ans.append(.join(S))returnif left n:S.append(()backtrack(S, left1, right)S.pop()if right left:S.append())backtrack(S, left, right1)S.pop()backtrack([], 0, 0)return ans执行用时42 ms 消耗内存16.55 MB 题解来源力扣官方题解
