【华为面试基础题】最大括号深度

news/2024/4/19 17:59:00/

描述

现有一字符串 仅由 '(', ')', '{', '}', '[', ']'一共六种括号组成。若字符串满足以下条件之一,则为无效字符串。

  1. 任意类型的左右括号数量不相等
  2. 存在未按正确顺序(先左后右)闭合的括号, 输出括号的最大嵌套深度,若字符串无效则输出 0。
    0 <= 字符串长度 <= 100000

输入描述:
一个只包括 '(', ')', '{', '}', '[', ']' 以一共6种字符的字符串。

输出描述:
一个整数,表示最大的括号深度。若字符串无效,则输出 0

示例1

输入:[]
输出:1
说明:该字符串有效,且最大嵌套深度为 1

示例2

输入:([]{()})
输出:3
说明:该字符串有效,且最大嵌套深度为 3

示例3

输入:(]
输出:0
说明:该字符串无效

示例4

输入:([)]
输出:0
说明:该字符串无效

示例5

输入:)(
输出:0
说明:该字符串无效

解题思路

  1. 首先,创建一个空栈stack用于存储遇到的左括号。
  2. 初始化最大深度max_depth为0。
  3. 遍历字符串s中的每个字符c
    • 如果c是左括号('(', '[', '{'),将其压入栈中,并更新最大深度max_depth为当前栈的长度和已知最大深度之间的较大值。
    • 如果c是右括号(')', ']', '}'),则检查栈是否为空,或者栈顶元素是否与当前右括号匹配。如果不匹配,说明括号不匹配,返回0。如果匹配,将栈顶元素弹出。
  4. 遍历结束后,如果栈为空,说明所有括号都匹配,返回最大深度max_depth;否则,说明有未匹配的括号,返回0。
def max_depth(s):stack = []max_depth = 0for c in s:if c in '([{':stack.append(c)max_depth = max(max_depth, len(stack))elif c in ')]}':if not stack or (c == ')' and stack[-1] != '(') or (c == ']' and stack[-1] != '[') or (c == '}' and stack[-1] != '{'):return 0stack.pop()return max_depth if not stack else 0# 测试示例
print(max_depth("[]"))  # 输出:1
print(max_depth("([]{()})"))  # 输出:3
print(max_depth("(]"))  # 输出:0
print(max_depth("([)]"))  # 输出:0
print(max_depth(")("))  # 输出:0

http://www.ppmy.cn/news/1365124.html

相关文章

基于EKF扩展卡尔曼滤波的传感器网络目标跟踪matlab仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 MATLAB2022a 3.部分核心程序 .....................................................................% 定义初始位置的均…

STL unordered_set/unordered_map 不能默认hash vector?

背景 最近在做项目的过程中&#xff0c;遇到使用unordered_set 使用的一个bug&#xff0c;这里简单来记录一下。 例子 #include <iostream> #include <vector> #include <set> #include <stack> #include <algorithm> #include <map> #i…

uniapp的扩展组件uni-popup 弹出层自动打开

我的需求是在页面加载完之后自动打开弹窗&#xff0c;自动打开只能写在onReady 或 mounted 生命周期内&#xff0c;这是这个组件的规定&#xff1a; 如果想在页面渲染完毕后就打开 uni-popup &#xff0c;请在 onReady 或 mounted 生命周期内调用&#xff0c;确保组件渲染完毕…

【一】【计算机网络】win基本命令

检查自己的信息 以太网IPv4 地址就是本地计算机。 以太网适配器 VMware Network Adapter VMnet1的IPv4 地址不是本地计算机。局域网内其他的计算机。 C:\Users\205>ipconfigWindows IP 配置以太网适配器 以太网:连接特定的 DNS 后缀 . . . . . . . :本地链接 IPv6 地址. .…

day02_前后端环境搭建(前端工程搭建,登录功能说明,后端项目搭建)

文章目录 1. 软件开发介绍1.1 软件开发流程1.2 角色分工1.3 软件环境1.4 系统的分类 2. 尚品甄选项目介绍2.1 电商基本概念2.1.1 电商简介2.1.2 电商模式B2BB2CB2B2CC2BC2CO2O 2.2 业务功能介绍2.3 系统架构介绍2.4 前后端分离开发 3. 前端工程搭建3.1 Element-Admin简介3.2 El…

目标跟踪之KCF详解

High-Speed Tracking with Kernelized Correlation Filters 使用内核化相关滤波器进行高速跟踪 大多数现代跟踪器的核心组件是判别分类器&#xff0c;其任务是区分目标和周围环境。为了应对自然图像变化&#xff0c;此分类器通常使用平移和缩放的样本补丁进行训练。此类样本集…

Eureka服务搭建

1️⃣搭建服务 引入依赖 <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-netflix-eureka-server</artifactId></dependency>启动类加注解 EnableEurekaServer SpringBootApplication public…

【从零开始学习重要知识点 | 第一篇】快速了解什么是幂等性以及常见解决方案

前言&#xff1a; 当我们在设计和实现分布式系统时&#xff0c;幂等性是一个非常重要的概念。幂等性可以简单地理解为&#xff1a;对于同一操作&#xff0c;不论执行多少次&#xff0c;产生的影响都是相同的。这个概念在分布式系统中非常重要&#xff0c;因为在这种环境下&…

【机器人最短路径规划问题(栅格地图)】基于蚁群算法求解

基于蚁群算法求解机器人最短路径规划问题的仿真结果 仿真结果 收敛曲线变化趋势 蚁群算法求解最优解的机器人运动路径 各代蚂蚁求解机器人最短路径的运动轨迹

利用Spring Boot实现MQTT在物联网中的应用

在物联网&#xff08;IoT&#xff09;领域&#xff0c;消息队列遵循发布/订阅模型的MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;协议变得越来越受欢迎。本文将深入探讨如何在Spring Boot中使用MQTT&#xff0c;并讨论其与其他中间件的集成以及在物联网中…

【vue】vue 是怎么把 template 模版编译成 render 函数的,什么是AST抽象语法树

什么是AST 抽象语法树 是一个对象/或者json是一个数据结构 AST通常是由多个节点组成的树状结构&#xff0c;每个节点代表一个语法单位或表达式。节点之间的关系通过父子关系或兄弟关系来表示程序的结构。在不同的编程语言和工具中&#xff0c;AST可能有不同的表示方式和节点类…

【深度学习笔记】深度卷积神经网络——NiN

网络中的网络&#xff08;NiN&#xff09; LeNet、AlexNet和VGG都有一个共同的设计模式&#xff1a;通过一系列的卷积层与汇聚层来提取空间结构特征&#xff1b;然后通过全连接层对特征的表征进行处理。 AlexNet和VGG对LeNet的改进主要在于如何扩大和加深这两个模块。 或者&am…

FPGA 与 数字电路的关系 - 这篇文章 将 持续 更新 :)

