22.括号生成
题目描述
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2:
输入:n = 1 输出:[“()”]
提示:
1 <= n <= 8
思路
首先思考算法的暴力解法,再对解法进行优化得到最终解法。
暴力思路:
输入为n时,输出的字符串长度为2n。可以定义一个长度为2n的数组,每一个位置不是左括号就是右括号。暴力生成所有的长度为2n的字符串,然后遍历所有的字符串,一旦左括号数小于右括号数就判定为不合格的字符串。这种算法的时间复杂度为O(2^2n)
这种算法的时间复杂度太高,根本没必要一下子生成这么多的字符串,浪费时间。我们可以使用条件来对生成字符串的过程进行剪枝。
条件观察
输入为n时,输出字符串长度为2n
局部字串符合条件的情况下,右括号不会作为新串的开头,如:'()‘合理,但’)()'不合理
局部串中 n >= 左括号数 >= 右括号数
由条件分析
如果left>n,则返回上一层;
如果left < right,则返回上一层;
代码
class Solution {public List<String> generateParenthesis(int n) {List<String> results = new ArrayList<String>();gen(0, 0, n, "", results);return results;}// 递归函数,参数说明如下// left :左括号使用的个数// right:右括号使用的个数// n:输入的n,用于判断左右括号是否超出限制// result:当前生成的合格的子串// results:合格字符串的列表public void gen(int left,int right,int n,String result, List<String> results){if(left == n && right == n){results.add(result);return;}// 两个剪枝条件,只要满足剪枝条件,则不再继续if(left > n || left < right)return;gen(left+1, right, n, result+'(', results);gen(left, right+1, n, result+')', results);}
}
相关文章:
22.括号生成
题目描述 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n 3 输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] 示例 2: 输入…...
JAVA八股--redis
JAVA八股--redis 如何保证Redis和数据库数据一致性redisson实现的分布式锁的主从一致性Redis脑裂现象及解决方案介绍I/O多路复用模型undo log 和 redo log(没掌握MyISAM 和 InnoDB 有什么区别? 如何保证Redis和数据库数据一致性 关于异步通知中消息队列…...
[图像处理] MFC载入图片并绘制ROI矩形
上一篇: [图像处理] MFC载入图片并进行二值化处理和灰度处理及其效果显示 文章目录 前言完整代码重要代码效果 前言 上一篇实现了MFC通过Picture控件载入图片。 这一篇实现ROI功能的第一部分,在Picture控件中,通过鼠标拖拽画出一个矩形。 完…...
Godot 4 教程《勇者传说》依赖注入 学习笔记(0):环境配置
文章目录 前言相关地址环境配置初始化环境配置文件夹结构代码结构代码运行 资源文件导入像素风格窗口环境设置背景设置,Tileap使用自动TileMap 人物场景动画节点添加站立节点添加移动动画添加 通过依赖注入获取Godot的全局属性项目声明 当前项目逻辑讲解角色下降添加代码位置问…...
强行让Java和Go对比一波[持续更新]
概述 很多Java开发如果想转Golang的话,比较让Java开发蛋疼的第一是语法,第二是一些思想和设计哲学的Gap,所以我这儿强行整理一波Java和Golang的对比,但是由于GO和Java在很多方面都有不同的设计,所以这些对比的项可以更…...
理解七层网络协议
osi体系结构 上三路(管数据) 应用层 通过http等,把传输的格式,数据打包 处理网络应用。直接为端用户服务,提供各类应用过程的接口和用户接口。例如:HTTP、Tenlent、FTP、SMTP、NFS等。基于TCP的FTP、HTTP…...
网络协议——HTTP协议
目录 编辑 一,HTTP协议基本认识 二,认识URL 三,http协议的格式 1,发送格式 2,回应格式 四,服务端代码 五,http报文细节 1,Post与Get方法 2,Content_lenth 3&…...
八股面试——数据库——索引
索引的概念 B树的概念: 索引的作用 聚簇索引与非聚簇索引 聚簇索引就是主键值,在B树上,通过主键大小(数据在B树叶子节点按主键顺序排序)寻找对应的叶子节点,叶子节点保存的一整条记录。 非聚簇索引&#x…...
【二分查找】Leetcode 二分查找
题目解析 二分查找在数组有序可以使用,也可以在数组无序的时候使用(只要数组中的一些规律适用于二分即可) 704. 二分查找 算法讲解 当left > right的时候,我们循环结束,但是当left和right缩成一个点的时候&#x…...
Python+Vuecil笔记
Nginx 进入目录: C:\nginx-1.20.2\nginx-1.20.2 start nginx 开始 nginx -s stop 停止 nginx -s quit 退出CSS 通过标签去写css 循环展示数据 JS 点击时执行事件 Django 配置media 在seetings里面修改 STATIC_URL /static/ MEDIA_URL /upload/ MEDIA_ROOT os.pat…...
C语言关于随机数知识点的总结
在C语言中,随机数的生成通常依赖于特定的库函数,最常用的是 <stdlib.h> 头文件中的 rand() 函数。以下是对随机数知识点的总结、举例和分析: 随机数知识点总结 1.随机数种子:rand() 函数生成的随机数是伪随机数࿰…...
网络应用层和传输层
网络中有很多协议这些协议的不同导致了分层这一现象,不同层的主要功能不一样。 应用层:应用程序。数据具体如何使用 传输层:关注起点和终点 网络层:关注路径规划 数据链路层:关注相邻节点的转发 物理层࿱…...
Vue3:优化-从响应式数据中获取纯数据
一、情景说明 我们知道,Vue3中,创建变量时,常用ref、reactive来包裹,这样,这个变量就是响应式数据 然而,有时候,我们只需要纯数据 例如,我们在调用后端接口的时候,我们只…...
C#.手术麻醉系统源码 手麻系统如何与医院信息系统进行集成?
C#.手术麻醉系统源码 手麻系统如何与医院信息系统进行集成? 手术麻醉系统与医院信息系统的集成是一个关键步骤,它有助于实现信息的共享和流程的协同,从而提高医疗服务的效率和质量。手麻系统与lis、his、pacs等系统的对接是医院信息化建设的重…...
学习CSS Flexbox 玩flexboxfroggy flexboxfroggy1-24关详解
欢迎来到Flexbox Froggy,这是一个通过编写CSS代码来帮助Froggy和朋友的游戏! justify-content 和 align-items 是两个用于控制 CSS Flexbox 布局的属性。 justify-content:该属性用于控制 Flexbox 容器中子项目在主轴(水平方向)…...
springboot项目如何配置跨域?
在Spring Boot项目中配置跨域(CORS,Cross-Origin Resource Sharing)主要是为了允许来自不同源(不同的协议、域名或端口)的前端应用能够访问后端API。Spring Boot提供了多种方式来配置跨域支持。 1. 使用CrossOrigin注…...
实现第一个动态链接库 游戏插件 成功在主程序中运行 dll 中定义的类
devc 5.11编译环境 dll编译环境设置参考 Dev c C语言实现第一个 dll 动态链接库 创建与调用-CSDN博客 插件 DLL代码和主程序代码如下 注意 dll 代码中的class 类名需要 和主程序 相同 其中使用了函数指针和强制类型转换 函数指针教程参考 以动态库链接库 .dll 探索结构体…...
算法第三十九天-验证二叉树的前序序列化
验证二叉树的前序序列化 题目要求 解题思路 方法一:栈 栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。 我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的,只有当根节点的所有左子树遍历完成之后…...
Rust---复合数据类型之字符串与切片(2)
目录 字符串操作删除 (Delete)连接 (Concatenate)字符串转义前情回顾: Rust—复合数据类型之字符串(1) 字符串操作 删除 (Delete) 删除方法仅适用于 String 类型,分别是: pop(),remove(),truncate(),clear(),此外还有drain() 方法。 pop 方法:pop() 方法返回一个 O…...
iOS 应用内网络请求设置代理
主要通过URLSessionConfiguration 的connectionProxyDictionary 属性 为了方便其他同学使用,我们可以通过界面来进行设定(是否开启代理、服务端、端口),从而达到类似系统上的设定 具体链接参考:为 iOS 网络请求设置代理…...
紧急通知:2024年Q3起欧盟EDPS已将差分隐私实现纳入DPIA强制审查项——Python开发者必须立即核查的4个代码检查点
第一章:差分隐私合规性背景与EDPS新规解读随着欧盟数据保护监管体系持续演进,欧洲数据保护监督机构(EDPS)于2024年7月发布《关于匿名化与假名化技术在公共部门应用的指导意见》,首次将差分隐私(Differentia…...
保姆级教程:用命令行实时监控瑞芯微RK3588的CPU/GPU/NPU负载与温度
嵌入式开发实战:构建RK3588芯片全维度性能监控系统 在边缘计算和AI推理场景中,RK3588作为一款高性能SoC,其复杂的多核架构(包括6核CPU、Mali-G610 GPU和6TOPS NPU)对系统监控提出了更高要求。本文将手把手教你搭建一个…...
告别命令行恐惧:用RU.EXE快捷键玩转硬件诊断(附常用命令速查表)
告别命令行恐惧:用RU.EXE快捷键玩转硬件诊断(附常用命令速查表) 在工业计算机维护和硬件诊断领域,RU.EXE一直是资深工程师的秘密武器。但对于每天奔波在不同现场的技术支持人员来说,面对这个功能强大却界面复古的工具&…...
OpenClaw语音交互扩展:百川2-13B+Whisper实现语音指令控制
OpenClaw语音交互扩展:百川2-13BWhisper实现语音指令控制 1. 为什么需要语音交互能力 去年冬天的一个深夜,我正在调试OpenClaw的自动化脚本,双手因为长时间敲键盘已经有些僵硬。突然想到:如果能让AI听懂我的语音指令直接执行任务…...
电脑c盘变红了怎么清理?C盘清理工具与方法
电脑c盘变红了怎么清理?问题不难解决,关键是选对方法工具!下面介绍实用的清理C盘方法,便于你解决C盘变红的问题哦! 关于C盘清理工具,给大家安排一款针对C盘爆满的清理神器---Windows - Cleaner,…...
HunyuanVideo-Foley效果展示:AI生成ASMR触发音、白噪音与专注背景音
HunyuanVideo-Foley效果展示:AI生成ASMR触发音、白噪音与专注背景音 1. 核心能力概览 HunyuanVideo-Foley是一款专为音效生成优化的AI模型,能够根据文字描述自动生成高质量的音频内容。基于RTX 4090D 24GB显存深度优化,该镜像提供了开箱即用…...
NRF_LOG时间戳配置全攻略:从sdk_config.h修改到RTT Viewer显示(附常见问题排查)
NRF_LOG时间戳配置全攻略:从sdk_config.h修改到RTT Viewer显示(附常见问题排查) 在嵌入式开发中,日志系统是调试和问题排查的重要工具。对于使用Nordic Semiconductor芯片的开发者来说,NRF_LOG结合RTT Viewer提供了高效…...
测试用例设计-XMind
🚀 一、XMind 用例设计核心思路👉 和传统Excel不同,XMind强调:以“功能模块”为主干 以“用户场景”为分支 以“测试点”为叶子节点👉 本质结构:模块 → 场景 → 用例点 → 具体测试数据/预期📌…...
3分钟轻松获取无水印抖音视频:DouYinBot全能解析工具使用指南
3分钟轻松获取无水印抖音视频:DouYinBot全能解析工具使用指南 【免费下载链接】DouYinBot 抖音无水印下载 项目地址: https://gitcode.com/gh_mirrors/do/DouYinBot 在短视频创作的浪潮中,每个创作者都曾遇到这样的困扰:精心挑选的抖音…...
OpenClaw自动化测试:Qwen3.5-9B执行Python脚本与结果校验
OpenClaw自动化测试:Qwen3.5-9B执行Python脚本与结果校验 1. 为什么选择OpenClaw做自动化测试? 去年接手一个数据清洗工具链项目时,我遇到了一个典型痛点:每次代码更新后,都需要手动执行十几个测试用例,比…...
