Loading...
墨滴

algolearn

2021/09/29  阅读:21  主题:默认主题

总结:栈与队列leecode几例

1 用栈实现队列

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

实现 MyQueue 类:

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空,返回 true ;否则,返回 false
class MyQueue(object):

    def __init__(self):
        self.stack = []
        self.back_stack = []


    def push(self, x):
        """
        :type x: int
        :rtype: None
        "
""
        self.stack.append(x)


    def pop(self):
        """
        :rtype: int
        "
""
        if not self.stack:
            return
        for i in range(len(self.stack)):
            self.back_stack.append(self.stack.pop())
        out = self.back_stack.pop(-1)
        for i in range(len(self.back_stack)):
            self.stack.append(self.back_stack.pop())
        return out


    def peek(self):
        """
        :rtype: int
        "
""
        if not self.stack:
            return
        for i in range(len(self.stack)):
            self.back_stack.append(self.stack.pop())
        out = self.back_stack[-1]
        for i in range(len(self.back_stack)):
            self.stack.append(self.back_stack.pop())
        return out


    def empty(self):
        """
        :rtype: bool
        "
""
        return len(self.stack ) == 0



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

2 用队列实现栈

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

实现 MyStack 类:

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
class MyStack(object):

    def __init__(self):
        self.queue = collections.deque()
        self.back_queue = collections.deque()


    def push(self, x):
        """
        :type x: int
        :rtype: None
        "
""
        self.back_queue.append(x)
        while self.queue:
            self.back_queue.append(self.queue.popleft())
        self.queue, self.back_queue = self.back_queue, self.queue

    def pop(self):
        """
        :rtype: int
        "
""
        if not self.queue:
            return
        return self.queue.popleft()


    def top(self):
        """
        :rtype: int
        "
""
        if not self.queue:
            return 
        return self.queue[0]


    def empty(self):
        """
        :rtype: 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()

3 字符串解码 (stack)

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        "
""
        stack = []
        i = 0
        while i < len(s):
            # 1. 如果第一个字符是数字,那么就取一整个数字
            if s[i] in "0123456789":
                num = ''
                while s[i] in "0123456789":
                    num += s[i]
                    i += 1
                stack.append(int(num))
            # 2. 如果不是右括号,可能是 [ 或者 字母 直接加进去
            if s[i] != ']':
                stack.append(s[i])
                i += 1
            # 3. 如果为右括号,计算当前结果
            elif s[i] == ']':
                rst = ''
                # 取字符串
                while stack[-1] != '[':
                    rst = stack.pop() + rst
                # 取数字,并且计算结果字符串
                stack.pop()
                num = stack.pop()

                # 计算结果字符串,添加到结果集,并再次进栈
                rst = rst * num
                stack.append(rst)
                i += 1

        #print(stack)
        return ''.join(stack)

4 图像渲染

有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一个新的颜色值 newColor,让你重新上色这幅图像。

为了完成上色工作,从初始坐标开始,记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点,接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点,……,重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

# BFS
class Solution(object):
    def floodFill(self, image, sr, sc, newColor):
        queue = [[sr, sc]]
        visted = {}
        row, col = len(image), len(image[0])
        color = image[sr][sc]
        image[sr][sc] = newColor
        while queue:
            d_row, d_col = queue.pop(0)
            for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                n_x = d_row + x
                n_y = d_col + y
                if 0 <= n_x < row and 0 <= n_y < col and image[n_x][n_y] == color and (n_x, n_y) not in visted:
                    queue.append([n_x, n_y])
                    image[n_x][n_y] = newColor
                    visted[(n_x, n_y)] = True
        return image
        
        
# DFS
class Solution:
    def floodFill(self, image, sr, sc, newColor):
        color = image[sr][sc]
        visted = {}
        row, col = len(image), len(image[0])
        def dfs(x, y):
            if image[x][y] == color:
                image[x][y] = newColor
                for dx, dy in [(0, 1), (0, -1), (-1, 0),(1, 0)]:
                    nx = x + dx
                    ny = y + dy
                    if 0 <= nx < row and 0 <= ny < col and image[nx][ny] == color and (nx, ny) not in visted:
                        visted[(nx, ny)] = True
                        dfs(nx, ny)
        if color != newColor:
            dfs(sr, sc)
            visted[(sr, sc)] = True
        return image

5 01 矩阵

给定一个由 0 和 1 组成的矩阵 mat ,请输出一个大小相同的矩阵,其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

class Solution:
    from collections import deque
    def updateMatrix(self, matrix):
        queue = deque()
        m, n = len(matrix), len(matrix[0])
        visited = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    queue.append((i,j))
                    visited[i][j] = 1
        while queue:
            i, j = queue.popleft()
            for ni, nj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= ni < m and 0 <= nj < n and visited[ni][nj] != 1:
                    matrix[ni][nj] = matrix[i][j] + 1
                    queue.append((ni, nj))
                    visited[ni][nj] = 1
        return matrix

6 钥匙和房间

有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j] 由 [0,1,...,N-1] 中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false。

# BFS 
class Solution:
    def canVisitAllRooms(self, rooms):
        visited, queue = {0}, [0]
        while queue:
            room_index = queue.pop(0)
            for key in rooms[room_index]:
                if key not in visited:
                    visited.add(key)
                    queue.append(key)
        return len(visited) == len(rooms)
        
# DFS
class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        visited, stack = {0}, [0]
        while stack:
            room_index = stack.pop()
            for key in rooms[room_index]:
                if key not in visited: 
                    visited.add(key)
                    stack.append(key)
        return len(visited) == len(rooms)

欢迎关注微信公众号(算法工程师面试那些事儿),建号初期,期待和大家一起刷leecode,刷机器学习、深度学习面试题等,共勉~

算法工程师面试那些事儿
算法工程师面试那些事儿

algolearn

2021/09/29  阅读:21  主题:默认主题

作者介绍

algolearn