我今天才知道，我之所以漂泊就是在向你靠近。
- 2019 年 10 月 5 日
- 筆記
LeetCode之栈(11)
0.说在前面
1.有效的括号
2.作者的话
0.说在前面
“旧梦是好梦。它没有实现，但是我很高兴我有过这些梦。”
我的梦在哪里，在LeetCode!
关于LeetCode刷题，与老表建立的微信群，目前已经坚持一个月了，收获很多，昨天跟老表沟通后，公开所有读者进群，只要你能够坚持刷题，坚持分享，便可以共同进步！
我今天才知道，我之所以漂泊就是在向你靠近。
又到了周二时间，今天来讨论的是LeetCode上的题目，今天主要以三种方法来刷一道非常简单的题目，有效的括号问题！
昨天的泰坦尼克号后面陆续更新。
1.有效的括号
【问题】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true
示例 2:
输入: "()[]{}" 输出: true
【方法一】
思想
这道题最关键是理解什么是括号匹配！
对于本道题的括号匹配实际上为只要连续两个括号为一组，则需要把当前一组删除掉继续判断！
这里说的连续两个括号：意思为，例如：([])，这种肯定为True，内部[]连续并构成一组，那么我们需要把当前的一组删除，然后继续判断，会发现后面的括号与前面也构成一组()，然后就为True!
对于这道题，在考研阶段看的两本书：王道与天勤数据结构上，明确提到过对于括号问题，采用的数据结构为栈！
在这里我们也是用栈，只不过用的python实现。
这里的数据结构，我定义为:
# 栈中元素初始化 stack_len=0 # 栈数据结构直接设为list stack=[]
然后，只要是左括号或者说前括号，就入栈，否则出栈，记得最后判断栈中元素是否为空。
算法
class Solution: def isValid(self, s): # 栈中元素初始化 stack_len=0 # 栈数据结构直接设为list stack=[] for i in s: # 前括号入栈 if i=='(' or i=='{' or i=='[': stack_len+=1 stack.append(i) # 后括号匹配 else: if stack and i==')' and stack[-1]=='(': stack.pop() stack_len-=1 elif stack and i=='}' and stack[-1]=='{': stack.pop() stack_len-=1 elif stack and i==']' and stack[-1]=='[': stack.pop() stack_len-=1 ''' 下面这两行非常重要！ 主要用于判别当栈中没有元素进来是后面的符号， 或者是栈有元素，但是不匹配，那么直接返回False即可！ ''' else: return False # 栈空为True，否则False return stack_len==0 s = Solution() t = "(]" res = s.isValid(t) print(res)
复杂度
时间复杂度：O(n)；空间复杂度：O(n)，由于使用了栈存储元素，故最多为O(n)!
击败99.06%，基本完美！
【方法二】
思想
采用的数据结构同上，对上述算法进行改进，不同之处，使用字典提前存储括号！
算法
class Solution: def isValid(self, s): stack_match = {'{':'}','[':']','(':')'} stack=[] for str in s: if str == '{' or str == '[' or str== '(': stack.append(str) else: # 无左括号，只有右括号，直接返回False if len(stack)==0: return False # 栈顶元素对应的字符串是否匹配当前字符 if stack_match[stack.pop()]!=str: return False flag = True if len(stack)==0 else False return flag s = Solution() t = "{[]}" res = s.isValid(t) print(res)
击败99.06%，基本完美！
复杂度
同方法一
【方法三】
思想
也是用的栈数据结构思想，不同之处是字典括号，key与value设置不同。
算法
参考自：https://www.jianshu.com/p/f67fab550282
class Solution: def isValid(self,s): dict = {')': '(', '}': '{', ']': '['} l = [None] for i in s: if i in dict and dict[i] == l[-1]: l.pop() else: l.append(i) return len(l) == 1
复杂度
同上述两个算法！
但是，测试的结果没前两个好….
击败76.55%，还可以！
