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

2024-06-24 02:52
文章标签 leetcode 22 java 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。

相关文章

C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
Java五子棋之坐标校正

Java五子棋之坐标校正

上篇针对了Java项目中的解构思维，在这篇内容中我们不妨从整体项目中拆解拿出一个非常重要的五子棋逻辑实现：坐标校正，我们如何使漫无目的鼠标点击变得有序化和可控化呢？ 目录 一、从鼠标监听到获取坐标 1.MouseListener和MouseAdapter 2.mousePressed方法 二、坐标校正的具体实现方法 1.关于fillOval方法 2.坐标获取 3.坐标转换 4.坐
阅读更多...
Spring Cloud：构建分布式系统的利器

Spring Cloud：构建分布式系统的利器

引言 在当今的云计算和微服务架构时代，构建高效、可靠的分布式系统成为软件开发的重要任务。Spring Cloud 提供了一套完整的解决方案，帮助开发者快速构建分布式系统中的一些常见模式（例如配置管理、服务发现、断路器等）。本文将探讨 Spring Cloud 的定义、核心组件、应用场景以及未来的发展趋势。 什么是 Spring Cloud Spring Cloud 是一个基于 Spring
阅读更多...
Javascript高级程序设计(第四版)--学习记录之变量、内存

Javascript高级程序设计(第四版)--学习记录之变量、内存

原始值与引用值 原始值：简单的数据即基础数据类型，按值访问。 引用值：由多个值构成的对象即复杂数据类型，按引用访问。 动态属性 对于引用值而言，可以随时添加、修改和删除其属性和方法。 let person = new Object();person.name = 'Jason';person.age = 42;console.log(person.name,person.age);//'J
阅读更多...
java8的新特性之一（Java Lambda表达式）

java8的新特性之一（Java Lambda表达式）

1：Java8的新特性 Lambda 表达式： 允许以更简洁的方式表示匿名函数（或称为闭包）。可以将Lambda表达式作为参数传递给方法或赋值给函数式接口类型的变量。 Stream API： 提供了一种处理集合数据的流式处理方式，支持函数式编程风格。 允许以声明性方式处理数据集合（如List、Set等）。提供了一系列操作，如map、filter、reduce等，以支持复杂的查询和转
阅读更多...
Java面试八股之怎么通过Java程序判断JVM是32位还是64位

Java面试八股之怎么通过Java程序判断JVM是32位还是64位

怎么通过Java程序判断JVM是32位还是64位 可以通过Java程序内部检查系统属性来判断当前运行的JVM是32位还是64位。以下是一个简单的方法： public class JvmBitCheck {public static void main(String[] args) {String arch = System.getProperty("os.arch");String dataM
阅读更多...
详细分析Springmvc中的@ModelAttribute基本知识（附Demo）

详细分析Springmvc中的@ModelAttribute基本知识（附Demo）

目录 前言1. 注解用法1.1 方法参数1.2 方法1.3 类 2. 注解场景2.1 表单参数2.2 AJAX请求2.3 文件上传 3. 实战4. 总结 前言 将请求参数绑定到模型对象上，或者在请求处理之前添加模型属性 可以在方法参数、方法或者类上使用 一般适用这几种场景： 表单处理：通过 @ModelAttribute 将表单数据绑定到模型对象上预处理逻辑：在请求处理之前
阅读更多...
eclipse运行springboot项目，找不到主类

eclipse运行springboot项目，找不到主类

解决办法尝试了很多种，下载sts压缩包行不通。最后解决办法如图： help--->Eclipse Marketplace--->Popular--->找到Spring Tools 3---->Installed。
阅读更多...
JAVA读取MongoDB中的二进制图片并显示在页面上

JAVA读取MongoDB中的二进制图片并显示在页面上

1：Jsp页面： <td><img src="${ctx}/mongoImg/show"></td> 2：xml配置： <?xml version="1.0" encoding="UTF-8"?><beans xmlns="http://www.springframework.org/schema/beans"xmlns:xsi="http://www.w3.org/2001
阅读更多...
Java面试题：通过实例说明内连接、左外连接和右外连接的区别

Java面试题：通过实例说明内连接、左外连接和右外连接的区别

在 SQL 中，连接（JOIN）用于在多个表之间组合行。最常用的连接类型是内连接（INNER JOIN）、左外连接（LEFT OUTER JOIN）和右外连接（RIGHT OUTER JOIN）。它们的主要区别在于它们如何处理表之间的匹配和不匹配行。下面是每种连接的详细说明和示例。 表示例 假设有两个表：Customers 和 Orders。 Customers CustomerIDCus
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2