打卡Day11
- 1.232.用栈实现队列
- 2.225. 用队列实现栈
- 3.20. 有效的括号
- 4.1047. 删除字符串中的所有相邻重复项
1.232.用栈实现队列
题目链接：用栈实现队列
文档讲解： 代码随想录
思路：需要用两个栈来实现队列的先进先出。一个输入栈，一个输出栈，用来调整数据出栈的顺序。在push数据的时候，只要将数据放入输入栈；而在输出的时候，就需要将数据先读入输出栈，再弹出。弹出数据的过程，要注意判断输出栈是否为空。
class MyQueue(object):
def __init__(self):
self.stack_in = []
self.stack_out = []
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_in.append(x);
def pop(self):
"""
:rtype: int
"""
if self.empty():
return None
#当stack_out为空的时候才从stack_in导入
if self.stack_out:
return self.stack_out.pop()
else:
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self):
"""
:rtype: int
"""
#直接使用pop函数
ans = self.pop()
#因为弹出，所以要再添加进去
self.stack_out.append(ans)
return ans
def empty(self):
"""
:rtype: bool
"""
#两个栈中都没有元素才为空
return not (self.stack_in or self.stack_out)
2.225. 用队列实现栈
题目链接：用队列实现栈
文档讲解： 代码随想录
class MyStack(object):
def __init__(self):
self.queue_in = deque()
self.queue_out = deque()
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.queue_in.append(x)
def pop(self):
"""
:rtype: int
"""
#确定是否为空
if self.empty():
return None
#将queue_in中除最后一个元素取出存放在queue_out中
for i in range(len(self.queue_in) - 1):
self.queue_out.append(self.queue_in.popleft())
#将queue_in和queue_out对换
self.queue_in, self.queue_out = self.queue_out, self.queue_in
#弹出
return self.queue_out.popleft()
def top(self):
"""
:rtype: int
"""
ans = self.pop()
self.queue_in.append(ans)
return ans
def empty(self):
"""
:rtype: bool
"""
return len(self.queue_in) == 0
3.20. 有效的括号
题目链接：有效的括号
文档讲解： 代码随想录
由于栈结构的特殊性，非常适合做对称匹配类的题目。括号匹配时使用栈解决的经典问题。一共三种情况。
（1）左括号多了。
（2）左右括号不对称。
（3）右括号多了。
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
for item in s:
if item == '(':
stack.append(')')
elif item == '{':
stack.append('}')
elif item == '[':
stack.append(']')
#右括号多了或者不匹配
elif not stack or stack[-1] != item:
return False
else:
stack.pop()
#左括号多了
#return True if not stack else False
if not stack:
return True
else:
return False
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
mapping = {
'(': ')',
'{': '}',
'[': ']'
}
for item in s:
if item in mapping.keys():
stack.append(mapping[item])
elif not stack or stack[-1] != item:
return False
else:
stack.pop()
return True if not stack else False
4.1047. 删除字符串中的所有相邻重复项
题目链接：删除字符串中的所有相邻重复项
文档讲解： 代码随想录
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
stack= []
for item in s:
#需要判断stack中有元素
if stack and stack[-1] == item:
stack.pop()
else:
stack.append(item)
return ''.join(stack)
还有一个双指针的版本，作为如果不让用栈的解决方法。
class Solution(object):
def removeDuplicates(self, s):
"""
:type s: str
:rtype: str
"""
#不可以对字符串进行修改
res = list(s)
slow = fast = 0
length = len(s)
#用while循环
while fast < length:
#如果相邻不同
res[slow] = res[fast]
#如果相邻相同
if slow > 0 and res[slow] == res[slow - 1]:
slow -= 1
else:
slow += 1
fast += 1
return ''.join(res[:slow])
要注意的点就是，最后返回的时候 res 的长度是 0 到 slow。
