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 网络请求设置代理…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
JS设计模式(4):观察者模式
JS设计模式(4):观察者模式 一、引入 在开发中,我们经常会遇到这样的场景:一个对象的状态变化需要自动通知其他对象,比如: 电商平台中,商品库存变化时需要通知所有订阅该商品的用户;新闻网站中࿰…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
