网站运营与管理实训报告,美观网站建设物美价廉,北京专业网站搭建公司,设计师35岁后的出路文章目录 题目方法一#xff1a;递归#xff1a;方法二#xff1a;递归回溯 题目 方法一#xff1a;递归#xff1a; 递归入口 空子结果集#xff0c;左括号数目#xff08;初始为0#xff09;#xff0c;右括号数目#xff08;初始为0#xff09; 递归出口 若左括… 文章目录 题目方法一递归方法二递归回溯 题目 方法一递归 递归入口 空子结果集左括号数目初始为0右括号数目初始为0 递归出口 若左括号 大于n 或者 左括号数量大于右括号数量 不符合题目要求 结束递归剪枝 若 左括号数目 和 右括号数目都等于n 说明符合条件 结束递归 递归方向 dfsback(zre‘(’,leftsum1,rightsum);//左括号递归 dfsback(zre‘)’,leftsum,rightsum1);//右括号递归
class Solution {ListString res new ArrayList(); // 结果集int n 0;public ListString generateParenthesis(int n) {this.n n;String zre ;//子结果集dfsback(zre,0,0);return res;}public void dfsback(String zre,int leftsum,int rightsum){// n3// leftsum n(((( 不满足 leftsum rightsum (( )))不满足if(leftsum n || leftsum rightsum ) return; //若左括号 大于n 或者 左括号数量大于右括号数量 不符合题目要求 结束递归剪枝if(leftsum n rightsum n ){//若 左括号数目 和 右括号数目都等于n 说明符合条件 结束递归res.add(zre);return;}dfsback(zre(,leftsum1,rightsum);//左括号递归dfsback(zre),leftsum,rightsum1);//右括号递归}
}或者下面在递归过程中根据条件去递归符合括号生成条件才递归
// 全递归 根据括号数目在递归过程中剪枝ListString res new ArrayList(); // 结果集int n 0;public ListString generateParenthesis(int n) {this.n n;String zre ;//子结果集dfsback(zre,0,0);return res;}public void dfsback(String zre,int leftsum,int rightsum){if(leftsum n rightsum n) { //左右括号都达到了n 结束递归res.add(zre);return;}if(leftsum n || leftsum rightsum ) return;//若左括号 大于n 或者 左括号数量大于右括号数量 不符合题目要求 结束递归剪枝if(leftsum rightsum) dfsback(zre(,leftsum1,rightsum); //在左括号右括号相等的情况下 只能添加左括号if(leftsum rightsum) {//在左括号大于右括号的情况下 两种括号都能添加dfsback(zre(,leftsum1,rightsum);//左括号递归dfsback(zre),leftsum,rightsum1);//右括号递归}}参考视频括号生成
方法二递归回溯
// 递归回溯ListString res new ArrayList(); // 结果集int n 0;public ListString generateParenthesis(int n) {StringBuffer str new StringBuffer();this.n n;// String zre ;//子结果集dfsback(str,0,0);return res;}public void dfsback(StringBuffer zre,int leftsum,int rightsum){if(leftsum n rightsum n) { //左右括号都达到了n 结束递归res.add(zre.toString());return;}if(leftsum n || leftsum rightsum ) return;//若左括号 大于n 或者 左括号数量大于右括号数量 不符合题目要求 结束递归剪枝zre.append(();dfsback(zre,leftsum1,rightsum);//左括号递归zre.deleteCharAt(zre.length()-1);//回溯zre.append());dfsback(zre,leftsum,rightsum1);//右括号递归zre.deleteCharAt(zre.length()-1);//回溯}
