【剑指offer进阶|剑指offer85(生成匹配的括号)】题目:
正整数 n 代表生成括号的对数,请设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
1.输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
2.输入:n = 1
输出:["()"]
分析:
需要注意的是每一步的限制条件,第1个限制条件是左括号或者右括号不能超过n个,第2个限制条件是括号的匹配原则,也就是在任意步骤中已经生成的右括号的数目不能超过左括号的数目。
代码:
import java.util.LinkedList;
import java.util.List;
public class GenerateParenthesis {
public List generateParenthesis(int n) {
List result = new LinkedList<>();
helper(n,n,"",result);
return result;
}private void helper(int left, int right, String parenthesis, List result) {
if (left == 0&& right == 0){
result.add(parenthesis);
return;
}
//在生成一个括号时,只要已经生成的左括号的数目小于n个,就可能生成一个左括号,只要已经生成的右括号的数目少于已经生成的左括号数目就可能
//生成一个右括号
if (left > 0){
helper(left-1,right,parenthesis+"(",result);
}
if (left < right){
helper(left,right-1,parenthesis+")",result);
}
}
}
文章图片
推荐阅读
- 蓝桥杯|蓝桥杯——乳草的入侵
- #|算法Day6(广度优先搜索——最短路径问题)
- 论文解读|Query-Efficient Hard-label Black-box Attack: An Optimization-based Approach论文解读
- leetcode|《九日集训》(第九讲) 简单递归
- 人工智能|一文看懂CV中的注意力机制
- Java进阶|Java进阶学习——数据结构基础(二)
- 数据结构|小肥柴慢慢手写数据结构(C篇)(3-2 Stack应用举例)
- 数据结构|数据结构与算法入门前必读
- 数据结构|数据结构与算法一篇帮助你吃下KMP算法