力扣题目解析--括号生成

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

  • 1 <= n <= 8

代码展示 

class Solution {
public:vector<string> generateParenthesis(int n) {string sb;vector<string> res;dfs(n, sb, res, 0, 0);return res;}private:void dfs(int n, string& sb, vector<string>& res, int left, int right) {if (left == n && right == n) {res.push_back(sb);}if (left < n) {sb += "(";dfs(n, sb, res, left + 1, right);sb.pop_back();}if (right < left) {sb += ")";dfs(n, sb, res, left, right + 1);sb.pop_back();}}
};

写者心得 

这段代码使用的是回溯的思想，代码是通过学习力扣题解里边儿的思想在改进过来的，这种思想其实和双指针是一脉相承的

这个题目它的逻辑过程是这个样子的：

n=0:''
n=1:   排列组合
        (0):
            ('')----> ()
n=2:  排列组合
       (0)+1: 
            ('')+()----> ()()
       (1)+0: 
            (())+''----->(())
n=3: 排列组合
       (0)+2: 
            ('')+()() ----> ()()()
            ('')+(())----->()(())
       (1)+1:
            (())+()------> (())()
       (2)+0:
            (()())+'' ----> (()())
            ((()))+''----->((()))
n=4: 排列组合
       (0)+3:
            ('')+()()()--->()()()()
            ('')+()(())--->()()(())
            ('')+ (())()--->()(())()
            ('')+(()())--->()(()())
            ('')+((()))--->()((()))
       (1)+2:
            (())+()()--->(())()()
            (())+(())--->(())(())
       (2)+1:
            (()())+()---->(()())()
            ((()))+()---->((()))()
       (3)+0:
            (()()())+''---->(()()())
            (()(()))+''---->(()(()))
            ((())())+''---->((())())
            ((()()))+''---->((()()))
            (((())))+''---->(((())))

调试过程解析

1. 初始化和首次调用
  • generateParenthesis(int n):
    • 初始化一个空字符串 sb 和一个空的字符串向量 res。
    • 调用 dfs(n, sb, res, 0, 0)，开始递归搜索。
2. 第一次递归调用 dfs(n, sb, res, 0, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "", res = [], left = 0, right = 0
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：满足，left = 0 < 2。
    • 更新 sb += "("，sb = "("。
    • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "(", res, 1, 0)。
