堆栈队列

# 练习题

# 1. 用队列实现栈 (opens new window)

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。 int pop() 移除并返回栈顶元素。 int top() 返回栈顶元素。 boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

class MyStack:

  def __init__(self):
      self.queue1 = collections.deque()
      self.queue2 = collections.deque()

  def push(self, x: int) -> None:
      # 后入先出，要将后入的元素放置在头部
      # 对应处的时候要从头部先出
      self.queue2.append(x)
      while self.queue1:
          self.queue2.append(self.queue1.popleft())
      self.queue1, self.queue2 = self.queue2, self.queue1

  def pop(self) -> int:
      return self.queue1.popleft()

  def top(self) -> int:
      return self.queue1[0]

  def empty(self) -> bool:
      return True if len(self.queue1) ==0 else False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Make sure to add code blocks to your code group

# 2. 数据流中的移动平均值 (opens new window)

给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算其所有整数的移动平均值。

实现 MovingAverage 类：

MovingAverage(int size) 用窗口大小 size 初始化对象。 double next(int val) 计算并返回数据流中最后 size 个值的移动平均值。

class MovingAverage:

  def __init__(self, size: int):
      self.size = size
      self.queue = collections.deque()
      self.total = 0
  def next(self, val: int) -> float:
      if len(self.queue) >=self.size:
          self.queue.popleft()
      self.queue.append(val)
      return sum(self.queue) / len(self.queue)

1
2
3
4
5
6
7
8
9
10
11
12

// Make sure to add code blocks to your code group

# 3. 锯齿迭代器 (opens new window)

给出两个一维的向量，请你实现一个迭代器，交替返回它们中间的元素。

示例:

输入: v1 = [1,2] v2 = [3,4,5,6]

输出: [1,3,2,4,5,6]

解析: 通过连续调用 next 函数直到 hasNext 函数返回 false， next 函数返回值的次序应依次为: [1,3,2,4,5,6]。

class ZigzagIterator:
  """
  通过tag标记下次是取数据的队列
  """
  def __init__(self, v1: List[int], v2: List[int]):
      self.queue1 = v1[::-1]
      self.queue2 = v2[::-1]
      self.tag = 1 if self.queue1 else 2

  def next(self) -> int:
      if self.queue1 and self.tag == 1:
          
          if self.queue2:
              self.tag = 2
          return self.queue1.pop()

      if self.queue2 and self.tag == 2:
          if self.queue1:
              self.tag = 1
          return self.queue2.pop()
          
  def hasNext(self) -> bool:
      return True if self.queue1 or self.queue2 else False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Make sure to add code blocks to your code group

# 4.螺旋矩阵 (opens new window)

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

class Solution:
  def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
      if not matrix:
          return []
      m = len(matrix)
      n = len(matrix[0])
      result = list()
      left, right, top, bottom = 0, n-1, 0, m-1
      while left <= right and top <= bottom:
          for col in range(left, right+1):
              result.append(matrix[top][col])

          for row in range(top+1, bottom+1):
              result.append(matrix[row][right])

          if left < right and top < bottom:
              for col in range(right-1, left, -1):
                  result.append(matrix[bottom][col])
              for row in range(bottom, top, -1):
                  result.append(matrix[row][left])
          left += 1
          right -= 1
          top += 1
          bottom -= 1
      return result

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

// Make sure to add code blocks to your code group

# 5. 敲击计数器 (opens new window)

设计一个敲击计数器，使它可以统计在过去 5 分钟内被敲击次数。（即过去 300 秒）

您的系统应该接受一个时间戳参数 timestamp (单位为秒 )，并且您可以假定对系统的调用是按时间顺序进行的(即 timestamp 是单调递增的)。几次撞击可能同时发生。

class HitCounter:
  """
  相当于一个固定大小的窗口，再窗口内找到合适数据
  """

  def __init__(self):
      self.queue1 = collections.deque()
      self.queue2 = collections.deque()

  def hit(self, timestamp: int) -> None:
      self.queue1.append(timestamp)
      while self.queue1 and timestamp - self.queue1[0]>=300:
          self.queue1.popleft()


  def getHits(self, timestamp: int) -> int:
      while self.queue1 and timestamp - self.queue1[0]>=300:
          self.queue1.popleft()      
      return len(self.queue1)


# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)

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

// Make sure to add code blocks to your code group

# 6.最小栈 (opens new window)

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

class MinStack:

  def __init__(self):
      self.min = list()
      self.stack = list()

  def push(self, val: int) -> None:
      #self.min = val if not self.min  else min(self.min, val)
      if not self.min:
          self.min.append(val)
      else:
          if self.min[-1] >= val:
              self.min.append(val)
      self.stack.append(val)

  def pop(self) -> None:
      num = self.stack.pop()
      if self.min and self.min[-1] == num:
          self.min.pop()
      return num

  def top(self) -> int:
      return self.stack[-1]

  def getMin(self) -> int:
      return self.min[-1]


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

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

// Make sure to add code blocks to your code group

# 7.用栈实现队列 (opens new window)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空，返回 true ；否则，返回 false 说明：

你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

class MyQueue:

  def __init__(self):
      self.stack1 = []
      self.stack2 = []

  def push(self, x: int) -> None:
      self.stack1.append(x)
  def pop(self) -> int:
      if self.stack2:
          return self.stack2.pop()
      else:
          while self.stack1:
              self.stack2.append(self.stack1.pop())
          return self.stack2.pop()
  def peek(self) -> int:
      if self.stack2:
          return self.stack2[-1]
      else:
          while self.stack1:
              self.stack2.append(self.stack1.pop())
          return self.stack2[-1]
  def empty(self) -> bool:
      return  False if (self.stack1 or self.stack2) else True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// Make sure to add code blocks to your code group

