题目描述:
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:
[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/generate-parentheses
分析:
方法2:回溯法
1、对于每个位置都有两种选择左括号,和有括号。
2、对于每个位置都依此添加左括号,和有括号,若是不符合条件,立马停止当前分支的的继续前行。
方法1,是用的是贪心法,
1、在n=3的是在n=2的基础上,分别在左侧,右侧,外侧添加括号。
java实现
class Solution { //特此声明:我没错,辣鸡后台。我就没错!!!写此注释,以表抗议!! public List<String> generateParenthesis2(int n) { //这是方法1,,,用的可能是贪心算法。。 List<String> list = new ArrayList<>(); if (n<1) return list; list.add("()"); if (n==1) return list; String str="()"; String s=""; for (int i=2;i<=n;i++) { int j=0; int list_len= list.size(); //先算好,别他娘的放到循环中,哼!!!!!! int k=j; for (j = 0; j < list_len; j++) { //把list所有元素取出来,每个分别处理一遍,相对于队。 s = list.get(k); String left = "()" + s; String mid = "(" + s + ")"; String right = s + "()"; list.add(mid); list.add(left); if (!left.equals(right)) { list.add(right); } list.remove(s); } } return list; } public List<String> generateParenthesis(int n){ List<String> result=new ArrayList<>(); gen(result,"",n,n); return result; } public void gen(List<String> result,String str,int l,int r){ if (l==0 && r==0){ result.add(str); return; } if( l>r || l<0 || r<0) return ; String str2=new String(str); *****这波操作,看清楚喽,每个位置就两种情况,就不写for循环了 gen(result,str+="(",l-1,r); gen(result,str2+=")",l,r-1); } }
转载于:https://www.cnblogs.com/sqchao/p/11073479.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100852.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...