3. 第二次递归调用 dfs(2, "(", res, 1, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(", res = [], left = 1, right = 0`
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：满足，left = 1 < 2。
    • 更新 sb += "("，sb = "(("。
    • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "((", res, 2, 0)。
4. 第三次递归调用 dfs(2, "((", res, 2, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "((", res = [], left = 2, right = 0
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：不满足，left = 2。
    • 检查条件 right < left：满足，right = 0 < 2。
    • 更新 sb += ")"，sb = "(()"。
    • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "(()", res, 2, 1)。
5. 第四次递归调用 dfs(2, "(()", res, 2, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(()", res = [], left = 2, right = 1
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：不满足，left = 2。
    • 检查条件 right < left：满足，right = 1 < 2。
    • 更新 sb += ")"，sb = "(())"。
    • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "(())", res, 2, 2)。
6. 第五次递归调用 dfs(2, "(())", res, 2, 2)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(())", res = [], left = 2, right = 2
    • 检查条件 left == n && right == n：满足，left = 2 且 right = 2。
    • 将 sb 添加到 res 中，res = ["(())"]。
    • 返回上一级递归调用。
7. 返回到第四次递归调用 dfs(2, "(()", res, 2, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(()", res = ["(())"], left = 2, right = 1
    • 执行 sb.pop_back()，sb = "(()"。
    • 返回上一级递归调用。
8. 返回到第三次递归调用 dfs(2, "((", res, 2, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "((", res = ["(())"], left = 2, right = 0
    • 执行 sb.pop_back()，sb = "("。
    • 返回上一级递归调用。
9. 返回到第二次递归调用 dfs(2, "(", res, 1, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(", res = ["(())"], left = 1, right = 0
    • 检查条件 right < left：满足，right = 0 < 1。
    • 更新 sb += ")"，sb = "()"。
    • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "()", res, 1, 1)。
10. 第六次递归调用 dfs(2, "()", res, 1, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()", res = ["(())"], left = 1, right = 1
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：满足，left = 1 < 2。
    • 更新 sb += "("，sb = "()("。
    • 递归调用 dfs(n, sb, res, left + 1, right)，即 dfs(2, "()(", res, 2, 1)。
11. 第七次递归调用 dfs(2, "()(", res, 2, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()(", res = ["(())"], left = 2, right = 1
    • 检查条件 left == n && right == n：不满足，继续。
    • 检查条件 left < n：不满足，left = 2。
    • 检查条件 right < left：满足，right = 1 < 2。
    • 更新 sb += ")"，sb = "()(())"。
    • 递归调用 dfs(n, sb, res, left, right + 1)，即 dfs(2, "()(())", res, 2, 2)。
12. 第八次递归调用 dfs(2, "()(())", res, 2, 2)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()(())", res = ["(())"], left = 2, right = 2
    • 检查条件 left == n && right == n：满足，left = 2 且 right = 2。
    • 将 sb 添加到 res 中，res = ["(())", "()()"]。
    • 返回上一级递归调用。
13. 返回到第七次递归调用 dfs(2, "()(", res, 2, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()(", res = ["(())", "()()"], left = 2, right = 1
    • 执行 sb.pop_back()，sb = "()("。
    • 返回上一级递归调用。
14. 返回到第六次递归调用 dfs(2, "()", res, 1, 1)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()", res = ["(())", "()()"], left = 1, right = 1
    • 执行 sb.pop_back()，sb = "()"。
    • 返回上一级递归调用。
15. 返回到第二次递归调用 dfs(2, "(", res, 1, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "()", res = ["(())", "()()"], left = 1, right = 0
    • 执行 sb.pop_back()，sb = "("。
    • 返回上一级递归调用。
16. 返回到第一次递归调用 dfs(2, "", res, 0, 0)
  • dfs(int n, string& sb, vector<string>& res, int left, int right):
    • 参数：n = 2, sb = "(", res = ["(())", "()()"], left = 0, right = 0
    • 执行 sb.pop_back()，sb = ""。
    • 返回上一级调用。

 

代码的逐行解释 

vector<string> generateParenthesis(int n) {string sb;vector<string> res;dfs(n, sb, res, 0, 0);return res;}
  • vector<string> generateParenthesis(int n)：定义了 generateParenthesis 函数，它接受一个整数 n 作为参数，并返回一个 vector<string> 类型的对象，该对象包含所有合法的括号组合。
  • string sb;：初始化一个空字符串 sb，用于构建当前正在生成的括号组合。
  • vector<string> res;：初始化一个空的字符串向量 res，用于存储所有合法的括号组合。
  • dfs(n, sb, res, 0, 0);：调用私有成员函数 dfs，开始深度优先搜索。n 是目标括号对的数量，sb 是当前正在构建的字符串，res 是存储结果的向量，0, 0 分别表示当前已经添加的左括号和右括号的数量。
  • return res;：返回存储所有合法括号组合的向量 res。
private:

这行指定了接下来定义的成员函数或变量是私有的（private），意味着它们只能在类的内部被访问

    void dfs(int n, string& sb, vector<string>& res, int left, int right) {
  • void dfs(int n, string& sb, vector<string>& res, int left, int right)：定义了私有成员函数 dfs，它接受五个参数：
    • int n：目标括号对的数量。
    • string& sb：引用传递的当前正在构建的字符串。
    • vector<string>& res：引用传递的存储结果的向量。
    • int left：当前已经添加的左括号的数量。
    • int right：当前已经添加的右括号的数量。
        if (left == n && right == n) {res.push_back(sb);}
  • if (left == n && right == n)：检查当前已经添加的左括号和右括号的数量是否都达到了目标数量 n。
  • res.push_back(sb);：如果条件满足，说明当前构建的字符串 sb 是一个合法的括号组合，将其添加到结果向量 res 中。
        if (left < n) {sb += "(";dfs(n, sb, res, left + 1, right);sb.pop_back();}
  • if (left < n)：检查当前已经添加的左括号数量是否小于目标数量 n。
  • sb += "(";：如果条件满足，向当前字符串 sb 添加一个左括号。
  • dfs(n, sb, res, left + 1, right);：递归调用 dfs 函数，增加左括号的数量。
  • sb.pop_back();：在递归调用返回后，移除最后一个字符（即刚刚添加的左括号），以便尝试其他可能的组合。
        if (right < left) {sb += ")";dfs(n, sb, res, left, right + 1);sb.pop_back();}
  • if (right < left)：检查当前已经添加的右括号数量是否小于左括号的数量。这个条件确保了不会生成非法的括号组合（即右括号的数量不能超过左括号的数量）。
  • sb += ")";：如果条件满足，向当前字符串 sb 添加一个右括号。
  • dfs(n, sb, res, left, right + 1);：递归调用 dfs 函数，增加右括号的数量。
  • sb.pop_back();：在递归调用返回后，移除最后一个字符（即刚刚添加的右括号），以便尝试其他可能的组合。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/473313.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

使用 Go 实现将任何网页转化为 PDF

使用 Go 实现将任何网页转化为 PDF

在许多应用场景中&#xff0c;可能需要将网页内容转化为 PDF 格式&#xff0c;比如保存网页内容、生成报告、或者创建网站截图。使用 Go 编程语言&#xff0c;结合一些现有的库&#xff0c;可以非常方便地实现这一功能。本文将带你一步一步地介绍如何使用 Go 语言将任何网页转换…
阅读更多...
ASP.NET 部署到IIS，访问其它服务器的共享文件 密码设定

ASP.NET 部署到IIS，访问其它服务器的共享文件 密码设定

asp.net 修改上面的 IIS需要在 配置文件 添加如下内容 》》》web.config <system.web><!--<identity impersonate"true"/>--><identity impersonate"true" userName"您的账号" password"您的密码" /><co…
阅读更多...
基础IO2

基础IO2

文章目录 磁盘结构磁盘存储结构磁盘的逻辑结构引入文件系统理解文件系统inode 映射 data blocks文件名与inode的关系dentry树文件描述符与进程之间的关系 深刻理解软硬链接软链接硬链接 动静态库静态库1. 手动制作静态库2.调用静态库(1)安装到系统(2)自己指定查找路径(3)自己创…
阅读更多...
计算机网络：运输层 —— TCP的流量控制

计算机网络：运输层 —— TCP的流量控制

文章目录 TCP的流量控制TCP的流量控制方法滑动窗口机制持续计时器 TCP的流量控制 当 TCP 客户端持续发送大量数据时&#xff0c;应用程序可能正忙于其他任务&#xff0c;并不一定能够立刻取走数据&#xff0c;这会造成接收方接收缓存的溢出&#xff0c;导致数据丢失。 TCP 为应…
阅读更多...
Flink_DataStreamAPI_执行环境

Flink_DataStreamAPI_执行环境

DataStreamAPI_执行环境 1创建执行环境1.1getExecutionEnvironment1.2createLocalEnvironment1.3createRemoteEnvironment 2执行模式&#xff08;Execution Mode&#xff09;3触发程序执行 Flink程序可以在各种上下文环境中运行&#xff1a;我们可以在本地JVM中执行程序&#x…
阅读更多...
鸿蒙中如何实现图片拉伸效果

鸿蒙中如何实现图片拉伸效果

2024年10月22日&#xff0c;华为发布会上&#xff0c;推出鸿蒙5.0。现在加入恰逢时机&#xff0c;你&#xff0c;我皆是鸿蒙时代合伙人。无论为了学习技术&#xff0c;还是为了谋福利&#xff0c;在鸿蒙的浩瀚海洋中分到一杯羹。现在学习鸿蒙正当时。 一文了解鸿蒙中图片拉伸的…
阅读更多...
Unity 2022 Nav Mesh 自动寻路入门

Unity 2022 Nav Mesh 自动寻路入门

untiy 2022 window-PackageManager-AINavigation 安装 Install 2.创建一个空物体命名Nav&#xff0c;在其自身挂载 NavMeshSurface 然后点击bake 烘焙地形即可 3.创建palyer和怪物 怪物AI代码 using System.Collections; using System.Collections.Generic; using UnityEngi…
阅读更多...
基于gradio+networkx库对图结构进行可视化展示

基于gradio+networkx库对图结构进行可视化展示

前言 在gradio框架下对蛋白质-蛋白质相互作用网络&#xff08;PPI网络&#xff09;进行可视化&#xff0c;并将其在网页前端进行展示。 方法 其实很简单 可以直接使用networkx画图后保存图片&#xff0c;然后使用Gradio框架的image组件进行展示即可。 但实际上gradio还配置…
阅读更多...
MSTP知识点

MSTP知识点

多生成树协议 在 MSTP&#xff08;Multiple Spanning Tree Protocol&#xff09;中&#xff0c;根桥&#xff08;root&#xff09;、指定端口&#xff08;designated port&#xff09;、备用端口&#xff08;alternate port&#xff09;等角色都是确保网络中没有循环并且流量能…
阅读更多...
为正在运行的 Docker 容器重启策略,以提高服务的可用性

为正在运行的 Docker 容器重启策略,以提高服务的可用性

为正在运行的 Docker 容器重启策略,以提高服务的可用性。 为正在运行的 Docker 容器添加 --restartalways –restartalways 是 Docker 中一个常用的参数&#xff0c;用来设置容器的重启策略。它的作用是确保容器在一定条件下能够自动重启&#xff0c;以提高服务的可用性。 方…
阅读更多...
后台管理系统(开箱即用)

后台管理系统(开箱即用)

很久没有更新博客了&#xff0c;给大家带上一波福利吧,大佬勿扰 现在市面上流行的后台管理模板很多,若依,芋道等,可是这些框架对我们来说可能会有点重,所以我自己从0到1写了一个后台管理模板,你们使用时候可扩展性也会更高 项目主要功能: 成员管理&#xff0c;部门管理&#…
阅读更多...
Cursor安装Windows / Ubuntu

Cursor安装Windows / Ubuntu

一、安装 1、下载软件 2、安装依赖 #安装fuse sudo apt-get install fuse3、将cursor添加到应用程序列表 sudo mv cursor-0.42.5x86_64.AppImage /opt/cursor.appimage #使用自己版本号替换 sudo chmod x /opt/cursor.appimage #给予可执行权限 sudo nano /usr/share/applic…
阅读更多...
谷粒商城のRedisESRabbit MQ集群

谷粒商城のRedisESRabbit MQ集群

文章目录 前言一、搭建Redis集群三、搭建ES集群三、搭建Rabbit MQ集群 前言 本篇是谷粒商城集群部署篇&#xff0c;搭建Redis、ES、Rabbit MQ集群实践的个人笔记&#xff0c;也是谷粒商城笔记的最后一篇。集群相关的理论性内容&#xff0c;会放在面试篇的笔记中。 一、搭建Redi…
阅读更多...
孙赢利_11月17日_超分周报

孙赢利_11月17日_超分周报

一. 康佳PC端实现&#xff1a;1080 → 4K 实时超分 1. 将图像预处理操作从 CPU → GPU 运行 2. 后处理部分操作 从 CPU → GPU 运行 inference_realesrgan_Animal_Video.py import argparse import cv2 import glob import os from basicsr.archs.rrdbnet_arch import RRDBNe…
阅读更多...
录的视频怎么消除杂音？从录制到后期的杂音消除攻略

录的视频怎么消除杂音？从录制到后期的杂音消除攻略

在录制视频时&#xff0c;杂音往往是一个令人头疼的问题。无论是环境噪音、设备噪音还是电磁干扰&#xff0c;杂音的存在都会极大地影响视频的听觉体验。录的视频怎么消除杂音&#xff1f;通过一些前期准备和后期处理技巧&#xff0c;我们可以有效地消除这些杂音&#xff0c;提…
阅读更多...
论文《基于现实迷宫地形的电脑鼠设计》深度分析——智能车驱动算法

论文《基于现实迷宫地形的电脑鼠设计》深度分析——智能车驱动算法

论文概述 《基于现实迷宫地形的电脑鼠设计》是由吴润强、庹忠曜、刘文杰、项璟晨、孙科学等人于2023年发表的一篇优秀期刊论文。其针对现阶段电脑鼠计算量庞大且不适用于现实迷宫地形的问题&#xff0c;特基于超声波测距与传统迷宫算法原理&#xff0c;设计出一款可在现实迷宫地…
阅读更多...
算法日记 26-27day 贪心算法

算法日记 26-27day 贪心算法

接下来的题目有些地方比较相似。需要注意多个条件。 题目&#xff1a;分发糖果 135. 分发糖果 - 力扣&#xff08;LeetCode&#xff09; n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求&#xff0c;给这些孩子分发糖果&#xff1a; 每…
阅读更多...
vue3点击按钮el-dialog对话框不显示问题

vue3点击按钮el-dialog对话框不显示问题

vue3弹框不显示问题&#xff0c;控制台也没报错 把 append-to-body:visible.sync"previewDialogOpen" 改为 append-to-bodyv-model"previewDialogOpen" 就好了。
阅读更多...
wordpress使用相关

wordpress使用相关

这里写目录标题 遇到的相关问题WordPress安装插件过程中遇到需要ftp出现确实XMLReader 插件的提示cURL Support Missing&#xff08;curl 缺失&#xff09; 遇到的相关问题 WordPress安装插件过程中遇到需要ftp 一般在这个位置 出现确实XMLReader 插件的提示 解决&#xff1a…
阅读更多...
21.3D surface

21.3D surface

3D surface """ File : 05-decoding-Major Name : 3d_surface.py Author : lyq Date : 2024/11/16 23:10 Envi : PyCharm Description: files details """ import numpy as np import matplotlib.pyplot as plt# 设置全局默认字体…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023