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

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

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

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

【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...