LeetCode-22. 括号生成 小鱼儿 2024-03-24 15:01 23阅读 0赞 #### 目录 #### * * 题目思路 * 回溯法 * 遇到的困难 题目来源 [22. 括号生成][22.] ### 题目思路 ### 回溯法,一般可以解决如下几种问题: * 组合问题:N个数里面按一定规则找出k个数的集合 * 切割问题:一个字符串按一定规则有几种切割方式 * 子集问题:一个N个数的集合里有多少符合条件的子集 * 排列问题:N个数按一定规则全排列,有几种排列方式 * 棋盘问题:N皇后,解数独等等 这道题的思路:就是不停选括号,要么选左括号,要么选右括号。 并有这些约束的: 只要(有剩,就可以选(。 (((((这么选,都还不能判定为非法。 当剩下的)比(多时,才可以选),否则,)不能选,选了就非法。 因为:剩下的)比(少,即,使用的)比(多,不能成双成对。 **举个简单的例子吧** n=2 如果(),接下来你选)就变成()),就不能成对了,那么只能选( 总结一句话:剩下的)比(多时,才可以选),相等的话也只能选( ![在这里插入图片描述][37bfdf09b71143069567b90610a15d66.png] ### 回溯法 ### * 1.确定回溯函数参数 首先需要一个字符串builder来收集叶子节点的结果,然后用一个字符串数组result保存起来,这两个变量我依然定义为全局。 我们要定义两个参数letf和right,分别表示左右括号 List<String> result = new ArrayList<>(); StringBuilder builder = new StringBuilder(); void backtracking(int n ,int left,int right) * 2.确定终止条件 如果builder字符长度等于n\*2,得到最终结果,把它放进result里面 **我来解释一下什么意思** 当n=2时,那么其中一个结果就是(()),那么答案就是4个,满足就放进result里面 if(builder.length() == n*2){ result.add(String.valueOf(builder)); return; } // 剪枝 if (left < right) { return; } * 3.确定单层遍历逻辑 if(left < n)表示最多能加多少个( if(left < n){ builder.append("("); //处理 backtracking(n,left+1,right); builder.deleteCharAt(builder.length() - 1); //回溯 } if(right < n){ builder.append(")"); //处理 backtracking(n,left,right+1); builder.deleteCharAt(builder.length() - 1); //回溯 } 代码实现 class Solution { List<String> result = new ArrayList<>(); StringBuilder builder = new StringBuilder(); public List<String> generateParenthesis(int n) { if(n == 0){ return result; } backtracking(n,0,0); return result; } public void backtracking(int n ,int left,int right){ if(builder.length() == n*2){ result.add(String.valueOf(builder)); return; } // 剪枝 if (left < right) { return; } if(left < n){ builder.append("("); backtracking(n,left+1,right); builder.deleteCharAt(builder.length() - 1); } if(right < n){ builder.append(")"); backtracking(n,left,right+1); builder.deleteCharAt(builder.length() - 1); } } } ![在这里插入图片描述][d46beaa643234b09bec4ef66ffadc16f.png] ### 遇到的困难 ### 对StringBuilder的api不熟悉 builder.append("("); //添加 builder.deleteCharAt(builder.length() - 1); //删除 [22.]: https://leetcode.cn/problems/generate-parentheses/ [37bfdf09b71143069567b90610a15d66.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a8b66a5ffa014edbaaae442766cad2ee.png [d46beaa643234b09bec4ef66ffadc16f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/cefa753d27124b03bc9665c85e6d3842.png
还没有评论,来说两句吧...