【经典算法】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。

相关文章

Java中流式并行操作parallelStream的原理和使用方法

Java中流式并行操作parallelStream的原理和使用方法

《Java中流式并行操作parallelStream的原理和使用方法》本文详细介绍了Java中的并行流（parallelStream）的原理、正确使用方法以及在实际业务中的应用案例,并指出在使用并行流... 目录Java中流式并行操作parallelStream0. 问题的产生1. 什么是parallelS
阅读更多...
C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
Linux join命令的使用及说明

Linux join命令的使用及说明

《Linuxjoin命令的使用及说明》`join`命令用于在Linux中按字段将两个文件进行连接,类似于SQL的JOIN,它需要两个文件按用于匹配的字段排序,并且第一个文件的换行符必须是LF,`jo... 目录一. 基本语法二. 数据准备三. 指定文件的连接key四.-a输出指定文件的所有行五.-o指定输出
阅读更多...
Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
C++中悬垂引用(Dangling Reference) 的实现

C++中悬垂引用(Dangling Reference) 的实现

《C++中悬垂引用(DanglingReference)的实现》C++中的悬垂引用指引用绑定的对象被销毁后引用仍存在的情况,会导致访问无效内存,下面就来详细的介绍一下产生的原因以及如何避免,感兴趣... 目录悬垂引用的产生原因1. 引用绑定到局部变量，变量超出作用域后销毁2. 引用绑定到动态分配的对象，对象
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
一篇文章彻底搞懂macOS如何决定java环境

一篇文章彻底搞懂macOS如何决定java环境

《一篇文章彻底搞懂macOS如何决定java环境》MacOS作为一个功能强大的操作系统,为开发者提供了丰富的开发工具和框架,下面：本文主要介绍macOS如何决定java环境的相关资料,文中通过代码... 目录方法一：使用 which命令方法二：使用 Java_home工具（Apple 官方推荐）那问题来了，
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2