Okii's blog

仅作为记录自己的学习过程

0%

Leetcode 栈和队列篇

发表于 分类于
本文字数： 4.6k 阅读时长 ≈ 8 分钟

Leetcode刷题记录——栈和队列篇

Leetcode232 用栈实现队列

用一个栈肯定模拟不了队列的操作

要用两个栈

一个负责push，另一个负责pop

  • 在push数据的时候，只要数据放进输入栈就好

  • 但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入）,再从输出栈弹出数据，如果输出栈不为空，则直接从输出栈弹出数据就可以了

  • 如果进栈和出栈都为空的话，说明模拟的队列为空了

注意：代码能复用的地方复用，不要再另外写逻辑

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class MyQueue:

    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        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()

Leetcode225 用队列实现栈

用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用

把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素(相当于弹出栈顶元素)，再把其他元素从que2导回que1

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from collections import deque
class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        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
        return self.queue_in[-1]

    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()

Leetcode20 有效的括号

遇到左字符{、[、(时压入栈

碰到右字符时，先检查栈是否为空，为空直接False

在检查是否与栈顶元素成对匹配，不匹配直接False，是的话栈顶元素出栈

最后检查栈是否为空，为空说明全部能成对，返回True

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        for i in s:
            if i == '(' or i == '[' or i == '{':
                stack.append(i)
            elif i == ')':
                if not stack:
                    return False
                elif stack[-1] != '(':
                    return False
                else:
                    stack.pop()
            elif i == ']':
                if not stack:
                    return False
                elif stack[-1] != '[' :
                    return False
                else:
                    stack.pop()
            elif i == '}':
                if not stack:
                    return False
                elif stack[-1] != '{' :
                    return False
                else:
                    stack.pop()
        if len(stack) != 0:
            return False
        else:
            return True

Leetcode1047 删除字符串中的所有相邻重复项

遍历s ，如果栈非空并且栈顶元素等于当前正在遍历元素的话

栈顶元素出栈，否则，当前正在遍历元素压入栈

遍历到最后只剩下不重复的字符

Python代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for i in s:
            if stack and stack[-1] == i:
                stack.pop()
            else:
                stack.append(i)
        return ''.join(stack)

Leetcode150 逆波兰式表达求值

遇到数字则入栈；遇到运算符则取出栈顶两个数字进行计算，并将结果压入栈中

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from operator import add, sub, mul
class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        op = {'+': add, '-':sub , '*':mul, '/':lambda x, y : int(x/y)}
        stack = []
        for i in tokens:
            if i not in {'+', '-', '*', '/'}:
                # 也可以在这写stack.append(int(token)) 后面就不用那么多int()了
                stack.append(i)
            else:
                num2 = int(stack.pop())
                num1 = int(stack.pop())
                # 第一个出来的在运算符后面
                temp_num = op[i](num1, num2)
                stack.append(temp_num)
        return int(stack.pop())

Leetcode239 滑动窗口最大值

其实队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。

设计单调队列的时候，pop，和push操作要保持如下规则：

  1. pop(self, value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。因为push的时候会将元素小的弹出了。
  2. push(self, value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止

保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。

Python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from collections import deque
class MyQueue:
    def __init__(self):
        self.queue = deque()
    
    def pop(self, value):
        if self.queue and value == self.queue[0]:
            self.queue.popleft()
    
    def push(self, value):
        # 不是value >= self.queue[-1] value等于队列末尾的时候不能弹出，依然要维护，因为窗口会移动的
        while self.queue and value > self.queue[-1]:
            self.queue.pop()
        self.queue.append(value)
    
    def front(self):
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = MyQueue()
        res = []
        for i in range(k):
            que.push(nums[i])
        res.append(que.front())
        for i in range(k, len(nums)):
            # 弹出的是窗口左端前面的那个, 所以是i-k, 错的时候写成了i-k+1
            que.pop(nums[i-k])
            que.push(nums[i])
            res.append(que.front())
        return res

Leetcode347 前K个高频元素

总共涉及3个步骤：

1、遍历nums，用一个map存储键为元素，值为对应元素出现的次数

2、对次数进行排序

3、返回top_k

Python代码如下：

1
2
3
4
5
6
7
8
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = {}
        for i in range(len(nums)):
            map[nums[i]] = map.get(nums[i], 0 ) + 1
        sort_map = sorted(map.items(), key = lambda x:x[1], reverse=True)
        top_k = [item[0] for item in sort_map[0:k]]
        return top_k

学完树再来用堆的思想来做