当前位置: 首页 > 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的版图。产…...

tools.simonwillison.net图像处理工具集:从裁剪到优化的完整指南

tools.simonwillison.net图像处理工具集&#xff1a;从裁剪到优化的完整指南 【免费下载链接】tools Assorted useful tools, almost entirely generated using LLMs 项目地址: https://gitcode.com/gh_mirrors/tools23/tools tools.simonwillison.net图像处理工具集是一…...

机器学习模型评估中的构念效度:超越基准测试分数的科学推断

1. 项目概述与核心问题在机器学习的日常研究和工程实践中&#xff0c;我们每天都在和各种各样的基准测试&#xff08;Benchmark&#xff09;打交道。无论是为了比较新提出的ResNet变体在ImageNet上的Top-1准确率&#xff0c;还是评估一个大型语言模型在MMLU上的常识推理能力&am…...

从理论推导到代码实现:手把手教你用Python/Numpy写出守恒形式的NS方程求解器

从理论推导到代码实现&#xff1a;手把手教你用Python/Numpy写出守恒形式的NS方程求解器计算流体力学&#xff08;CFD&#xff09;的魅力在于它将抽象的数学方程转化为可执行的代码&#xff0c;让流体运动的奥秘在计算机中重现。对于已经掌握流体力学理论的中高级学习者来说&am…...

浏览器 Profile 环境排查:Cookie、LocalStorage、网络出口与自动化任务配置清单

一、为什么浏览器环境经常“今天能用&#xff0c;明天失效”很多团队遇到登录状态丢失、页面配置异常、自动化任务失败时&#xff0c;会先怀疑网络、脚本或系统本身。但在实际项目里&#xff0c;问题经常不是单点故障&#xff0c;而是浏览器环境缺少稳定管理&#xff1a;对象常…...

为什么92%的DeepSeek二次开发团队在6个月内遭遇交付延迟?——基于17个真实项目的技术债务归因分析

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;为什么92%的DeepSeek二次开发团队在6个月内遭遇交付延迟&#xff1f;——基于17个真实项目的技术债务归因分析 在对17个采用DeepSeek-R1/VL模型开展定制化开发的工业级项目进行回溯审计后&#xff0c;我…...

内存占用3KB!极致瘦身释放MCU无限可能

极致小体积&#xff0c;给工业领域带来了无限的可能&#xff1a;更低硬件成本&#xff0c;更小芯片体积&#xff0c;更低功耗&#xff0c;更高可靠性&#xff0c;让每一颗小MCU都拥有大系统的完整能力。 https://www.bilibili.com/video/BV1eZLi6PEjc/?spm_id_from333.1387.ho…...

使用TaotokenCLI工具一键配置开发环境中的API密钥

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 使用Taotoken CLI工具一键配置开发环境中的API密钥 在团队协作或个人开发中&#xff0c;为每个项目或成员手动配置大模型API密钥和…...

从零到上机:我的第一个Quest 3空间锚点应用是如何跑起来的(附完整Unity工程)

从零到上机&#xff1a;我的第一个Quest 3空间锚点应用是如何跑起来的&#xff08;附完整Unity工程&#xff09;第一次戴上Meta Quest 3时&#xff0c;那种虚拟与现实交织的震撼感至今难忘。但作为开发者&#xff0c;更让我着迷的是如何让虚拟物体在真实空间中"记住"…...

风控系统如何全维度识别爬虫:IP、账号与行为的协同决策机制

1. 这不是“反爬失败”&#xff0c;而是风控系统在对你做全维度画像你写完一段 requests BeautifulSoup 的代码&#xff0c;本地跑通了&#xff0c;开开心心部署到服务器&#xff0c;结果第二天早上发现&#xff1a;所有请求返回 403&#xff0c;日志里全是空响应&#xff1b;…...

Adobe-GenP 3.0:轻松激活Adobe全家桶的完整指南

Adobe-GenP 3.0&#xff1a;轻松激活Adobe全家桶的完整指南 【免费下载链接】Adobe-GenP Adobe CC 2019/2020/2021/2022/2023 GenP Universal Patch 3.0 项目地址: https://gitcode.com/gh_mirrors/ad/Adobe-GenP Adobe-GenP 3.0是一款专为Adobe Creative Cloud系列软件…...