Leetcode 22. 括号生成

心路历程:
一开始看到左右括号,第一想到了栈。后来发现题目要求遍历所有的可能组合,第一想法是暴力for循环,但是不知道用几个for循环,所以想到递归和回溯。
虽然叫‘括号组合’,但是实际上这是一个满足规则的全排列问题,这道题与前面的leetcode 17非常像,只是多了一步判断候选集合是否合法。
按照回溯问题的模板,维护候选集合和记录路径即可:维护一个栈,代表当前已经输出的括号,栈为空or栈里只有左括号时才行,进去一个右括号就消掉一个左括号。栈为空时,只能分配左括号。
代码写的有点啰嗦,不过思路很清楚,就没有在AC后进一步简化;里面有一些可以简化行数的点。
注意的点:
1、在任意一个遍历节点,需要保证当前左括号数量大于等于右括号,)(这种是不合法的。
2、注意这是一个满足候选集规则的全排列问题,在树的末端拷贝路径。
3、终止条件是遍历到空节点而不是叶子节点,即到2n而不是2n-1。
4、候选集的条件:1)还有某种类型的括号可以选;2)满足已选的左括号数量大于右括号。
class Solution:def generateParenthesis(self, n: int) -> List[str]:res = []path = []left = [['('] * n, [')'] * n]mystack = Mystack()def dfs(i): # 第i个节点,代表目前已经生成了i个括号,还有2n-i个需要遍历nonlocal nif i == 2 * n :res.append(''.join(path[:]))return# 按照规则选择括号candicates = []if mystack.len() == 0:if left[0] == []:candicates.append(')')else:candicates.append('(')else: # 一定剩有右括号if left[0] == []:candicates.append(')')else:candicates += ['(', ')']for each in candicates:if each == '(':path.append(each)left[0].pop()mystack.append(each, True)dfs(i+1)path.pop()left[0].append(each)mystack.pop()else:path.append(each)left[1].pop()mystack.append(each, False)dfs(i+1)path.pop()left[1].append(each)mystack.append('(', True)dfs(0)return resclass Mystack:def __init__(self):from collections import dequeself.stack = deque([])def pop(self):return self.stack.pop()def append(self, ele, is_left):if is_left:self.stack.append(ele)else:assert self.stack != []self.stack.pop()def len(self):return len(self.stack)
相关文章:
Leetcode 22. 括号生成
心路历程: 一开始看到左右括号,第一想到了栈。后来发现题目要求遍历所有的可能组合,第一想法是暴力for循环,但是不知道用几个for循环,所以想到递归和回溯。 虽然叫‘括号组合’,但是实际上这是一个满足规则…...
ChatGPT编程—实现小工具软件(批量替换文本、批量处理图像文件)
ChatGPT编程—实现小工具软件(批量替换文本、批量处理图像文件) 今天借助[小蜜蜂AI][https://zglg.work]网站的ChatGPT编程实现一个功能:批量处理文件及其内容,例如批量替换文本、批量处理图像文件等。 环境:Pycharm 2021 系统:…...
更安全的C gets()和str* 以及fgets和strcspn的用法
#include <stdio.h>int main() {char *str;gets(str);puts(str);return(0); }可以说全是错误 首先char *str没有指向一个分配好的地址,就直接读入,危险 ps: 怎么理解char *str "Hello World" 是将一个存储在一个只读的数据段中字符串常…...
专升本 C语言笔记-07 逗号运算符
1.逗号表达式的用法 就是用逗号隔开的多个表达式。逗号表达式,从左向右依次执行。 2.逗号表达式的特性 2.1.当没有括号时,第一个表达式为整个表达式的值。 代码 int x 3,y 5,a 0; a x,y; printf("a %d",a); 说明:因为逗号优先级最低,会…...
k8s之图形界面DashBoard【九】
文章目录 9. DashBoard9.1 部署Dashboard9.2 使用DashBoard 镇场 9. DashBoard 之前在kubernetes中完成的所有操作都是通过命令行工具kubectl完成的。其实,为了提供更丰富的用户体验,kubernetes还开发了一个基于web的用户界面(Dashboard&…...
基于Java+Springmvc+vue+element实现高校心理健康系统详细设计和实现
基于JavaSpringmvcvueelement实现高校心理健康系统详细设计和实现 博主介绍:多年java开发经验,专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐…...
python --阿里云(智能媒体管理/视频点播)
智能媒体服务获取token # alibabacloud_imm202009304.1.0 class Sample(object):智能媒体服务def __init__(self):self.access_key 111self.key_secret 222def weboffice_permission(self):return imm_20200930_models.WebofficePermission(renameFalse,readonlyTrue,histor…...
湖南麒麟SSH服务漏洞
针对湖南麒麟操作系统进行漏洞检测时,会报SSH漏洞风险提醒,具体如下: 针对这些漏洞,可以关闭SSH服务(前提是应用已经部署完毕不再需要通过SSH远程访问传输文件的情况下,此时可以通过VNC远程登录方法&#x…...
升级ChatGPT4.0失败的解决方案
ChatGPT 4.0科普 ChatGPT 4.0是一款具有多项出众功能的新一代AI语言模型。以下是关于ChatGPT 4.0的一些关键特点和科普内容: 多模态:ChatGPT 4.0具备处理不同类型输入和输出的能力。这意味着它不仅可以接收文字信息,还能处理图片、视频等多媒…...
常用图像滤波器,图像增强
滤波器 滤波器在图像处理中有各种各样的应用,它们可以用于去除噪声、平滑图像、增强图像特征等。以下是一些常见的滤波器及其主要应用: 均值滤波器(Mean Filter): 用于去除高斯噪声或均匀噪声。 平滑图像࿰…...
【PyTorch】成功解决ModuleNotFoundError: No module named ‘torch’
【PyTorch】成功解决ModuleNotFoundError: No module named ‘torch’ 🌈 个人主页:高斯小哥 🔥 高质量专栏:Matplotlib之旅:零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程👈 希…...
CommandInvokationFailure: Failed to update Android SDK package list. 报错的解决方法
将Unity升级到2021.3.36f1, 再次打开项目,结果出现“CommandInvokationFailure: Failed to update Android SDK package list. ”这样的警告,查看SDK版本最高只有到30,这应该就是Unity自动升级SDK的时候出现了错误,导致…...
9.用FFmpeg测试H.264文件的解码时间
1. Essence of Method 要测试对H.264文件的解码时间,可以使用FFmpeg进行操作。FFmpeg是一个开源的多媒体处理工具,可以用来处理视频和音频文件,包括解码H.264文件。以下是使用FFmpeg的命令行来测试解码时间的方法: ffmpeg -i in…...
重建3D结构方式 | 显式重建与隐式重建(Implicit Reconstruction)
在3D感知领域,包括3D目标检测在内,显式重建和隐式重建是两种不同的方法来表示和处理三维数据。它们各自有优势和局限,适用于不同的场景和需求。 显式重建(Explicit Reconstruction) 显式重建是指直接构建场景或物体的三…...
模型的参数量、计算量、延时等的关系
模型的参数量、计算量、延时等的关系 基本概念相互关系代码计算 基本概念 1.参数量:Params 2.计算量:FLOPs,Floating Point Operations,浮点运算次数,用来衡量模型计算复杂度。 3.延时:Latency 4.内存访问…...
Java映射(含源码)
在Java中,“映射”(Map)是一个存储键值对的数据结构,允许你通过键(Key)快速访问值(Value)。映射中的每个键都是唯一的,这意味着每个键都对应一个特定的值。Java提供了几种…...
JMeter 面试题及答案整理,最新面试题
JMeter中如何进行性能测试的规划和设计? 进行JMeter性能测试的规划和设计主要遵循以下几个步骤: 1、确定测试目标: 明确性能测试的目的和目标,比如确定要测试的系统性能指标(如响应时间、吞吐量、并发用户数等&#…...
lua脚本的基础内容
官方地址:http://luajit.org/ 官方wiki地址:http://wiki.luajit.org/Home 推荐书籍: OpenResty 最佳实践:https://moonbingbing.gitbooks.io/openresty-best-practices/content/ lua基础文档:https://www.runoob.com/l…...
MySQL语法分类 DDL(1)
DDL(1)(操作数据库、表) 数据库操作(CRUD) C(Create):创建 //指定字符集创建 create database db_1 character set utf8;//避免重复创建数据库报错可以用一下命令 create database if not exists db_1 character set utf8;R(Retrieve):查询 //查询所…...
苹果Find My App用处多多,产品认准伦茨科技ST17H6x芯片
苹果发布AirTag发布以来,大家都更加注重物品的防丢,苹果的 Find My 就可以查找 iPhone、Mac、AirPods、Apple Watch,如今的Find My已经不单单可以查找苹果的设备,随着第三方设备的加入,将丰富Find My Network的版图。产…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
