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

LeetCode LCR 085.括号生成

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

示例 1:

输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2:

输入:n = 1
输出:[“()”]

提示:

1 <= n <= 8

法一:直接生成由’(‘和’)'组成的全部可能的字符串,然后再一个一个判断是否合法:

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;string s(2 * n, '\0');getAllParentheses(res, 0, s, n);return res;}private:void getAllParentheses(vector<string> &res, int index, string &s, int n){if (index == 2 * n){if (isValid(s)){res.push_back(s);}return;}s[index] = '(';getAllParentheses(res, index + 1, s, n);s[index] = ')';getAllParentheses(res, index + 1, s, n);}bool isValid(string &s){int cnt = 0;for (char c : s){if (c == '('){++cnt;}else{--cnt;}if (cnt < 0){return false;}}return cnt == 0;}
};

此方法时间复杂度为O(n2 2 n ^{2n} 2n);空间复杂度为O(n),最多递归2n层。很差的方法。

法二:递归求解即可:

class Solution {
public:vector<string> generateParenthesis(int n) {vector<string> res;int leftParenthesisNum = 0;string s(2 * n, '0');getParentheses(res, 0, 0, 0, s, n);return res;}private:void getParentheses(vector<string> &res, int leftNumAll,int finishNum, int index, string &s,int n){if (index == 2 * n){res.push_back(s);}if (leftNumAll < n){s[index] = '(';getParentheses(res, leftNumAll + 1, finishNum, index + 1, s, n);}if (finishNum < leftNumAll){s[index] = ')';getParentheses(res, leftNumAll, finishNum + 1, index + 1, s, n);}}
};

在这里插入图片描述
法三:我们可以把生成的结果看做(a)b,其中a和b分别是合法括号串。我们枚举每个右括号,分别计算枚举过程中a和b的内容,并且可以把特定长度的a和b的内容缓存下来:

class Solution {
public:vector<string> generateParenthesis(int n) {vector<vector<string>> cache(9);cache[0] = {""};return generate(n, cache);}private:vector<string> generate(int n, vector<vector<string>> &cache){if (cache[n].size() != 0){return cache[n];}vector<string> cur;for (int i = 0; i < n; ++i){vector<string> left = generate(i, cache);vector<string> right = generate(n - 1 - i, cache);for (string &sleft : left){for (string &sright : right){cur.push_back("(" + sleft + ")" + sright);}}cache[n] = cur;}return cache[n];}
};

在这里插入图片描述

相关文章:

LeetCode LCR 085.括号生成

正整数 n 代表生成括号的对数&#xff0c;请设计一个函数&#xff0c;用于能够生成所有可能的并且 有效的 括号组合。 示例 1&#xff1a; 输入&#xff1a;n 3 输出&#xff1a;[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2&#xff1a; 输入&#x…...

抖音视频评论数据提取软件|抖音数据抓取工具

一、开发背景&#xff1a; 在业务需求中&#xff0c;我们经常需要下载抖音视频。然而&#xff0c;在网上找到的视频通常只能通过逐个复制链接的方式进行抓取和下载&#xff0c;这种操作非常耗时。我们希望能够通过关键词自动批量抓取并选择性地下载抖音视频。因此&#xff0c;为…...

【web】云导航项目部署及环境搭建(复杂)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、项目介绍1.1项目环境架构LNMP1.2项目代码说明 二、项目环境搭建2.1 Nginx安装2.2 php安装2.3 nginx配置和php配置2.3.1 修改nginx文件2.3.2 修改vim /etc/p…...

软件测试人员必会的linux命令

文件和目录操作: ● ls:列出目录中的文件和子目录。 ● cd:改变当前工作目录。 ● mkdir:创建新目录。 ● rm:删除文件或目录。 ● cp:复制文件或目录。 ● mv:移动或重命名文件或目录。 文本查看和编辑: ● cat:查看文件内容。 ● more或less:分页查看文件内…...

Mac使用K6工具压测WebSocket

commend空格 打开终端&#xff0c;安装k6 brew install k6验证是否安装成功 k6 version设置日志级别为debug export K6_LOG_LEVELdebug执行脚本&#xff08;进入脚本所在文件夹下&#xff09; k6 run --vus 100 --duration 10m --out csvresult.csv script.js 脚本解释&…...

小程序--vscode配置

要在vscode里开发微信小程序&#xff0c;需要安装以下两个插件&#xff1a; 安装后&#xff0c;即可使用vscode开发微信小程序。 注&#xff1a;若要实现鼠标悬浮提示&#xff0c;则需新建jsconfig.json文件&#xff0c;并进行配置&#xff0c;即可实现。 jsconfig.json内容如…...

linux僵尸进程

僵尸进程&#xff08;Zombie Process&#xff09;是指在一个进程终止时&#xff0c;其父进程尚未调用wait()或waitpid()函数来获取该进程的终止状态信息&#xff0c;导致进程的资源&#xff08;如进程表中的记录&#xff09;仍然保留在系统中的一种状态。 当一个进程结束时&am…...

【web | CTF】攻防世界 Web_php_unserialize

