最新回复 (1)
-
#!/usr/bin/python #-*- coding:utf-8 -*- """ 由于这题和检查有效括号字符串那题属于一个上下文,一些面试者会想到一个清奇的思路,就是先生成 全部的排列然后再排除无效的。这种思路就不赘述了,肯定会被判定为不优的。 正确的思路应该就是递归(recursion)。简单思路就是如果有n对括号,那么每个字符串就一定有2n个字符, 每生成一个字符实际上都在做一个二分决策,即“我是接下来生成开阔号'('好呢,还是闭括号')'好呢?“ 如果决策正确,我们将最终得到一个有效的括号字符串,便可将其加入solution_set当中去。 从二叉树的角度可以可视化这个过程(n=2为例): '' / '(' / \ '()' '((' / \ '()(' '(()' / \ '()()' '(())' 虽然我们最终只取二叉树的叶子节点,但是实际上我们还是遍历了途径节点,所以算法时间复杂度是O(2^n)。 如果被要求写循环(iteration)的方式做的话,借助一个有Stack(栈)功能的数据结构就能搞定了。 任何recursion能解决的问题都是借助了函数本身call stack的特性,都可以想到在转循环写法的时候用到栈。 """ def generate_parentheses(n): solution_set = [] # 基础参数:空结果集,空字符串,已添加0个开括号,已添加0个闭括号,需要填充n对括号 generate_parentheses_recursive(solution_set, "", 0, 0, n) return solution_set def generate_parentheses_recursive(solution_set, current, num_open, num_close, n): # 当已添加开括号和已添加闭括号都达到n时: if (num_open == n and num_close == n): # 得到了一个有效的括号字符串,将其加入结果集 solution_set.append(current) # 当开括号还不够时: if num_open < n: # 继续添加开括号 generate_parentheses_recursive(solution_set, current+"(", num_open+1, num_close, n) # 当开括号已满,但闭括号还不够时: if num_open > num_close: #继续添加闭括号 generate_parentheses_recursive(solution_set, current+")", num_open, num_close+1, n) def generate_parentheses_iterative(n): solution_set = [] s = [] s.append(("", 0, 0, n)) while (len(s) != 0): top = s.pop() if (top[1] == n and top[2] == n): solution_set.append(top[0]) if top[1] < n: s.append((top[0]+"(", top[1]+1, top[2], n)) if top[1] > top[2]: s.append((top[0]+")", top[1], top[2]+1, n)) return solution_set if __name__ == "__main__": print(generate_parentheses(3)) print(generate_parentheses_iterative(3))```