当前位置: 首页 > news >正文

Python面试宝典第6题:有效的括号

题目

        给定一个只包括 '('、')'、'{'、'}'、'['、']' 这些字符的字符串,判断该字符串是否有效。有效字符串需要满足以下的条件。

        1、左括号必须用相同类型的右括号闭合。

        2、左括号必须以正确的顺序闭合。

        3、每个右括号都有一个对应的相同类型的左括号。

        注意:空字符串可被认为是有效字符串。

        示例 1:

输入: "([])"
输出: true

        示例 2:

输入: "()[]{}"
输出: true

        示例 3:

输入: "(]"
输出: false

        示例 4:

输入: "([)]"
输出: false

递归法

        本题可以采用递归的方式来解决,递归的基本思想是不断地将问题分解为更小的子问题。对于当前的字符串,如果它是有效括号字符串,那么它要么为空,要么可以分为两部分:第一个部分包含一个左括号、一个有效括号字符串、一个对应的右括号,第二部分包含另一个有效括号字符串(如果存在的话)。通过这种方式,我们可以递归地检查字符串的每一部分是否有效。使用递归法求解本题的主要步骤如下。

        1、如果字符串为空,直接返回true,因为空字符串视为有效。

        2、如果字符串长度为奇数,直接返回false,因为有效的括号字符串长度必须是偶数。

        3、从字符串的第一个字符开始,找到第一个闭合的括号对(即左括号和其对应的右括号)。如果找不到成对的括号,说明字符串无效,返回false。

        4、将字符串分割为两部分:中间的有效括号对、右边的子字符串(从找到的右括号之后的部分)。

        5、递归地检查子字符串是否有效,如果都有效,则整个字符串有效。否则,无效。

        注意:虽然递归法在理论上可行,但它在处理长字符串时,可能会导致调用栈溢出。递归法更多地是作为一种算法思维的展示,帮助理解问题的分解过程,故这里就不给出具体的源码实现了。

栈方法

        对于括号匹配问题,最直观的方法是使用栈数据结构来解决。首先遍历整个字符串,每次遇到左括号时,将其压入栈中。每次遇到右括号时,检查栈顶元素是否为对应的左括号。如果是,则弹出栈顶元素,继续遍历。如果不是,则直接判定该字符串无效。遍历结束后,如果栈为空,则说明所有括号都已正确匹配。使用栈方法求解本题的主要步骤如下。

        1、初始化一个空栈。

        2、遍历字符串中的每一个字符,做如下判断。

        (1)如果字符是'('、'{' 、'[',将其压入栈中。

        (2)如果字符是')'、'}' 、']',检查栈顶元素是否为其对应的左括号。如果是,弹出栈顶元素。如果不是,直接返回false。

        3、遍历完成后,检查栈是否为空。为空则返回true,表示所有括号都已正确匹配。不为空则返回false,表示存在未匹配的括号。

        根据上面的算法步骤,我们可以得出下面的示例代码。

def is_valid_brackets(s: str) -> bool:bracket_map = {")": "(", "}": "{", "]": "["}stack = []for char in s:if char in bracket_map:# 如果栈为空,或者栈顶元素不是对应的左括号,返回falseif not stack or stack[-1] != bracket_map[char]:return Falsestack.pop()  # 匹配成功,弹出栈顶元素else:# 左括号直接入栈stack.append(char)return not stack  # 栈为空则返回true,表示所有括号都已正确匹配# 输出:True
print(is_valid_brackets("([])"))
# 输出:True
print(is_valid_brackets("()[]{}"))
# 输出:False
print(is_valid_brackets("(]"))
# 输出:False
print(is_valid_brackets("([)]"))

总结

        使用栈结构处理括号匹配问题的时间复杂度是O(n),空间复杂度也是O(n)。在处理括号匹配这类问题时,栈结构是极其高效且直观的选择。它能够自然地处理“后进先出”的特性,完美符合括号匹配的场景。

相关文章:

Python面试宝典第6题:有效的括号

题目 给定一个只包括 (、)、{、}、[、] 这些字符的字符串,判断该字符串是否有效。有效字符串需要满足以下的条件。 1、左括号必须用相同类型的右括号闭合。 2、左括号必须以正确的顺序闭合。 3、每个右括号都有一个对应的相同类型的左括号。 注意:空字符…...

Windows上使用Navicat连接ubuntu上的mysql8报错:10061和1130

问题一:can’t connect to mysql server on ‘192.168.xxx.xxx’(10061) 解决: sudo vim /etc/mysql/mysql.conf.d/mysqld.cnf,bind-address绑定了登陆的IP,把这两行代码注释掉,然后重启mysql。 问题二:1…...

Feign远程调用,请求头丢失情况

现象 解决方案 import feign.RequestInterceptor; import feign.RequestTemplate; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.web.context.request.RequestContextHolde…...

Windows 11 安装 安卓子系统 (WSA)

How to Install Windows Subsystem for Android (WSA) on Windows 11 新手教程:如何安装Windows 11 安卓子系统 说明 Windows Subsystem for Android 或 WSA 是由 Hyper-V 提供支持的虚拟机,可在 Windows 11 操作系统上运行 Android 应用程序。虽然它需…...

CD4017 – 带解码输出的十进制计数器

