【经典算法】LeetCode 22括号生成(Java/C/Python3/Go实现含注释说明,中等)

2024-06-24 02:52
文章标签 java leetcode 算法 实现 go 中等 生成 说明 经典 括号 python3 注释 22

本文主要是介绍【经典算法】LeetCode 22括号生成(Java/C/Python3/Go实现含注释说明,中等)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  • 作者主页： 🔗进朱者赤的博客

  • 精选专栏：🔗经典算法

  • 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）

  • ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的关注，持续更新🤞
    ————————————————-

首先，请注意题目链接有误，您提供的链接是LeetCode 14，但题目描述应该是关于LeetCode 22（括号生成）。以下是按照您提供的格式和要求，针对LeetCode 22题目“括号生成”的多种语言实现方式。

目录

  • 题目描述
  • 思路及实现
    • 方式一：回溯法
      • 思路
      • 代码实现
        • Java版本
        • C语言版本
        • Python3版本
        • Go语言版本
      • 复杂度分析
    • 方式二：动态规划
        • 思路**
        • **Java实现**
        • **C++实现**
        • **Python3实现**
        • **Go实现**
      • 复杂度分析
      • 总结
  • 相似题目

  • 标签(题目类型)：动态规划

题目描述

给定 n 对括号，生成所有由 n 对括号组成的合法（有效）括号组合。例如，给出 n = 3，生成结果为：
["((()))","(()())","(())()","()(())","()()()"
]

思路及实现

方式一：回溯法

思路

使用回溯法来递归地生成所有可能的括号组合，并在递归过程中检查括号的有效性。

代码实现

Java版本
import java.util.ArrayList;
import java.util.List;public class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(result, "", 0, 0, n);return result;}private void backtrack(List<String> result, String current, int open, int close, int max) {if (current.length() == max * 2) {result.add(current);return;}if (open < max) {backtrack(result, current + "(", open + 1, close, max);}if (close < open) {backtrack(result, current + ")", open, close + 1, max);}}
}

说明：使用回溯法，在递归过程中跟踪已打开的括号数量（open）和已关闭的括号数量（close）。只有当open小于max时，才添加左括号；只有当close小于open时，才添加右括号。

C语言版本
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>void backtrack(char*** result, int* returnSize, char* current, int open, int close, int max, int* currentIndex) {if (strlen(current) == max * 2) {char* temp = (char*)malloc(max * 2 + 1);strcpy(temp, current);result[*returnSize] = temp;(*returnSize)++;return;}if (open < max) {current[(*currentIndex)++] = '(';backtrack(result, returnSize, current, open + 1, close, max, currentIndex);(*currentIndex)--;}if (close < open) {current[(*currentIndex)++] = ')';backtrack(result, returnSize, current, open, close + 1, max, currentIndex);(*currentIndex)--;}
}char** generateParenthesis(int n, int* returnSize) {char* current = (char*)malloc((n * 2 + 1) * sizeof(char));char** result = (char**)malloc(10000 * sizeof(char*)); // Assuming max number of results*returnSize = 0;int currentIndex = 0;backtrack(result, returnSize, current, 0, 0, n, &currentIndex);free(current); // Don't forget to free the allocated memoryreturn result;
}

说明：在C语言中，我们使用动态内存分配来存储结果和当前路径。同样，我们跟踪已打开的括号和已关闭的括号数量。

Python3版本
class Solution:def generateParenthesis(self, n: int) -> List[str]:def backtrack(current, open, close, result):if len(current) == 2 * n:result.append(current)returnif open < n:backtrack(current + '(', open + 1, close, result)if close < open:backtrack(current + ')', open, close + 1, result)result = []backtrack("", 0, 0, result)return result

说明：Python版本相对简洁，利用递归和字符串拼接来生成所有可能的

Go语言版本
package mainimport ("fmt""strconv"
)func generateParenthesis(n int) []string {var result []stringbacktrack(&result, "", 0, 0, n)return result
}func backtrack(result *[]string, current string, open, close, max int) {if len(current) == max*2 {*result = append(*result, current)return}if open < max {backtrack(result, current+"(", open+1, close, max)}if close < open {backtrack(result, current+")", open, close+1, max)}
}func main() {n := 3res := generateParenthesis(n)for _, s := range res {fmt.Println(s)}
}

说明：在Go语言中，我们使用切片来存储结果，并通过backtrack函数递归地生成所有可能的括号组合。

复杂度分析

对于所有语言版本，其时间复杂度和空间复杂度都是相同的。

  • 时间复杂度：O(2^n * n)，因为对于n对括号，左括号有n个位置可以放置，每个位置有放和不放两种选择，所以总共有2^n种可能，但是每种可能都需要O(n)的时间来生成和验证括号串。
  • 空间复杂度：O(n * 2^n)，在最坏情况下，即所有可能的括号串都需要被存储时，我们需要O(n * 2^n)的空间来存储这些串。在递归过程中，我们还需要额外的栈空间来保存递归调用的上下文，但这部分空间相对于结果空间来说较小，因此通常忽略不计。

方式二：动态规划

（由于动态规划在生成所有可能的组合时不如回溯法直观，通常用于求解某个最优解问题，而不是直接生成所有解，因此这里不给出动态规划的直接实现。但我们可以理解其思路是构建一个表格，其中每个单元格存储了给定括号对数量时的所有有效括号组合。）

