群晖系统可以做网站吗,wordpress 关闭边栏,青岛网上房地产官网,优化网站排名哪家好22.数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1#xff1a; 输入#xff1a;n 3 输出#xff1a;[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2#xff1a; 输入#x… 22.数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 示例 1 输入n 3 输出[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2 输入n 1 输出[“()”] 观察会发现有效的组合在生成时一定满足左括号多余等于右括号否则比如 ()) 无论之后怎么加括号最后都是无效组合生成的过程不难想到用回溯法在每一位尝试放左括号或者右括号在前一步的基础上继续各自递归尝试很像二叉树遍历基本上套用回溯模版即可回溯模板 private void backtrack(原始参数) {//终止条件(递归必须要有终止条件)if (终止条件) {//一些逻辑操作可有可无视情况而定return;}for (int i for循环开始的参数; i for循环结束的参数; i) {//一些逻辑操作可有可无视情况而定//做出选择//递归backtrack(新的参数);//一些逻辑操作可有可无视情况而定//撤销选择}}最终代码 ListString res new ArrayList();public ListString generateParenthesis(int n) {dfs(n, n, );return res;}// left能放的左括号数量right 同理// str当前生成的字符串public void dfs(int left, int right, String str){// 说明此时右括号数量多余左括号直接舍弃if(leftright)return;// 左右括号都用完就记录该组合if(left0 right 0){res.add(str);return;}// 左括号用完就继续加右括号以下同理if(left0)dfs(left,right-1,str));else if(right0)dfs(left-1,right,str();else{dfs(left-1,right,str();dfs(left,right-1,str));}}他人题解思路一致代码更精简。实际上只要左括号还有并且左括号数量大于等于左括号数量就说明 rightleft0那就可以直接递归所以可以不分情况 public void dfs(int left, int right, String str){// 左括号都用到负数了肯定不行了// 右括号更多必定无效组合// 并且如果通过了以下两个条件就说明 right 也 0所以不需要再判断 rightif(left0 || leftright)return;if(left0 right 0){res.add(str);return;}dfs(left-1,right,str();dfs(left,right-1,str));}他人题解2动态规划从感觉上来说是感觉可以 dp 的但是这个公式真不太好想。设 dp[i] 表示 n 等于 i 时生成的有效括号组合递推公式为dp[i] ( dp[m] ) dp[k] m k i-1 。具体写的时候这里比较绕的就是 dp[i] 是一个 list比如 dp[1] [()]dp[2][()(), (())] 所以即使知道知道动态规划方程 dp 部分还是比较难理解dp[i] ( dp[m] ) dp[k] 的理解这里的意思其实是 dp[m] 中每个组合和 dp[k] 中每个组合结合成新的结果。比如 ( dp[m] ) dp[k] 先简化理解成 dp[m]dp[k] 假设 dp[m][1,2], dp[k][3,4] 那么其实得到结果应该为 [13,14,23,24]。 所以核心部分如下 for (int m 0; m i; m) {int k i - 1 - m;ListString str1 dp[m];ListString str2 dp[k];for (String s1 : str1) {for (String s2 : str2) {cur.add(( s1 ) s2);}}}边界条件为 dp[0] 所以最终代码如下 public ListString generateParenthesis(int n) {// 初始化 [[]]不然 dp[i-1] 都没东西ListString[] dp new List[n 1];ListString dp0 new ArrayList();dp0.add();dp[0] dp0;for (int i 1; i n; i) {// 记录 dp[i] 的组合ListString cur new ArrayList();for (int m 0; m i; m) {int k i - 1 - m;ListString str1 dp[m];ListString str2 dp[k];for (String s1 : str1) {for (String s2 : str2) {cur.add(( s1 ) s2);}}}dp[i] cur;}return dp[n];}他人题解2优化上面 dp 的核心就在于 dp[m] 和 dp [k] 的组合但是 dp[m] 其实不就是 generateParenthesis(m)所以可以优化如下 public static ListString generateParenthesis(int n) {ListString list new ArrayList();if (n 0) {//边界条件的判断list.add();return list;}for (int m 0; m n; m) {int k n - m - 1;ListString first generateParenthesis(m);ListString second generateParenthesis(k);for (String left : first) {for (String right : second) {list.add(( left ) right);}}}return list;}
