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

本文主要是介绍【经典算法】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

相关文章

Spring Security常见问题及解决方案

《SpringSecurity常见问题及解决方案》SpringSecurity是Spring生态的安全框架,提供认证、授权及攻击防护,支持JWT、OAuth2集成,适用于保护Spring应用,需配置... 目录Spring Security 简介Spring Security 核心概念1. ​Securit

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

SpringBoot+EasyPOI轻松实现Excel和Word导出PDF

《SpringBoot+EasyPOI轻松实现Excel和Word导出PDF》在企业级开发中,将Excel和Word文档导出为PDF是常见需求,本文将结合​​EasyPOI和​​Aspose系列工具实... 目录一、环境准备与依赖配置1.1 方案选型1.2 依赖配置(商业库方案)二、Excel 导出 PDF

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

spring中的@MapperScan注解属性解析

《spring中的@MapperScan注解属性解析》@MapperScan是Spring集成MyBatis时自动扫描Mapper接口的注解,简化配置并支持多数据源,通过属性控制扫描路径和过滤条件,利... 目录一、核心功能与作用二、注解属性解析三、底层实现原理四、使用场景与最佳实践五、注意事项与常见问题六

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Java中Arrays类和Collections类常用方法示例详解

《Java中Arrays类和Collections类常用方法示例详解》本文总结了Java中Arrays和Collections类的常用方法,涵盖数组填充、排序、搜索、复制、列表转换等操作,帮助开发者高... 目录Arrays.fill()相关用法Arrays.toString()Arrays.sort()A

Spring Boot Maven 插件如何构建可执行 JAR 的核心配置

《SpringBootMaven插件如何构建可执行JAR的核心配置》SpringBoot核心Maven插件,用于生成可执行JAR/WAR,内置服务器简化部署,支持热部署、多环境配置及依赖管理... 目录前言一、插件的核心功能与目标1.1 插件的定位1.2 插件的 Goals(目标)1.3 插件定位1.4 核

如何使用Lombok进行spring 注入

《如何使用Lombok进行spring注入》本文介绍如何用Lombok简化Spring注入,推荐优先使用setter注入,通过注解自动生成getter/setter及构造器,减少冗余代码,提升开发效... Lombok为了开发环境简化代码,好处不用多说。spring 注入方式为2种,构造器注入和setter