1 leetcode232.用栈实现队列
题目链接：232. 用栈实现队列 - 力扣（LeetCode）
文章链接：代码随想录
视频链接：栈的基本操作！ | LeetCode：232.用栈实现队列哔哩哔哩bilibili
自己的思路：真的第一次接触这个概念，完全没有任何思路，甚至不知道从何下手
1.1 基本概念
-
栈就是相当于砌墙的砖头，先进后出，先放进去的元素最后才能出来，有个底兜着
-
队列就好像我们排队去看展览一样，先进先出，先进去看完就先出来，去做别的事情
-
用栈实现队列，那么就是在开辟一个栈，将之前栈里的内容全部存储到新的栈里面，然后再进行输出，就实现了队列
1.2 视频后的操作
思路:
-
对元素推到末尾，对于栈而言就是入栈，所以直接在空列表中加入数据
-
队列开头元素移除并返回移除的元素
-
那么根据栈的知识，就是首先判断所构建的队列是不是空的，如果是空的就没办法移除，先判断完成
-
然后要判断出栈的列表有没有值，有值也无法完成操作
-
出栈列表为空以后，然后对出栈列表进行元素加进去，并对入栈的列表进行删除
-
返回出栈列表的第一个数
-
-
返回列表的开头数，就是先将出栈的头部数值拿出来，拿出来以后还需要将其放回出栈中，所以需要一个相当于存储的东西，最后返回存储的值
-
判断列表是不是空的，空的返回
true，有值就返回false那么就是先对其入栈列表和出栈列表求一下二者有没有值，有值会是true，然后在进行not true即可
class MyQueue: def __init__(self): self.stack_in = [] self.stack_out = [] def push(self, x: int) -> None: return self.stack_in.append(x) def pop(self) -> int: if self.empty(): return None 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) -> int: ans = self.pop() self.stack_out.append(ans) return ans def empty(self) -> bool: return not(self.stack_in or self.stack_out) # Your MyQueue object will be instantiated and called as such: # obj = MyQueue() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.peek() # param_4 = obj.empty()
1.3 本题小结
-
出入这种题，才开始被这个概念吓到了，其实仔细一看，就是列表的一种创建方式吧，对于python语言来说，对于其他语言可能有更多不同的方法吧
-
这道题学会了一种类别函数里面的函数之间的调用方法，挺强大的，感觉自己以后也可以这么写代码，之前的代码真的写的不是很行
2 leetcode225. 用队列实现栈
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
文章链接：代码随想录
视频链接：队列的基本操作！ | LeetCode：225. 用队列实现栈哔哩哔哩bilibili
自己的思路：根据前一道题的思路，想着再建立一个队列，然后对其进行放数值
2.1 看视频后的思路
2.1.1 两个队列的方法
思路：
-
建立一个
deque的数据形式，然后使用里面的append是添加元素，以及popleft来移除元素 -
其他的其实思路和栈的相似
from collections import deque class MyStack: def __init__(self): self.queue_in = deque() self.queue_out = deque() def push(self, x: int) -> None: return self.queue_in.append(x) def pop(self) -> int: if self.empty(): return None for i in range(len(self.queue_in)-1): self.queue_out.append(self.queue_in.popleft()) self.queue_in,self.queue_out = self.queue_out,self.queue_in return self.queue_out.popleft() def top(self) -> int: if self.empty(): return None tmp = self.pop() self.queue_in.append(tmp) return tmp def empty(self) -> bool: return len(self.queue_in)==0 # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
2.1.2 用一个列表实现的方法
思路:
这个思路超级简单，就是将移除的元素往后添加就好啦
from collections import deque class MyStack: def __init__(self): self.queue = deque() def push(self, x: int) -> None: return self.queue.append(x) def pop(self) -> int: if self.empty(): return None for i in range(len(self.queue)-1): self.queue.append(self.queue.popleft()) return self.queue.popleft() def top(self) -> int: tmp = self.pop() self.queue.append(tmp) return tmp def empty(self) -> bool: return len(self.queue)==0 # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
2.2 本题小结
-
关于python中的调用
deque的代码from collections import deque，这是一个双端队列的数据结构类型 -
其实发现这种题比链表简单，自己觉得难的时候是因为自己不想去尝试
3 leetcode20. 有效的括号
题目链接：225. 用队列实现栈 - 力扣（LeetCode）
文章链接：代码随想录
视频链接：队列的基本操作！ | LeetCode：225. 用队列实现栈哔哩哔哩bilibili
自己的思路：才开始的思路就是找到几个括号，找到了就返回True，否则就返回False
3.1 自己的代码
这个代码在所给的几个示例中是完全可以用的，但是在提交的时候，遇到了s ="(){}}{"示例的时候就报错了
class Solution:
def isValid(self, s: str) -> bool:
if ('()'in s) or ('[]' in s) or ('{}' in s):
return True
return False
看完视频以后我感觉我的思路上去就是错的，不过尝试了也就知道自己做这种题的不妥之处了
3.2 视频后的思路
3.2.1 使用栈
思路：
-
首先会出现的不对的类型进行划分，第一种是有左没右，第二种是括号匹配不上，第三种是右括号多余了
-
然后就是对题目的思考，首先如果这个括号是奇数，就一定不满足条件可以返回
-
然后就可以对括号进行存储，如果遇到左括号就存储右括号，这样的遇到了右括号出栈就会方便许多
-
但是对栈而言，更需要保证这个出栈的栈不为空，如果是空的就没有出的
-
循环结束后，如果栈为空，就是
True，否则也是false
class Solution:
def isValid(self, s: str) -> bool:
l_s = list()
if len(s)%2 !=0:
return False
for i in range(len(s)):
if s[i] == '(':
l_s.append(')')
elif s[i] == '[':
l_s.append(']')
elif s[i] == '{':
l_s.append('}')
elif l_s == [] or s[i] !=l_s[-1]:
return False
else:
l_s.pop()
return l_s == []
3.2.2 使用字典的方法
其实思路和栈的差不多，只是将栈的中间的存储数据的方式改了一下，这样好像运行变快了
class Solution:
def isValid(self, s: str) -> bool:
stack = list()
mapping = {'(':')','[':']','{':'}'}
if len(s)%2 !=0:
return False
for i in s:
if i in mapping.keys():
stack.append(mapping[i])
elif stack == [] or i !=stack[-1]:
return False
else:
stack.pop()
return stack == []
3.3 本题小结
-
这一道题主要就是思考的时候会有一些小问题，才开始没有想到这种题的一个思路，其次是对栈理解真的不够深，第一次接触就会有很多地方出问题
-
这道题让我更加深刻的理解了列表中的
append和pop函数，append函数在内部增加元素的时候，就是在最后面插入元素，pop删除元素也是同样的道理 -
还是会在if条件判断的时候将双等号写成单等号，希望以后少犯错误
4 leetcode1047. 删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
文章链接：代码随想录
视频链接：栈的好戏还要继续！| LeetCode：1047. 删除字符串中的所有相邻重复项哔哩哔哩bilibili
自己的思路：第一眼看上去我觉得和上一道题的思路非常像，但是下手的时候才开始没有办法，但是因为用python语言麻，实现的时候是列表存储，后面就想着其实顺序和那个本身顺序是一样的，直接加一个join函数就行了
4.1 自己的代码
class Solution: def removeDuplicates(self, s: str) -> str: stack = [] for i in s: if stack == [] or stack[-1]!= i: stack.append(i) else: stack.pop() return ''.join(stack)
4.2 看视频后的思路
这道题能想出双指针的方法，真的他们超聪明，我只能说理解了，但是自己写的话还是很有问题，自己用笔画了一遍写的，不是那么的熟练
class Solution: def removeDuplicates(self, s: str) -> str: stack = list(s) fast = slow = 0 length = len(stack) while fast<length: stack[slow] = stack[fast] if slow>0 and stack[slow]==stack[slow-1]: slow-=1 else: slow +=1 fast +=1 return ''.join(stack[0:slow])
4.3 本题小结
-
这道题真的可以说是上一题的扩展，思路挺简单的，我也学会啦
-
但是这道题双指针的方法也真的厉害的，不过如果直接看是有些迷惑的，但是练习以后就会好很多
5 今日小结
-
掌握的栈和队列，栈是先进后出，队列是先进先出
-
对于python而言使用列表即可模仿栈，对于队列的模仿，需要从
collections库中调用deque，然后进行操作 -
对于第三题，主要是思路上的问题，需要掌握这种思路，分析问题的能力很重要吧