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的版图。产…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的: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;…...
