当前位置: 首页 > 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,触摸屏分辨…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

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

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

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

HubSpot推出与ChatGPT的深度集成引发兴奋与担忧

上周三&#xff0c;HubSpot宣布已构建与ChatGPT的深度集成&#xff0c;这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋&#xff0c;但同时也存在一些关于数据安全的担忧。 许多网络声音声称&#xff0c;这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving

地址&#xff1a;LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂&#xff0c;正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

数据挖掘是什么?数据挖掘技术有哪些?

目录 一、数据挖掘是什么 二、常见的数据挖掘技术 1. 关联规则挖掘 2. 分类算法 3. 聚类分析 4. 回归分析 三、数据挖掘的应用领域 1. 商业领域 2. 医疗领域 3. 金融领域 4. 其他领域 四、数据挖掘面临的挑战和未来趋势 1. 面临的挑战 2. 未来趋势 五、总结 数据…...

GB/T 43887-2024 核级柔性石墨板材检测

核级柔性石墨板材是指以可膨胀石墨为原料、未经改性和增强、用于核工业的核级柔性石墨板材。 GB/T 43887-2024核级柔性石墨板材检测检测指标&#xff1a; 测试项目 测试标准 外观 GB/T 43887 尺寸偏差 GB/T 43887 化学成分 GB/T 43887 密度偏差 GB/T 43887 拉伸强度…...