当然，以下是使用Markdown语言书写的之前提到的四种编程语言的实现示例，以及关于动态规划结合回溯的额外说明：

思路**

在方式二中，我们将动态规划（DP）与回溯算法结合使用。这种方法的核心思想是，先利用动态规划预处理一些信息，在回溯过程中利用这些信息来减少无效搜索。然而，在生成有效括号这个问题中，由于问题的特殊性，我们实际上可以通过简单的条件判断来实现隐式剪枝，而无需显式构建动态规划表。

Java实现
public class Solution {public List<String> generateParenthesis(int n) {List<String> result = new ArrayList<>();backtrack(result, "", 0, 0, n);return result;}private void backtrack(List<String> result, String current, int open, int close, int max) {if (current.length() == max * 2) {result.add(current);return;}if (open < max) {backtrack(result, current + "(", open + 1, close, max);}if (close < open) {backtrack(result, current + ")", open, close + 1, max);}}
}
C++实现
#include <vector>
#include <string>using namespace std;class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> result;backtrack(result, "", 0, 0, n);return result;}private:void backtrack(vector<string>& result, string current, int open, int close, int max) {if (current.size() == max * 2) {result.push_back(current);return;}if (open < max) {backtrack(result, current + "(", open + 1, close, max);}if (close < open) {backtrack(result, current + ")", open, close + 1, max);}}
};
Python3实现
def generateParenthesis(n):def backtrack(path, open_count, close_count, res):if len(path) == 2 * n:res.append(path)returnif open_count < n:backtrack(path + '(', open_count + 1, close_count, res)if close_count < open_count:backtrack(path + ')', open_count, close_count + 1, res)res = []backtrack("", 0, 0, res)return res
Go实现
package mainimport "fmt"func generateParenthesis(n int) []string {var result []stringbacktrack(&result, "", 0, 0, n)return result
}func backtrack(result *[]string, current string, open, close, max int) {if len(current) == max*2 {*result = append(*result, current)return}if open < max {backtrack(result, current+"(", open+1, close, max)}if close < open {backtrack(result, current+")", open, close+1, max)}
}func main() {res := generateParenthesis(3)for _, s := range res {fmt.Println(s)}
}

复杂度分析

  • 时间复杂度：

由于需要生成并检查所有可能的括号序列（包括无效的），算法在最坏情况下可能会检查接近 2^n 个序列，其中 n 是括号对的数量。
然而，由于算法中使用了隐式剪枝（即确保在任何前缀中左括号数量不少于右括号数量），实际检查的序列数量会远少于 2^n。
因此，虽然时间复杂度是指数级的，但由于剪枝的存在，实际运行时间会比 O(2^n) 要好。
空间复杂度：

  • 空间复杂度
    主要由递归栈的深度和存储结果的列表决定。
    递归栈的深度在最坏情况下为 O(n)，其中 n 是括号对的数量。
    存储结果的列表最终会包含所有有效的括号序列，其数量是卡特兰数 C_n，渐进复杂度为 O(4^n / (n^(3/2) * sqrt(π)))，但算法运行时的空间复杂度主要由递归栈决定，为 O(n)。
    简而言之，时间复杂度是指数级的但剪枝有效，空间复杂度为 O(n)。

关于动态规划结合回溯

在更复杂的问题中，动态规划表可以用来存储子问题的解，以减少重复计算，并在回溯过程中提供快速查找。然而，在本问题中，由于括号的有效性检查相对简单，我们直接通过递归函数中的参数进行条件判断，实现了高效的回溯，无需额外的动态规划表。这种方法称为“隐式剪枝”，它避免了不必要的搜索，从而提高了算法效率。

总结

方式优点缺点时间复杂度空间复杂度
方式一（回溯法）直观易理解，可以生成所有解可能产生大量重复计算（可通过记忆化搜索优化）O(2^n * n)O(n * 2^n)
方式二（动态规划）（理论上可以优化，但不适合直接生成所有解）实现复杂，不直观O(2^n) 要好。
O(n)

相似题目

相似题目难度链接
LeetCode 32. 最长有效括号困难LeetCode-32
LeetCode 20. 有效的括号简单LeetCode-20

注意：相似题目链接指向的是英文LeetCode，如果需要中文版本，请替换为leetcode-cn.com。

欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界

  • 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等

  • —⬇️欢迎关注下面的公众号：进朱者赤，认识不一样的技术人。⬇️—

这篇关于【经典算法】LeetCode 22括号生成(Java/C/Python3/Go实现含注释说明,中等)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1088978。

相关文章

JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
Zookeeper安装和配置说明

Zookeeper安装和配置说明

一、Zookeeper的搭建方式 Zookeeper安装方式有三种，单机模式和集群模式以及伪集群模式。 ■ 单机模式：Zookeeper只运行在一台服务器上，适合测试环境； ■ 伪集群模式：就是在一台物理机上运行多个Zookeeper 实例； ■ 集群模式：Zookeeper运行于一个集群上，适合生产环境，这个计算机集群被称为一个“集合体”（ensemble） Zookeeper通过复制来实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2