当前位置: 首页 > news >正文

每日一题——括号生成

题解

给定 n 对括号,要求编写一个函数生成所有合法的括号组合。合法的括号组合必须满足每一对括号中的左括号必须先于右括号,并且括号数量必须平衡。

题目描述

输入:

  • 一个整数 n,表示括号的对数,满足 0 ≤ n ≤ 10 0 \leq n \leq 10 0n10

输出:

  • 返回一个包含所有合法括号组合的字符串数组。

示例1

输入:

1

输出:

["()"]

示例2

输入:

2

输出:

["(())", "()()"]

题解思路

这个问题是一个典型的递归回溯问题。我们可以通过递归来生成所有可能的括号组合。具体步骤如下:

  1. 用递归函数生成括号的组合。
  2. 每次递归调用时,有两个选择:
    • 如果左括号还没有用完,就添加一个左括号 '('
    • 如果右括号的数量小于左括号的数量,且右括号还没有用完,就添加一个右括号 ')'
  3. 当左右括号的数量都达到了 n 时,表示一个合法的组合已经完成,将其加入结果数组。

时间复杂度和空间复杂度

  • 时间复杂度:O( 2 n 2^n 2n),因为每一层递归有两种选择(添加左括号或右括号)。
  • 空间复杂度:O( n n n),由于递归调用栈的深度是 n,每次递归都在 2n 长度的字符串上操作。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 深度优先搜索(DFS)函数,用于生成所有有效的括号组合* * @param left 左括号的数量* @param right 右括号的数量* @param ret 存储所有生成的括号组合的数组* @param path 当前路径,即当前生成的括号组合* @param n 括号对数* @param returnSize 当前已生成的括号组合数量*/
void DFS(int left, int right, char **ret, char* path, int n, int *returnSize) {// 如果左括号和右括号的数量都等于 n,说明生成了一个有效的括号组合if (left == n && right == n) {// 为当前括号组合分配内存,长度为 2n + 1(包括字符串终止符)ret[*returnSize] = malloc(sizeof(char) * (2 * n + 1));if (ret[*returnSize] == NULL) {printf("Memory allocation failed\n");exit(1);}// 将当前路径复制到结果数组中for (int i = 0; i < 2 * n; i++) {ret[*returnSize][i] = path[i];}ret[*returnSize][2 * n] = '\0'; // 添加字符串终止符// 增加已生成的括号组合数量(*returnSize)++;return;}// 如果左括号的数量小于 n,可以添加一个左括号if (left < n) {path[left + right] = '('; // 在当前路径中添加左括号DFS(left + 1, right, ret, path, n, returnSize); // 递归调用,继续生成}// 如果右括号的数量小于左括号的数量且小于 n,可以添加一个右括号if (right < left && right < n) {path[left + right] = ')'; // 在当前路径中添加右括号DFS(left, right + 1, ret, path, n, returnSize); // 递归调用,继续生成}
}/*** 主函数,生成所有有效的括号组合* * @param n 括号对数* @param returnSize 返回的括号组合数量* @return 存储所有有效括号组合的数组*/
char** generateParenthesis(int n, int *returnSize) {// 预分配足够大的空间存储结果,这里假设最多有 2000 种组合char** ret = (char**)malloc(sizeof(char*) * 2000);if (ret == NULL) {printf("Memory allocation failed\n");exit(1);}*returnSize = 0; // 初始化返回的括号组合数量为 0// 为当前路径分配内存,长度为 2n + 1(包括字符串终止符)char* path = (char*)malloc(sizeof(char) * (2 * n + 1));if (path == NULL) {printf("Memory allocation failed\n");exit(1);}// 调用 DFS 函数生成所有有效的括号组合DFS(0, 0, ret, path, n, returnSize);// 释放当前路径的内存free(path);return ret;
}

解析

  1. DFS函数的递归逻辑:

    • DFS(left, right, ret, str, n, returnSize)是递归的核心函数,leftright 分别表示已使用的左括号和右括号数量。
    • 如果leftright都达到了n,就将当前字符串str(存放括号组合)存入ret数组。
    • 如果left < n,我们可以继续添加左括号。
    • 如果right < left,我们可以继续添加右括号。
  2. 空间分配:

    • 结果数组ret被分配了2000个空间,可以容纳所有合法组合(理论上可能达到O(4^n)个组合,但实际上不会达到这么多)。
    • 每个合法的括号组合是一个长度为2n的字符串,因此str的长度是2n
  3. 返回值:

    • ret返回存放合法括号组合的数组,returnSize返回合法组合的数量。