CD4017 IC 是一个十进制计数器,它有 10 个输出,分别代表 0 到 9 的数字。计数器在(14号引脚)每个时钟脉冲上升时增加 1。计数器达到 9 后,它会在下一个时钟脉冲时从 0 重新开始。 引脚名称管脚 #类型描述VD…...

Spring Boot 文件上传和下载指南:从基础到进阶

文章目录 引言1. 环境配置2. 文件上传2.1 配置文件上传路径2.2 创建上传服务2.3 创建上传控制器 3. 文件下载3.1 创建下载服务3.2 创建下载控制器 4. 前端页面4.1 文件上传页面4.2 文件下载页面 5. 技术分析结论 🎉欢迎来到SpringBoot框架学习专栏~ ☆* o(≧▽≦)o …...

Windows Server 2019部署网络负载均衡NLB服务的详细操作步骤

部署前准备 首先需要准备两台Windows Server 2019服务器,虚拟机创建请参考 VMware Workstation安装Windows Server2019系统详细操作步骤_安装windows server 2019操作系统(写出操作过程)-CSDN博客 克隆虚拟机请参考 VMware Workstation克隆虚拟机详细步骤-CSDN博…...

Java增加线程后kafka仍然消费很慢

文章目录 一、问题分析二、控制kafka消费速度属性三、案例描述 一、问题分析 Java增加线程通常是为了提高程序的并发处理能力,但如果Kafka仍然消费很慢,可能的原因有: 网络延迟较大:如果网络延迟较大,即使开启了多线…...

分布式事务实现技术及考虑点

什么是分布式事务? 首先理解什么是本地事务 平时我们在程序中通过Spring去控制事务是利用数据库本身的事务特性来实现的,因此叫数据库事务,由于应用主要靠关系数据库来控制事务,而数据库通常和应用在同一个服务器,所…...

JavaScript中闭包的理解

闭包(Closure)概念:一个函数对周围状态的引用捆绑在一起,内层函数中访问到其外层函数的作用域。简单来说;闭包内层函数引用外层函数的变量,如下图: 外层在使用一个函数包裹住闭包是对变量的保护&#xff0c…...

传统IO和NIO文件拷贝过程

参考:https://blog.csdn.net/weixin_57323780/article/details/130250582...

算法思想总结:优先级队列

一、最后一块石头的重量 . - 力扣(LeetCode) 我们每次都要快速找到前两个最大的石头进行抵消,这个时候用优先级队列(建大堆),不断取堆顶元素是最好的!每次删除堆顶元素后,可以自动调整&#xf…...

《米小圈日记魔法》边看边学,轻松掌握写日记的魔法!

在当今充满数字化娱乐和信息快速变迁的时代,如何创新引导孩子们学习,特别是如何培养他们的写作能力,一直是家长和教育者们关注的焦点。今天就向大家推荐一部寓教于乐的动画片《米小圈日记魔法》,该系列动画通过其独特的故事情节和…...

鸿蒙应用实践:利用扣子API开发起床文案生成器

前言 扣子是一个新一代 AI 应用开发平台,无需编程基础即可快速搭建基于大模型的 Bot,并发布到各个渠道。平台优势包括无限拓展的能力集(内置和自定义插件)、丰富的数据源(支持多种数据格式和上传方式)、持…...

二手物品交易小程序的设计

管理员账户功能包括:系统首页,个人中心,用户管理,管理员管理,商品信息管理,论坛管理,收货地址管理,基础数据管理 微信端账号功能包括:系统首页,商品信息&…...

基于Spring Boot的高校智慧采购系统

1 项目介绍 1.1 摘要 随着信息技术与网络技术的迅猛发展,人类社会已跨入全新信息化纪元。传统的管理手段因其内在局限,在处理海量信息资源时日渐捉襟见肘,难以匹配不断提升的信息管理效率和便捷化需求。顺应时代发展趋势,各类先…...

数字流的秩

题目链接 数字流的秩 题目描述 注意点 x < 50000 解答思路 可以使用二叉搜索树存储出现的次数以及数字的出现次数&#xff0c;方便后续统计数字x的秩关键在于构建树的过程&#xff0c;如果树中已经有值为x的节点&#xff0c;需要将该节点对应的数字出现次数加1&#xf…...

【mybatis】mybatis-plus中Wrapper(条件构造器)简介_常用方法及说明

1、简介 MyBatis-Plus 是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。MyBatis-Plus 提供了强大的条件构造器&#xff08;Wrapper&#xff09;&#xff0c;用于构建复杂的 SQL 查询条件&#xff0c;使得我们…...

IT专业入门:高考假期预习指南

七月&#xff0c;是一个充满转折与希望的月份。随着各省高考分数的揭晓&#xff0c;许多有志于踏入IT领域的少年们正站在新旅程的起点上。高考的完结并不意味着学习的结束&#xff0c;相反&#xff0c;它是一个全新的开始&#xff0c;一个探索未知世界的绝佳时机。作为IT领域的…...

推动高效能:东芝TB67H301FTG全桥直流电机驱动IC

在如今高度自动化的时代&#xff0c;电子产品的性能和效率成为了工程师们关注的焦点。东芝的TB67H301FTG全桥直流电机驱动IC应运而生&#xff0c;以其卓越的技术和可靠性&#xff0c;成为众多应用的理想选择。无论是在机器人、家用电器、工业自动化&#xff0c;还是在其他需要精…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...