【【Leetcode刷题笔记】栈刷题笔记】栈
目录目录一、有效的括号二、最小栈
一、有效的括号一、有效的括号
【题号】20
【题目描述】
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
【常规解法】
1.初始化栈 S。
2.一次处理表达式的每个括号。
3.如果遇到开括号,我们只需将其推到栈上即可。这意味着我们将稍后处理它,让我们简单地转到前面的 子表达式。
4.如果我们遇到一个闭括号,那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹
出并继续处理。否则,这意味着表达式无效。
5.如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。
【我的代码】
class Stack(object):
def __init__(self, limit=10):
self.stack = [] #存放元素
self.limit = limit #栈容量极限
def push(self, data): #判断栈是否溢出
if len(self.stack) >= self.limit:
print('StackOverflowError')
pass
self.stack.append(data)
def pop(self):
if self.stack:
return self.stack.pop()
else:
#raise IndexError('pop from an empty stack') #空栈不能被弹出
return False
def peek(self): #查看堆栈的最上面的元素
if self.stack:
return self.stack[-1] def is_empty(self): #判断栈是否为空
return not bool(self.stack)
def size(self): #返回栈的大小
return len(self.stack)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = Stack(len(s))
for c in s:
if (c == '(') or (c=='{') or (c=='['):
stack.push(c)
elif c==')':
if(stack.pop()!='('):