当前位置:网站首页>每日一题-括号生成-0721
每日一题-括号生成-0721
2022-08-05 05:17:00 【菜鸡程序媛】
题目
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
- 输入:n = 3
- 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
思路
- 采用深度优先遍历的方式,先把左括号消耗完,再匹配右括号;右括号走到头的时候,开始回溯
- 当left>right的时候,记得剪枝(因为左括号肯定是先出现的)
代码
public List<String> generateParenthesis(int n) {
List<String> res = new LinkedList<>();
if(n <= 0)
return res;
recur(n, n, new StringBuilder(), res);
return res;
}
private void recur(int left, int right, StringBuilder sb, List<String> res){
if(left == 0 && right == 0){
res.add(sb.toString());
return;
}
// 这个时候要剪枝
if(left > right)
return;
if(left > 0){
sb.append('(');
recur(left - 1, right, sb, res);
sb.deleteCharAt(sb.length() - 1); // 回溯
}
if(right > 0){
sb.append(')');
recur(left, right - 1, sb, res);
sb.deleteCharAt(sb.length() - 1);
}
}
边栏推荐
猜你喜欢
随机推荐
CVPR2020 - 自校准卷积
用GAN的方法来进行图片匹配!休斯顿大学提出用于文本图像匹配的对抗表示学习,消除模态差异!
ECCV2022 | RU&谷歌提出用CLIP进行zero-shot目标检测!
MySQL主从复制—有手就能学会的MySQL集群搭建教程
网络ID,广播地址,掩码位数计算
It turns out that the MAE proposed by He Yuming is still a kind of data enhancement
SQL (2) - join window function view
伪RTOS-ProroThread在CH573芯片上的移植
framebuffer应用编程及文字显示(1)
idea 快速日志
MaskDistill - Semantic segmentation without labeled data
【UiPath2022+C#】UiPath 数据操作
六、请求处理—获取请求参数系列注解是怎样工作的?
You should write like this
CVPR 2020 - 频谱正则化
[Pytorch study notes] 10. How to quickly create your own Dataset dataset object (inherit the Dataset class and override the corresponding method)
七、请求处理——Map、Model类型参数处理原理
Redis设计与实现(第一部分):数据结构与对象
【nodejs】第一章:nodejs架构
【UiPath2022+C#】UiPath 练习和解决方案-变量、数据类型和控制流程