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

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 系统&#xff1a…...

更安全的C gets()和str* 以及fgets和strcspn的用法

#include <stdio.h>int main() {char *str;gets(str);puts(str);return(0); }可以说全是错误 首先char *str没有指向一个分配好的地址&#xff0c;就直接读入&#xff0c;危险 ps: 怎么理解char *str "Hello World" 是将一个存储在一个只读的数据段中字符串常…...

专升本 C语言笔记-07 逗号运算符

1.逗号表达式的用法 就是用逗号隔开的多个表达式。逗号表达式&#xff0c;从左向右依次执行。 2.逗号表达式的特性 2.1.当没有括号时&#xff0c;第一个表达式为整个表达式的值。 代码 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完成的。其实&#xff0c;为了提供更丰富的用户体验&#xff0c;kubernetes还开发了一个基于web的用户界面&#xff08;Dashboard&…...

基于Java+Springmvc+vue+element实现高校心理健康系统详细设计和实现

基于JavaSpringmvcvueelement实现高校心理健康系统详细设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注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服务漏洞

针对湖南麒麟操作系统进行漏洞检测时&#xff0c;会报SSH漏洞风险提醒&#xff0c;具体如下&#xff1a; 针对这些漏洞&#xff0c;可以关闭SSH服务&#xff08;前提是应用已经部署完毕不再需要通过SSH远程访问传输文件的情况下&#xff0c;此时可以通过VNC远程登录方法&#x…...

升级ChatGPT4.0失败的解决方案

ChatGPT 4.0科普 ChatGPT 4.0是一款具有多项出众功能的新一代AI语言模型。以下是关于ChatGPT 4.0的一些关键特点和科普内容&#xff1a; 多模态&#xff1a;ChatGPT 4.0具备处理不同类型输入和输出的能力。这意味着它不仅可以接收文字信息&#xff0c;还能处理图片、视频等多媒…...

常用图像滤波器,图像增强

滤波器 滤波器在图像处理中有各种各样的应用&#xff0c;它们可以用于去除噪声、平滑图像、增强图像特征等。以下是一些常见的滤波器及其主要应用&#xff1a; 均值滤波器&#xff08;Mean Filter&#xff09;&#xff1a; 用于去除高斯噪声或均匀噪声。 平滑图像&#xff0…...

【PyTorch】成功解决ModuleNotFoundError: No module named ‘torch’

【PyTorch】成功解决ModuleNotFoundError: No module named ‘torch’ &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希…...

CommandInvokationFailure: Failed to update Android SDK package list. 报错的解决方法

将Unity升级到2021.3.36f1&#xff0c; 再次打开项目&#xff0c;结果出现“CommandInvokationFailure: Failed to update Android SDK package list. ”这样的警告&#xff0c;查看SDK版本最高只有到30&#xff0c;这应该就是Unity自动升级SDK的时候出现了错误&#xff0c;导致…...

9.用FFmpeg测试H.264文件的解码时间

1. Essence of Method 要测试对H.264文件的解码时间&#xff0c;可以使用FFmpeg进行操作。FFmpeg是一个开源的多媒体处理工具&#xff0c;可以用来处理视频和音频文件&#xff0c;包括解码H.264文件。以下是使用FFmpeg的命令行来测试解码时间的方法&#xff1a; ffmpeg -i in…...

重建3D结构方式 | 显式重建与隐式重建(Implicit Reconstruction)

在3D感知领域&#xff0c;包括3D目标检测在内&#xff0c;显式重建和隐式重建是两种不同的方法来表示和处理三维数据。它们各自有优势和局限&#xff0c;适用于不同的场景和需求。 显式重建&#xff08;Explicit Reconstruction&#xff09; 显式重建是指直接构建场景或物体的三…...

模型的参数量、计算量、延时等的关系

模型的参数量、计算量、延时等的关系 基本概念相互关系代码计算 基本概念 1.参数量&#xff1a;Params 2.计算量&#xff1a;FLOPs&#xff0c;Floating Point Operations&#xff0c;浮点运算次数&#xff0c;用来衡量模型计算复杂度。 3.延时&#xff1a;Latency 4.内存访问…...

Java映射(含源码)

在Java中&#xff0c;“映射”&#xff08;Map&#xff09;是一个存储键值对的数据结构&#xff0c;允许你通过键&#xff08;Key&#xff09;快速访问值&#xff08;Value&#xff09;。映射中的每个键都是唯一的&#xff0c;这意味着每个键都对应一个特定的值。Java提供了几种…...

JMeter 面试题及答案整理,最新面试题

JMeter中如何进行性能测试的规划和设计&#xff1f; 进行JMeter性能测试的规划和设计主要遵循以下几个步骤&#xff1a; 1、确定测试目标&#xff1a; 明确性能测试的目的和目标&#xff0c;比如确定要测试的系统性能指标&#xff08;如响应时间、吞吐量、并发用户数等&#…...

lua脚本的基础内容

官方地址&#xff1a;http://luajit.org/ 官方wiki地址&#xff1a;http://wiki.luajit.org/Home 推荐书籍&#xff1a; OpenResty 最佳实践&#xff1a;https://moonbingbing.gitbooks.io/openresty-best-practices/content/ lua基础文档&#xff1a;https://www.runoob.com/l…...

MySQL语法分类 DDL(1)

DDL&#xff08;1&#xff09;(操作数据库、表) 数据库操作(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发布以来&#xff0c;大家都更加注重物品的防丢&#xff0c;苹果的 Find My 就可以查找 iPhone、Mac、AirPods、Apple Watch&#xff0c;如今的Find My已经不单单可以查找苹果的设备&#xff0c;随着第三方设备的加入&#xff0c;将丰富Find My Network的版图。产…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)

要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况&#xff0c;可以通过以下几种方式模拟或触发&#xff1a; 1. 增加CPU负载 运行大量计算密集型任务&#xff0c;例如&#xff1a; 使用多线程循环执行复杂计算&#xff08;如数学运算、加密解密等&#xff09;。运行图…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...