天命&#xff1a;这条反序列化题目也是比较特别&#xff0c;里面的漏洞知识点&#xff0c;在现在的php都被修复了 天命&#xff1a;而且这次反序列化的字符串数量跟其他题目不一样 <?php class Demo { // 初始化给变量内容&#xff0c;也就是当前文件&#xff0c;高亮显示…...

Vue3中的select 的option是多余的?

背景&#xff1a; 通过Vue3中填充一个下拉框&#xff0c;在打开页面时要指定默认选中&#xff0c;并在选项改变时把下拉框的选中值显示出来 问题&#xff1a; 填充通常的作法是设置 <option v-for"option in cities" :value"option.value" >&a…...

考研408深度分析+全年规划

408确实很难&#xff0c;他的难分两方面 一方面是408本身的复习难度&#xff0c;我们都知道&#xff0c;408的考察科目有四科&#xff0c;分别是数据结构&#xff0c;计算机组成原理&#xff0c;操作系统和计算机网络。大家回想一下自己在大学本科时候学习这些专业课的难度&am…...

【算法笔记】ch01_01_0771 宝石与石头

笔记介绍&#xff1a; 本项目是datawhale发布的LeetCode 算法笔记&#xff08;Leetcode-Notes&#xff09;课程完成笔记&#xff0c;根据推荐题目循序渐进练习算法题目。主要用python进行书写相关代码&#xff0c;会介绍解题思路及跑通解法。 0771. 宝石与石头 题目大意 描…...

jQuery瀑布流画廊,瀑布流动态加载

jQuery瀑布流画廊&#xff0c;瀑布流动态加载 效果展示 手机布局 jQuery瀑布流动态加载 HTML代码片段 <!-- mediabanner --><div class"mediabanner"><img src"img/mediabanner.jpg" class"bg"/><div class"text&qu…...

玩转ChatGPT:参考文献速查

一、写在前面 各位大佬&#xff0c;我又回来了&#xff0c;最近2月太忙啦&#xff08;过年、奶娃、本子、材料、结题&#xff09;&#xff0c;断更了。现水一篇证明我还活着&#xff01;&#xff01;&#xff01; 最近在写国自然本子&#xff0c;遇到一个估计大家都会遇到的问…...

[设计模式Java实现附plantuml源码~行为型]算法的封装与切换——策略模式

前言&#xff1a; 为什么之前写过Golang 版的设计模式&#xff0c;还在重新写Java 版&#xff1f; 答&#xff1a;因为对于我而言&#xff0c;当然也希望对正在学习的大伙有帮助。Java作为一门纯面向对象的语言&#xff0c;更适合用于学习设计模式。 为什么类图要附上uml 因为很…...

​【C语言】长篇详解,字符系列篇3-----strstr,strtok,strerror字符串函数的使用【图文详解​】

欢迎来CILMY23的博客喔&#xff0c;本期系列为​【C语言】长篇详解&#xff0c;字符系列篇3-----strstr&#xff0c;strtok&#xff0c;strerror字符串函数的使用【图文详解​】&#xff0c;图文讲解各种字符串函数&#xff0c;带大家更深刻理解C语言中各种字符串函数的应用&am…...

如何实现一个K8S DevicePlugin?

什么是device plugin k8s允许限制容器对资源的使用&#xff0c;比如CPU和内存&#xff0c;并以此作为调度的依据。 当其他非官方支持的设备类型需要参与到k8s的工作流程中时&#xff0c;就需要实现一个device plugin。 Kubernetes提供了一个设备插件框架&#xff0c;你可以用…...

Android LruCache源码分析

文章目录 Android LruCache源码分析概述LruCache和LinkedHashMap关系源码分析属性写入数据读取数据删除缓存 Android LruCache源码分析 概述 LruCache&#xff08;Least Recently Used Cache&#xff0c;最近最少使用缓存&#xff09;是 Android 中的一种缓存机制。 根据数据…...

如何使用Inno Setup制作Unity构建程序的Windows安装程序

1. 准备 &#xff08;1&#xff09;准备好Unity构建的程序集合 必须包括&#xff1a; Data文件夹&#xff08;xxx_Data&#xff09; Mono文件夹&#xff08;MonoBleedingEdge&#xff09; 打包的应用程序文件&#xff08;xxx.exe&#xff09; Unity播放器dll文件&#xff…...

linux 面试题

1.linux操作系统的常用指令可以详细说下吗,平常哪些用的比较多 文件目录操作命令: ls cd more cat tail mkdir touch rm rmdir 拷贝复制: cp mv 打包解包压缩解压: tar -z 解亚压缩 -c 打包 -x 解包 -v 显示过程 -f 指定文件名 文本编辑: vi vim 查找: find 查找文件 gre…...

嵌入式中逻辑分析仪基本操作方法

前期准备 1.一块能触摸的屏对应的主板机 2.逻辑分析仪对应的软件工具 3.对应的拓展板 4.确定拓展板的引脚分布情况 第一步&#xff1a;逻辑分析仪j基本操作 1.数据捕捉需要先进行对应软件安装,并按照需求进行配置 2.这里以A20为例:此手机使用显示驱动芯片CST148,触摸屏分辨…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

Axure 下拉框联动

实现选省、选完省之后选对应省份下的市区...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...