今日挑战
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
示例 1:
输入: "()"输出: true
示例 2:
输入: "()[]{}"输出: true
示例 3:
输入: "(]"输出: false
示例 4:
输入: "([)]"输出: false
示例 5:
输入: "{[]}"输出: true
这道题很有意思,其实它和我们的日常写sql很有联系,就是当我们写漏或者写多括号的时候,编辑器会提示我们错误,而我们这道题,就是实现这个功能。
先思考一下,后面我会给出一个解题思路~?
图来自网络
这道题目,我们会用到栈的知识点,在使用栈之前,我们先说明一下一些名词。
我们大致通过下面的步骤来实现:
1 )初始化栈 S;
2 )依次遍历所有的括号,如果遇到左括号,我们只需将其推到栈上即可;
3 )如果我们遇到一个右括号,那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效;
4 )如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。
大家可以看下我画的示意图:
Python实现:
def isValid(s):
# 初始化一个栈
stack = []
# 设置左右括号的对应关系
mapping = {")": "(", "}": "{", "]": "["}
# 遍历所有的元素(即括号)
for char in s:
# 当前元素为右括号
if char in mapping:
# 抽取当前栈的栈顶元素,如果为空,则赋值为 #
top_element = stack.pop() if stack else '#'
# 如果栈顶元素不等于当前的右括号对应的左括号,则直接返回 False
if mapping[char] != top_element:
return False
# 当前元素为左括号
else:
# 直接放入栈顶
stack.append(char)
# 最后如果栈为空,代表表达式有效
return not stack
? 配图角色背景介绍
冬日战士(Winter Soldier)是美国漫威漫画旗下超级英雄,初次登场于《美国队长》(Captain America)第1期(1941年3月),作为冬日战士首次出现于《美国队长》第5卷第1期(2005年1月),由乔·西蒙以及杰克·科比联合创造。本名詹姆斯·布坎南·巴恩斯 / 巴基·巴恩斯(James Buchan Barnes / Bucky Barnes),是美国队长在二战中最亲密的战友和最坚实的后盾,后来在二战尾声的一次行动中,与队长一同掉入大海之中被冰封。但是不同的是,九头蛇的人发现并解冻了他,还在他的断臂处安装上了机械手臂,并将其洗脑训练成了只效忠九头蛇的特工“冬日战士”(Winter Soldier)。此后巴基以冬日战士的身份为邪恶组织九头蛇在世界各地完成各种刺杀任务,后在与复仇者成员多次较量中恢复记忆,背叛了九头蛇,并被好友美国队长邀请加入复仇者联盟。