58同城建设网站,网站开发有哪几类,sql数据库添加网站,wordpress外链go文章目录题目描述代码 解法题目描述
先吐槽#xff1a;括号题好恶心。。括号有效判断需要考虑考虑
代码 解法
思路#xff1a;把括号分开看#xff0c;这道题和20.有效的括号其实是有差别的#xff1a;这道题的括号是成对的#xff0c;而20题的括号则没有…
文章目录题目描述代码 解法题目描述
先吐槽括号题好恶心。。括号有效判断需要考虑考虑
代码 解法
思路把括号分开看这道题和20.有效的括号其实是有差别的这道题的括号是成对的而20题的括号则没有这个硬性要求。 基于此我们可以用这么一个思路去考虑这道题分配一个大小为2n的括号集其中n个是左括号n个是右括号递归过程中需要剪枝递归结束时获得答案。结果正确性见代码注释1.2.
class Solution {public ListString generateParenthesis(int n) {/**1. 如何确保不重复画格子走不同分枝肯定至少有一个格子不同。如下[x][x][o][x][x][x][o][o]也就是无论如何不同分枝代表的字符串内容肯定不相同。2. 如何跑全因为包括了所有左右括号组合。*/ArrayListString ans new ArrayList();dfs(ans, n, n, );return ans;}// ans存储答案left左括号剩余数right右括号剩余数now当前字符串public void dfs(ArrayListString ans, int left, int right, String now) {// 递归结束if (left 0 right 0) {ans.add(now);}// 剪枝情况如)肯定是错误顺序。if (right left) {return;}// 走左括号路线if(left 0){dfs(ans, left - 1, right, now ();}// 走右括号路线if(right 0){dfs(ans, left, right - 1, now ));}return;}
}
