网站导航功能,网站icp备案信息如何查询,阜南网站建设公司,2021十大网络舆情案例一、题目 二、思路解析 1.思路#xff1a; 生成所有可能并且有效的括号组合——回溯方法 2.常用方法#xff1a; a.数组#xff0c;因为需要增删元素#xff0c;所以选择LinkedList
LinkedListString resnew LinkedList(); b.StringBuilder创建#xff0…一、题目 二、思路解析 1.思路 生成所有可能并且有效的括号组合——回溯方法 2.常用方法 a.数组因为需要增删元素所以选择LinkedList
LinkedListString resnew LinkedList(); b.StringBuilder创建因为要拼接字符
StringBuilder sbnew StringBuilder(); c.删除sb中的某一个字符因为要进行回溯
sb.deleteCharAt(s.length()-1); d.stringBuilder对象转string对象
String strsb.toString(); 3.核心逻辑 a.回溯模板
void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {处理节点;backtracking(路径选择列表); // 递归回溯撤销处理结果}
} b.终止条件当sb中的长度等于n*2时
if(sb.length()n*2){res.add(sb.toString());return ;
} c.回溯过程 首先必然是先放(才会有效同时(的数量不能超过n
if(openn){sb.append(();back(res,sb,n,open1,close);//进行回溯sb.deleteCharAt(sb.length()-1);
} 当(的数量大于)的时候就可以放入)是有效的
if(closeopen){sb.append());back(res,sb,n,open,close1);sb.deleteCharAt(sb.length()-1);
}
三、代码实现
class Solution {public ListString generateParenthesis(int n) {ListString resnew LinkedListString();StringBuilder sbnew StringBuilder();back(res,sb,n,0,0);return res;}void back(ListString res,StringBuilder sb,int n,int open,int close){if(sb.length()n*2){res.add(sb.toString());return ;}if(openn){sb.append(();back(res,sb,n,open1,close);sb.deleteCharAt(sb.length()-1);}if(closeopen){sb.append());back(res,sb,n,open,close1);sb.deleteCharAt(sb.length()-1);}}
}