总结

通过递归的方式,我们能够高效地生成所有合法的括号组合。递归回溯方法简洁而直观,适合解决此类组合生成的问题。

相关文章:

每日一题——括号生成

题解 给定 n 对括号&#xff0c;要求编写一个函数生成所有合法的括号组合。合法的括号组合必须满足每一对括号中的左括号必须先于右括号&#xff0c;并且括号数量必须平衡。 题目描述 输入&#xff1a; 一个整数 n&#xff0c;表示括号的对数&#xff0c;满足 0 ≤ n ≤ 1…...

实操部署DeepSeek,添加私有知识库

目录 一、环境介绍 PowerShell版本&#xff1a; wsl版本&#xff1a; 虚拟机版本&#xff1a; 本机IP&#xff1a; 虚拟机IP&#xff1a; 容器宿主机IP&#xff08;host.docker.internal&#xff09;&#xff1a; Docker版本&#xff1a; Docker Compose版本&#xff…...

宜宾数字经济新标杆:树莓集团赋能区域产业转型升级

树莓集团在宜宾成为数字经济新标杆&#xff0c;有力地赋能区域产业转型升级。在传统产业数字化转型方面&#xff0c;树莓集团针对宜宾的制造业企业&#xff0c;引入工业互联网技术。 通过搭建工业互联网平台&#xff0c;实现企业生产设备的联网和数据采集&#xff0c;帮助企业…...

8.大规模推荐系统的实现

接下来我们将学习大规模推荐系统的实现。在实际应用中&#xff0c;推荐系统需要处理海量数据&#xff0c;并在短时间内生成推荐结果。这要求我们在设计和实现推荐系统时&#xff0c;考虑到数据的分布式存储与处理、计算的高效性和系统的可扩展性。在这一课中&#xff0c;我们将…...

第三届通信网络与机器学习国际学术会议(CNML 2025)

在线投稿&#xff1a; 学术会议-学术交流征稿-学术会议在线-艾思科蓝 通信网络机器学习 通信理论 通信工程 计算机网络和数据通信 信息分析和基础设施 通信建模理论与实践 无线传感器和通信网络 云计算与物联网 网络和数据安全 光电子学和光通信 无线/移动通信和技术 智能通信…...

MySQL两阶段提交策略

书接上一篇文章&#xff0c;MySQL通过不同的策略来保证事务的ACID&#xff1a;原子性、一致性、隔离性、持久性&#xff0c;通过锁机制实现隔离性&#xff0c;通过redoundobinlog三种日志实现事务的原子性、一致性和持久性。 本文主要讲MySQL的持久性的一个实现机制-两阶段提交…...

uniapp商城之购物车模块

文章目录 一、列表渲染二、删除单品1.封装删除API2.按钮绑定事件三、修改单品数量1.复用步进器组件2.属性和事件的绑定3.接口封装4.调用接口四、修改商品选中/全选1.单品选中绑定事件调用修改API2.计算全选状态3.绑定事件调用全选API并渲染单品选中状态五、底部结算信息1.计算选…...

STM32_USART通用同步/异步收发器

目录 背景 程序 STM32浮空输入的概念 1.基本概念 2. STM32浮空输入的特点 3. STM32浮空输入的应用场景 STM32推挽输出详解 1. 基本概念 2. 工作原理 3. 应用场景 使能外设时钟 TXE 和 TC的区别 USART_IT_TXE USART_IT_TC 使能串口外设 中断处理函数 背景 单片…...

python自动化测试之Pytest框架之YAML详解以及Parametrize数据驱动!

一、YAML详解 YAML是一种数据类型&#xff0c;它能够和JSON数据相互转化&#xff0c;它本身也是有很多数据类型可以满足我们接口 的参数类型&#xff0c;扩展名可以是.yml或.yaml 作用&#xff1a; 1.全局配置文件 基础路径&#xff0c;数据库信息&#xff0c;账号信息&…...

python基础入门:6.3异常处理机制

Python异常处理全面指南&#xff1a;构建健壮程序的关键技术 # 完整异常处理模板 def process_file(file_path):"""文件处理示例函数"""file Nonetry:file open(file_path, r, encodingutf-8)data json.load(file)if not data:raise EmptyDa…...

Mybatis快速入门与核心知识总结

