萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第22题-括号生成

发表于 2022-09-04 | 分类于 力扣刷题 | 0 | 阅读次数 90

题目描述

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

样例

示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:
输入:n = 1
输出:["()"]

题目评估

知识点:字符串、动态规划、回溯、深度优先遍历、广度优先遍历
难度:中等

分析

使用深度优先遍历进行剪枝递归

Java代码题解

import java.util.LinkedList;
import java.util.List;

class Solution {

    public List<String> generateParenthesis(int n) {
        List<String> res = new LinkedList<>();
        generate("", n, n, res);
        return res;
    }

    /**
     * dfs
     * @param current 当前节点
     * @param left 左括号剩余
     * @param right 右括号剩余
     * @param result 结果集
     */
    private void generate(String current, int left, int right, List<String> result) {
        // 叶子节点
        if (left == 0 && right == 0) {
            result.add(current);
            return;
        }
        // 剪纸:右括号不可以剩得多
        if (right < left) {
            return;
        }
        // 遍历左子树
        if (left > 0) {
            generate(current + "(", left - 1, right, result);
        }
        // 遍历右子树
        if (right > 0) {
            generate(current + ")", left, right - 1, result);
        }
    }
}

复杂度分析

时间复杂度:O(22n)
空间复杂度:O(2n)

# 算法 # 程序设计 # 力扣
RabbitMQ基础学习
力扣第24题-两两交换链表中的节点
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持