flash网站开发,平台网站如何做推广方案,祥云网站推广,在线购物网站模板【题目描述】 数字 n 代表生成括号的对数#xff0c;请你设计一个函数#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 【题目链接】. - 力扣#xff08;LeetCode#xff09; 【解题代码】
package dp;import java.util.ArrayList;
import java.util.Arrays;
im…【题目描述】 数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。 【题目链接】. - 力扣LeetCode 【解题代码】
package dp;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class GenerateParenthesis {// 生成的有效括号字符串列表private ListString result;// StringBuilder变量用于生成有效括号字符串private StringBuilder sb;// 左括号数量private int count1;// 右括号数量private int count2;public static void main(String[] args) {long start System.currentTimeMillis();ListString result new GenerateParenthesis().generateParenthesis(3);System.out.println(result Arrays.toString(result.toArray()));System.out.println(函数执行时间: (System.currentTimeMillis() - start) MS);}public ListString generateParenthesis(int n) {// 初始化各个变量result new ArrayList();sb new StringBuilder();count1 0;count2 0;// 有效的括号字符串肯定第一个肯定是左括号generateParenthesis(n, 0);// 返回最终结果return result;}/*** 生成有效括号字符串* param n 有效括号组数量* type当前添加括号的类型0:左括号1右括号**/private void generateParenthesis(int n, int type) {// 当前添加左括号if (type 0) {sb.append(();count1;} else { // 当前添加右括号sb.append());count2;// 右括号数量等于n,说明新的有效括号组完成添加到结果类表中if (count2 n) {result.add(sb.toString());return;}}// 先处理左括号如果左括号数小于n添加左括号if (count1 n) {generateParenthesis(n, 0);// 回溯删除这一层递归函数里添加的左括号并将左括号数减一sb.deleteCharAt(sb.length() - 1);count1--;}// 再处理右括号右括号只能数量小于左括号时才能添加if (count2 count1) {generateParenthesis(n, 1);// 回溯删除这一层递归函数里添加的左括号并将左括号数减一sb.deleteCharAt(sb.length() - 1);count2--;}}}【解题思路】 分析题目仔细思考得到以下几个思路点 所谓有效括号就是最终的左括号数和右括号数一样右括号出现时前面至少有一个左括号能与之匹配也就是右括号的数量必须小于等于已有的左括号数。此道题目可以按照“回溯递归”的方式进行处理 即当前一步添加左括号-然后递归处理下一步-递归回到这一层-然后弹出左括号-然后添加右括号的-然后递归处理下一步。第一步肯定要添加左括号
【解题步骤】
首先要给解题类添加几个成员变量包括最终的结果字符串列表、存储过程字符串的StringBuilder、左右括号的数量等,并在构造函数中进行初始化 // 生成的有效括号字符串列表
private ListString result;
// StringBuilder变量用于生成有效括号字符串
private StringBuilder sb;
// 左括号数量
private int count1;
// 右括号数量
private int count2;public GenerateParenthesis(){// 初始化各个变量result new ArrayList();sb new StringBuilder();count1 0;count2 0;
} 定义一个“回溯递归”生成有效括号字符串的函数generateParenthesis传入参数包括有效括号组数量当前添加括号类型 /*** 生成有效括号字符串* param n 有效括号组数量* type当前添加括号的类型0:左括号1右括号**/
private void generateParenthesis(int n, int type) generateParenthesis函数内部第一步根据当前要添加括号类型存储对应的括号字符串并进行计数处理。如果是右括号则判断当前括号组数是否等于n如果等于则将当前字符串加入结果列表中 // 当前添加左括号
if (type 0) {sb.append(();count1;
} else { // 当前添加右括号sb.append());count2;// 右括号数量等于n,说明新的有效括号组完成添加到结果类表中if (count2 n) {result.add(sb.toString());return;}
} generateParenthesis函数内部第二步下一步递归添加左括号递归完毕后进行回溯 // 先处理左括号如果左括号数小于n添加左括号
if (count1 n) {generateParenthesis(n, 0);// 回溯删除这一层递归函数里添加的左括号并将左括号数减一sb.deleteCharAt(sb.length() - 1);count1--;
} generateParenthesis函数内部第二步下一步递归添加右括号递归完毕后进行回溯只有在右括号数量小于左括号的情况下才能添加右括号 // 再处理右括号右括号只能数量小于左括号时才能添加
if (count2 count1) {generateParenthesis(n, 1);// 回溯删除这一层递归函数里添加的左括号并将左括号数减一 sb.deleteCharAt(sb.length() - 1);count2--;
} 最后主函数generateParenthesis里调用递归函数从第一个左括号添加开始最后返回结果列表即可 public ListString generateParenthesis(int n) {// 有效的括号字符串肯定第一个肯定是左括号generateParenthesis(n, 0);// 返回最终结果return result;
}
【思考总结】
掌握“回溯”回溯算法也叫试探法它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走能进则进不能进则退回来换一条路再试大的算法框架定下来后 要细心找出业务里面的逻辑关键点这道理题的关键点就在于“只有在右括号数量小于左括号的情况下才能添加右括号”算法优化里要掌握所运用语言库的性能最优方式比如这里字符串处理使用了Java库里面的StringBuilder LeetCode解题之前一定不要看题解看了就“破功”了