Mybatis 1. 实体类&#xff08;Entity Class&#xff09;1.1 实体类的定义1.2 简化编写1.2.1 Data1.2.2 AllArgsConstructor1.2.3 NoArgsConstructor 2. 创建 Mapper 接口2.1 Param2.2 #{} 占位符2.3 SQL 预编译 3. 配置 MyBatis XML 映射文件&#xff08;可选&#xff09;3.1 …...

畅聊deepseek-r1,SiliconFlow 硅基流动注册+使用

文章目录 SiliconFlow 硅基流动注册使用注册创建API密钥使用网页端使用代码调用api调用支持的模型 SiliconFlow 硅基流动注册使用 注册 硅基流动官网 https://cloud.siliconflow.cn/i/XcgtUixn 注册流程 切换中文 ​ 邀请码&#xff1a; XcgtUixn 创建API密钥 账户管理 --&g…...

一个基于ESP32S3和INMP441麦克风实现音频强度控制RGB灯带律动的代码及效果展示

一个基于ESP32S3和INMP441麦克风实现音频强度控制RGB灯带律动的代码示例&#xff0c;使用Arduino语言&#xff1a; 硬件连接 INMP441 VCC → ESP32的3.3VINMP441 GND → ESP32的GNDINMP441 SCK → ESP32的GPIO 17INMP441 WS → ESP32的GPIO 18INMP441 SD → ESP32的GPIO 16RG…...

Springboot 中如何使用Sentinel

在 Spring Boot 中使用 Sentinel 非常方便&#xff0c;Spring Cloud Alibaba 提供了 spring-cloud-starter-alibaba-sentinel 组件&#xff0c;可以快速将 Sentinel 集成到你的 Spring Boot 应用中&#xff0c;并利用其强大的流量控制和容错能力。 下面是一个详细的步骤指南 …...

访问Elasticsearch服务 curl ip 端口可以 浏览器不可以

LINUX学习 在虚拟机上面的linux上面用docker 部署Elasticsearch项目后&#xff0c;在linux系统内部用curl ip 端口地址的形式可以访问到Elasticsearch。可以返回数据。 但是在本机的浏览器中输入ip 端口&#xff0c;会报错&#xff0c;找不到服务。 ping 和 trelnet均不通。 …...

Curser2_解除机器码限制

# Curser1_无限白嫖试用次数 文末有所需工具下载地址 Cursor Device ID Changer 一个用于修改 Cursor 编辑器设备 ID 的跨平台工具集。当遇到设备 ID 锁定问题时&#xff0c;可用于重置设备标识。 功能特性 ✨ 支持 Windows 和 macOS 系统&#x1f504; 自动生成符合格式的…...

人工智能与低代码如何重新定义企业数字化转型?

引言&#xff1a;数字化转型的挑战与机遇 在全球化和信息化的浪潮中&#xff0c;数字化转型已经成为企业保持竞争力和创新能力的必经之路。然而&#xff0c;尽管“数字化”听上去是一个充满未来感的词汇&#xff0c;落地的过程却往往充满困难。 首先&#xff0c;传统开发方式…...

arkTS基础

arkTS基础 // 变量声明 let hi: string hello; hi hello,world; // 常量声明 const hi: string hello;// ArkTS是一种静态类型语言&#xff0c;所有数据的类型都必须在编译时确定 // 如果一个变量或常量的声明包含了初始值&#xff0c;那么开发者就不需要显式指定其类型。…...

C++20中的std::atomic_ref

一、std::atomic_ref 我们在学习C11后的原子操作时&#xff0c;都需要提前定义好std::atomic变量&#xff0c;然后才可以在后续的应用程序中进行使用。原子操作的优势在很多场合下优势非常明显&#xff0c;所以这也使得很多开发者越来习惯使用原子变量。 但是&#xff0c;在实…...

四、自然语言处理_08Transformer翻译任务案例

0、前言 在Seq2Seq模型的学习过程中&#xff0c;做过一个文本翻译任务案例&#xff0c;多轮训练后&#xff0c;效果还算能看 Transformer作为NLP领域的扛把子&#xff0c;对于此类任务的处理会更为强大&#xff0c;下面将以基于Transformer模型来重新处理此任务&#xff0c;看…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...

macOS 终端智能代理检测

&#x1f9e0; 终端智能代理检测&#xff1a;自动判断是否需要设置代理访问 GitHub 在开发中&#xff0c;使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新&#xff0c;例如&#xff1a; fatal: unable to access https://github.com/ohmyzsh/oh…...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...