先说几个逻辑&#xff1a;&#xff08;强调一下在这篇文章 输入路数 只有 1个或2个&#xff0c;输出只有1个&#xff0c;N个输入M个输出以后再说&#xff09; 看下面的几个图&#xff1a; 图一&#xff08; 忘了 这是 啥门&#xff0c;不是门吧 &#xff1a;&#xff09;也就…

Swagger接口文档管理工具

Swagger 1、Swagger1.1 swagger介绍1.2 项目集成swagger流程1.3 项目集成swagger 2、knife4j2.1 knife4j介绍2.2 项目集成knife4j 1、Swagger 1.1 swagger介绍 官网&#xff1a;https://swagger.io/ Swagger 是一个规范和完整的Web API框架&#xff0c;用于生成、描述、调用和…

Day03:Web架构OSS存储负载均衡CDN加速反向代理WAF防护

目录 WAF CDN OSS 反向代理 负载均衡 思维导图 章节知识点&#xff1a; 应用架构&#xff1a;Web/APP/云应用/三方服务/负载均衡等 安全产品&#xff1a;CDN/WAF/IDS/IPS/蜜罐/防火墙/杀毒等 渗透命令&#xff1a;文件上传下载/端口服务/Shell反弹等 抓包技术&#xff1a…

迭代器模式(Iterator Pattern)

定义 迭代器模式&#xff08;Iterator Pattern&#xff09;是一种行为型设计模式&#xff0c;它提供了一种方法来顺序访问聚合对象中的各个元素&#xff0c;而不需要暴露该对象的内部表示。迭代器模式使得客户端代码能够独立于聚合对象的具体实现进行遍历操作。 在迭代器模式…

SD-WAN技术:优化国内外服务器访问的关键

在全球化的商业环境中&#xff0c;企业经常需要在国内访问国外的服务器。然而&#xff0c;由于地理位置和网络架构的限制&#xff0c;这种跨国访问往往会遇到速度慢、延迟高等问题。SD-WAN&#xff08;软件定义广域网&#xff09;技术的兴起&#xff0c;为企业提供了一种新的解…

sql 分割字段,并分行

创建测试表格 CREATE TABLE test (id INT PRIMARY KEY, data VARCHAR(100)); INSERT INTO test VALUES (1, A,B,C); INSERT INTO test VALUES (2, D,E,F,G);查询并分割字段 SELECT id, value AS split_data FROM test CROSS APPLY STRING_SPLIT(data, ,) WHERE LEN(value) …

10:00面试,10:05就出来了,问的问题过于变态了。。。

我从一家小公司转投到另一家公司&#xff0c;期待着新的工作环境和机会。然而&#xff0c;新公司的加班文化让我有些始料未及。虽然薪资相对较高&#xff0c;但长时间的工作和缺乏休息使我身心俱疲。 就在我逐渐适应这种高强度的工作节奏时&#xff0c;公司突然宣布了一则令人…

了解 Go 中原子操作的重要性与使用方法

引言 并发是现代软件开发的一个基本方面&#xff0c;而在 Go 中编写并发程序相对来说是一个相对轻松的任务&#xff0c;这要归功于其强大的并发支持。 Go 提供了对原子操作的内置支持&#xff0c;这在同步并发程序中起着至关重要的作用。在本篇博客文章中&#xff0c;我们将探…