# 8. 逆波兰表达式求值 (opens new window)

根据逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

class Solution:
  def evalRPN(self, tokens: List[str]) -> int:
      stack = list()

      set1 = {"/", "+", "-","*"}
      for chr in tokens:
          if chr not in set1:
              stack.append(int(chr))
          else:
              num1 = stack.pop()
              num2 = stack.pop()
              if chr == "/":
                  temp = int(num2 /  num1)
              elif chr == "*":
                  temp = num1 * num2
              elif chr == "+":
                  temp =num1 + num2
              else:
                  
                  temp = num2 - num1
              stack.append(temp)
      return stack[-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

// Make sure to add code blocks to your code group

# 9. 有效的括号 (opens new window)

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

class Solution:
  def isValid(self, s: str) -> bool:
      stack = list()
      dict1 = {")": "(", "}": "{",  "]": "["}

      for ss in s:
          if ss in dict1:
              if stack and stack[-1] == dict1.get(ss):
                  stack.pop()
              else:
                  return False
          else:
              stack.append(ss)
      
      return True if not stack else False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// Make sure to add code blocks to your code group

# 10. 设计浏览器历史记录 (opens new window)

你有一个只支持单个标签页的浏览器，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。 void visit(string url) 从当前页跳转访问 url 对应的页面。执行此操作会把浏览历史前进的记录全部删除。 string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退至多 steps 步以后的 url 。 string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进至多 steps步以后的 url 。

class BrowserHistory:

  def __init__(self, homepage: str):
      self.stack = [homepage]
      self.pos = 0

  def visit(self, url: str) -> None:
      
      self.stack = self.stack[:self.pos+1]
      self.stack.append(url)
      self.pos = len(self.stack) -1
      return url
      
  def back(self, steps: int) -> str:

      if steps >= self.pos:
          self.pos = 0
          return self.stack[self.pos]      
      else:
          self.pos = self.pos-steps

          return self.stack[self.pos]


  def forward(self, steps: int) -> str:

      if len(self.stack) - (self.pos+1) < steps:
          self.pos = len(self.stack)-1
          return self.stack[-1]
      else:
          self.pos = self.pos + steps
          return self.stack[self.pos]

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

// Make sure to add code blocks to your code group

# 11. 行星碰撞 (opens new window)

给定一个整数数组 asteroids，表示在同一行的行星。

对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。

找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。

class Solution:
  def asteroidCollision(self, asteroids: List[int]) -> List[int]:
      stack = [asteroids[0]]
      asteroids = asteroids[1:]

      for i in range(len(asteroids)):
          need_insert= True
          while stack:
              # print(stack[-1], asteroids[i])
              if (stack[-1] >0 and asteroids[i]) >0 or (stack[-1] <0 and asteroids[i] <0):
                  stack.append(asteroids[i])
                  need_insert = False
                  break
              # 下面为不通向的逻辑

              # 前数向左，后数向右
              elif stack[-1] <0 and asteroids[i] > 0:
                  need_insert = False
                  stack.append(asteroids[i])
                  break
              # 相撞， 后大于前
              elif abs(stack[-1]) < abs(asteroids[i]):
                  # 插入后需要判断和原有的stack中的大小
                  stack.pop()
              elif abs(stack[-1]) == abs(asteroids[i]):
                  stack.pop()
                  need_insert = False
                  break
              else:
                  need_insert = False
                  break
          if not stack and need_insert:
              stack.append(asteroids[i])
      return stack

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
35

// Make sure to add code blocks to your code group

# 12.删除字符串中的所有相邻重复项 II (opens new window)

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一

class Solution:
  def removeDuplicates(self, s: str, k: int) -> str:


      # 方法一：会超时
      # result = list()
      # for ss in s:
      #     # 不足k-1个直接加入
      #     if len(result) < k-1:
      #         result.append(ss)
      #     else:
      #         # 检测后k-1各元素是否相同并且同为ss
      #         is_valid = False
      #         result.append(ss)
      #         for i in range(-1, -k-1, -1):
      #             if result[i] != ss:
      #                 is_valid = True
      #                 break
      #         if not is_valid:
      #             result = result[:len(result)-k]
      # return "".join(result)

      # 方法二 利用栈
      stack = list()
      for ss in s:
          if stack:
              if ss == stack[-1][0] and stack[-1][1]+1 < k:
                  stack[-1][1] += 1
              elif ss == stack[-1][0] and stack[-1][1]+1 >=k:
                  stack.pop()

              else:
                  stack.append([ss, 1])
          else:
              stack.append([ss, 1])
      result = list()
      for chr, num in stack:
          result.append(chr*num)
      return "".join(result)

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
35
36
37
38
39

// Make sure to add code blocks to your code group

# 13.移除无效的括号 (opens new window)

给你一个由 '('、')' 和小写字母组成的字符串 s。

你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。

请返回任意一个合法字符串。

有效「括号字符串」应当符合以下任意一条要求：

空字符串或只包含小写字母的字符串可以被写作 AB（A 连接 B）的字符串，其中 A 和 B 都是有效「括号字符串」可以被写作 (A) 的字符串，其中 A 是一个有效的「括号字符串」

class Solution:
  def minRemoveToMakeValid(self, s: str) -> str:
      stack1 = list()
      s= list(s)
      for i in range(len(s)):
          if s[i] == "(":
              stack1.append(i)
          elif s[i] == ")":
              if stack1:
                  stack1.pop()
              else:
                  s[i] = "0"
          else:
              pass
      while stack1:
          s[stack1.pop()]="0"
      s = "".join(s)
      s= s.replace("0", "")
      return s

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

// Make sure to add code blocks to your code group

编辑

上次更新: 2024/12/31 14:23:38

← 基本认知基本认知→