一般做网站带宽选择多大的,宁慈建设网站,公司标志,好的wordpress企业模板下载括号生成#xff08;Medium#xff09;
数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。示例 1#xff1a;输入#xff1a;n 3
输出#xff1a;[((())),(()()),(())()Medium
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。示例 1输入n 3
输出[((())),(()()),(())(),()(()),()()()]
示例 2输入n 1
输出[()]
提示1 n 8
Related Topics
字符串
动态规划
回溯思路分析
这道题可以使用动态规划的思想来进行实现动态规划就是说首先确定dp数组的定义然后找到递进关系式再找到初始值就可以获得所有的结果。这道题也是使用相同的思想虽然没有使用dp数组来进行数据的记录但是关系传递的思想是一样的。 根据动态规划的思想我们要想知道in的所有情况首先我们要知道in的所有情况。我们首先添加进in的时候新加入的一组括号“”然后把剩下的n-1添加到这一对括号中。 n-1的所有情况添加方法只有如下所示
“(” 【ip时所有括号的排列组合】 “)” 【iq时所有括号的排列组合】
其中 p q n-1且 p q 均为非负整数。 事实上当上述 p 从 0 取到 n-1q 从 n-1 取到 0 后所有情况就遍历完了。 然后我们使用递归的方式来完成这个过程。
代码实现
我自己的代码有点乱我直接贴标准答案了
class Solution {ArrayList[] cache new ArrayList[100];public ListString generate(int n) {if (cache[n] ! null) {return cache[n];}ArrayListString ans new ArrayListString();if (n 0) {ans.add();} else {for (int c 0; c n; c) {for (String left: generate(c)) {for (String right: generate(n - 1 - c)) {ans.add(( left ) right);}}}}cache[n] ans;return ans;}public ListString generateParenthesis(int n) {return generate(n);}
}
个人笔记
动态规划总结 第一步定义记录数组的元素规定数组元素的含义可能是二维数组也可能是一维数组。 第二步找出数组元素之间的递进关系式使用历史数据来找出下一步的数据比如dp[n] dp[n-1]dp[n-2]。 第三步找到运算的初始值从关系式可以知道从第n个元素可以一直回推到第一个元素所以你找到第一个元素就等于知道了所有的情况。 具体例题可以看同专栏文章 Leetcode刷题一——掷骰子等于目标和的方法数Medium Leetcode刷题十三——正则表达式匹配Hard
