做室内设计的网站,图书馆网站建设所需资料,网站地图模板下载,网站个人博客怎么做1.问题描述 数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例1 输入#xff1a;n 3
输出#xff1a;[((())),(()()),(())(),()(()),()()()请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 示例1 输入n 3
输出[((())),(()()),(())(),()(()),()()()] 示例2 输入n 1
输出[()] 提示
1 n 8 难度等级 中等 题目链接 生成括号
2.解题思路 这道题要我们求出指定括号对数所能满足的所有可能想法很简单把这个过程分成无数的添加左括号和右括号的小步每一次添加之后判断是否是合法的括号形式是的话就继续不是的话就撤销回退因为我们要穷举所有的可能所以在每一步真正执行完成之后都要把当前这一步撤销回退(回溯)。 这里我们直接来看核心的递归函数是如何实现的。 首先我们要确定递归的结束条件。如果左括号的个数大于n或者右括号的个数大于左括号的个数那么情况的括号形式是非法的递归结束不做任何操作。如果右括号的个数等于n说明我们找到了一种符合题意的情况将当前这种情况加入到存储结果的List集合中然后递归结束。 //如果左括号数大于n、右括号数大于左括号数直接返回if(leftSum n || rightSum leftSum){return;}//如果右括号个数等于n,递归结束if(rightSum n){//将当前情况添加到data中data.add(sb.toString());//返回return;} 接着我们要来确定递归的结束条件。我们需要传入题目给的括号对数n当前左括号的个数和当前右括号的个数以及用来存储合法可能的List集合由于每一种可能的情况都是一个字符串这意味着我们要不断的对字符串进行增删操作所以这里我们可以传入一个StringBuilder来提高字符串操作的效率。
public void backtrack(int n,int leftSum,int rightSum,ListString data,StringBuilder sb) 然后我们就可以来确定单层的递归逻辑了。其实很简单在当前情况的基础上添加左括号然后递归调用当前方法同时左括号个数1获取当前情况基础上所有的可能情况获取到所有可能情况之后将左括号从当前情况的字符串中移除(撤销回滚)。右括号的步骤和上述差不多我就不多赘述了。 //单层递归逻辑//添加左括号sb.append(();backtrack(n,leftSum1,rightSum,data,sb);sb.delete(sb.length()-1,sb.length());//添加右括号sb.append());backtrack(n,leftSum,rightSum1,data,sb);sb.delete(sb.length()-1,sb.length()); 最后只需要在主方法中调用我们上面实现的函数并将答案返回即可。 public ListString generateParenthesis(int n) {//存储结果的ListListString data new ArrayList();//递归函数获取生成括号的对数backtrack(n,0,0,data,new StringBuilder());//返回最终答案return data;}
3.代码展示
class Solution {public ListString generateParenthesis(int n) {//存储结果的ListListString data new ArrayList();//递归函数获取生成括号的对数backtrack(n,0,0,data,new StringBuilder());//返回最终答案return data;}public void backtrack(int n,int leftSum,int rightSum,ListString data,StringBuilder sb){//如果左括号数大于n、右括号数大于左括号数直接返回if(leftSum n || rightSum leftSum){return;}//如果右括号个数等于n,递归结束if(rightSum n){//将当前情况添加到data中data.add(sb.toString());//返回return;}//单层递归逻辑//添加左括号sb.append(();backtrack(n,leftSum1,rightSum,data,sb);sb.delete(sb.length()-1,sb.length());//添加右括号sb.append());backtrack(n,leftSum,rightSum1,data,sb);sb.delete(sb.length()-1,sb.length());}
}
4.总结 这道题的核心的思想其实就是递归穷举再加上一些限制条件的逻辑判断就解决了。这道题就简单的水到这里祝大家刷题愉快~
