当前位置:网站首页>【LeetCode】老虎证券面试-括号嵌套且满足优先级
【LeetCode】老虎证券面试-括号嵌套且满足优先级
2022-08-03 08:51:00 【凝眸伏笔】
LeetCode第20题:简单括号 力扣
题目描述:
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
例子:
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([)]"
输出:false
示例 5:
输入:s = "{[]}"
输出:true
解题思路:
- 如果 c 是左括号,则入栈 pushpush;
- 否则通过哈希表判断括号对应关系,若 stack 栈顶出栈括号 stack.pop() 与当前遍历括号 c 不对应,则提前返回 falsefalse。
解决边界问题:
- 栈 stack 为空: 此时 stack.pop() 操作会报错;因此,我们采用一个取巧方法,给 stack 赋初值 ?? ,并在哈希表 dic 中建立 key: '?',value:'?'key: ′? ′,value: ′? ′的对应关系予以配合。此时当 stack 为空且 c 为右括号时,可以正常提前返回 falsefalse;
- 字符串 s 以左括号结尾: 此情况下可以正常遍历完整个 s,但 stack 中遗留未出栈的左括号;因此,最后需返回 len(stack) == 1,以判断是否是有效的括号组合。
解题代码:
class Solution:
def isValid(self, s: str) -> bool:
stack = ['?']
kv = {'(':')', '[':']', '{':'}','?':'?'}
for ch in s:
if ch in kv.keys():
stack.append(ch)
elif stack and kv[stack.pop()] != ch: return False
res = False
if len(stack) == 1:
res = True
return res
题目变种:
题目描述:
要求括号,满足:
- 成对出现
- 满足嵌套关系,{}中,可以有[], ()
解题思路:
在上述解题思路的基础上,在入栈的时候,做一个嵌套优先级的判断.
解题代码:
def isValid(s):
stack = ['?']
kv = {'(':')', '[':']', '{':'}','?':'?'}
for ch in s:
if ch in kv.keys():
if ch == '{' and len(stack) >=2 and stack[-1] in {'(', '['}:
return False
if ch == '[' and len(stack) >=2 and stack[-1] in {'('}:
return False
stack.append(ch)
elif kv[stack.pop()] != ch: return False
res = False
if len(stack) == 1:
res = True
return res
边栏推荐
猜你喜欢
Exception: Dataset not found.解决办法
【TPC-DS】DF的SQL(Data Maintenance部分)
LeetCode第三题(Longest Substring Without Repeating Characters)三部曲之二:编码实现
redis stream 实现消息队列
【论文笔记】一种基于启发式奖赏函数的分层强化学习方法
LINGO 18.0软件安装包下载及安装教程
Qt 下拉复选框(MultiSelectComboBox)(一) 实现下拉框多选,搜索下拉框内容
行业洞察 | 如何更好的实现与虚拟人的互动体验?
【微信小程序】底部有安全距离,适配iphone X等机型的解决方案
数据监控平台
随机推荐
dflow入门3——dpdispatcher插件
内存模型之可见性
flutter 应用 抓包
并发之多把锁和活跃性
【愚公系列】2022年07月 Go教学课程 026-结构体
关于Unity,Laya学习,第一步加载Unity加载场景
QT中线程调用GUI主线程控件的问题
Laya中关于摄像机跟随人物移动或者点击人物碰撞器触发事件的Demo
MySQL1
ArcEngine (5) use the ICommand interface to achieve zoom in and zoom out
进程信息
The Transformer, BERT, GPT paper intensive reading notes
MySQL-存储过程-函数-
QImage的指针问题
【收获合辑】k-NN与检索任务的异同+jupyter转pdf
内存模型之有序性
Exch:重命名或删除默认邮箱数据库
LINGO 18.0 software installation package download and installation tutorial
【LeetCode】112.路径总和
Qt 下拉复选框(MultiSelectComboBox)(一) 实现下拉框多选,搜索下拉框内容