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 网络请求设置代理…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
第25节 Node.js 断言测试
Node.js的assert模块主要用于编写程序的单元测试时使用,通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试,通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Webpack性能优化:构建速度与体积优化策略
一、构建速度优化 1、升级Webpack和Node.js 优化效果:Webpack 4比Webpack 3构建时间降低60%-98%。原因: V8引擎优化(for of替代forEach、Map/Set替代Object)。默认使用更快的md4哈希算法。AST直接从Loa…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
