抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

30 | 面试题:生成有效括号组合

22. 括号生成

解法一:数学归纳法

直接按 n=1…n 的做法,一个个写岀来,抱歉我写不出来。

解法二:递归搜索 DFS 不推荐

当 n 给定后,字符串的长度已经给定,大小为2n,每个格子都可以是 ‘(‘ 或者 ‘)’,可以生成2^2n 个候选人,然后判断候选人是否合法。

由于做了一个完全的搜索,所以时间复杂度:O(2^2n)

解法三:改进解法二,剪枝

  1. 局部判断不合法,不再进行递归,例:一上来就是’)’,这肯定是不合法的
  2. 2n 个格子,其中的count(左括号)==count(右括号),并且数量一定是 n,所以递归时,每用掉一个括号,就减去一个,括号没有剩余时,则所有情况都已结束。

剪枝后,因为限制了括号数量,时间复杂度变成了 O(2ⁿ)

老师的Python 版:

Kotlin版:这里为了看得清楚 没有用字符串模板

class Solution {
fun generateParenthesis(n: Int): List<String> {
val res = ArrayList<String>()
gen(0, 0, n, "", res)
return res
}

/**
* 辅助函数
* @left 左括号剩余
* @right 右括号剩余
* @n 需要生成的 括号对 数
* @result 当前结果
*/
fun gen(left: Int, right: Int, n: Int, result: String, res: ArrayList<String>) {
//左右括号都用完
if (left == n && right == n) {
res.add(result)
return
}
//左括号没用完
if (left < n) {
gen(left + 1, right, n, result + "(", res)
}
//右括号不能随意拼 必须已经用了相同数量的左括号才合法
if (left > right && right < n) {
gen(left, right + 1, n, result + ")", res)
}
}
}

加餐内容:Google code style

PS:按公司规范即可


0条评论

发表评论