Loading...
墨滴

algolearn

2021/09/22  阅读:28  主题:默认主题

存储结构 - 队列 queue

1 概述

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列:先入先出

2 实现

如下图所示,队列是典型的 FIFO 数据结构。插入(insert)操作也称作入队(enqueue),新元素始终被添加在队列的末尾。 删除(delete)操作也被称为出队(dequeue)。 你只能移除第一个元素。

class Queue():
    def __init__(self):
        self.__list = []
    def enqueue(self, item):
        '''入队'''
        self.__list.append(item)
    def dequeue(self):
        '''出队'''
        if self.__list:
            return self.__list.pop(0)
        else:
            return None
    def is_empty(self):
        '''是否为空'''
        return self.__list == []
    def size(self):
        '''队列长度'''
        return len(self.__list)

上面的实现很简单,但在某些情况下效率很低。 随着起始指针的移动,浪费了越来越多的空间。 当我们有空间限制时,这将是难以接受的。

让我们考虑一种情况,即我们只能分配一个最大长度为 5 的数组。当我们只添加少于 5 个元素时,我们的解决方案很有效。 例如,如果我们只调用入队函数四次后还想要将元素 10 入队,那么我们可以成功。

但是我们不能接受更多的入队请求,这是合理的,因为现在队列已经满了。但是如果我们将一个元素出队呢?

实际上,在这种情况下,我们应该能够再接受一个元素。

3 循环队列

更有效的方法是使用循环队列。 具体来说,我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置。 目的是重用我们之前提到的被浪费的存储。

思路

入队:尾指针加一,空队列为特殊状态,需将头指针加一。 出队:头指针加一,队列只剩一个元素(头尾指针相等)为特殊状态,需将头尾指针设为 -1 isFull:尾指针与头指针的距离为 0

class MyCircularQueue:
    def __init__(self, k):
        self.size = k
        self.queue = [None] * self.size
        self.head = -1
        self.tail = -1

    def enQueue(self, value):
        if self.isFull():
            return False
        if self.isEmpty():
            self.head = 0
        self.tail = (self.tail + 1) % self.size
        self.queue[self.tail] = value
        return True

    def deQueue(self):
        if self.isEmpty():
            return False
        if self.head == self.tail:
            self.head = -1
            self.tail = -1
            return True
        self.head = (self.head + 1) % self.size
        return True

    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[self.head]

    def Rear(self):
        if self.isEmpty():
            return -1
        return self.queue[self.tail]

    def isEmpty(self):
        return self.head == -1

    def isFull(self):
        return (self.tail + 1) % self.size == self.head

# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

4 队列与广度优先搜索

# %%
# 模板1,不带hash表,每个节点可以访问多次,遍历树没有问题,遍历图就会陷入循环
def BFS1(root, target):
    # 记录遍历的层次
    step = 0
    # 这一层的节点列表,注意第一层要将根节点放进去
    this_layer = [root]
    # 当这一层的节点列表不为空,就要一直遍历
    while this_layer != []:
        # 下一层的节点列表
        next_layer = []
        # 遍历这一层的节点
        for node in this_layer:
            if node.value == target:
                return step  # 找到了就返回
            # 同时要把每个节点的下一个节点加入到下一层节点列表
            next_layer.append(node.next)
        # 遍历完这一层的节点,step就加一
        step += 1
        this_layer = next_layer


# %%
# 模板2,带hash表,保证每个节点只访问一次,遍历图没有问题
def BFS2(root, target):
    # 只需要在BFS1的基础上将遍历过的节点加入hash表就好了
    hash_table = set()
    # 记录遍历的层次
    step = 0
    # 这一层的节点列表,注意第一层要将根节点放进去
    this_layer = [root]
    # 当这一层的节点列表不为空,就要一直遍历
    while this_layer != []:
        # 下一层的节点列表
        next_layer = []
        # 遍历这一层的节点
        for node in this_layer:
            # 没遍历过才需要遍历
            if node not in hash_table:
                if node.value == target:
                    return step  # 找到了就返回
                # 被遍历了就加入hash_table
                hash_table.add(node)
            # 同时要把每个节点的下一个节点加入到下一层节点列表
            next_layer.append(node.next)
        # 遍历完这一层的节点,step就加一
        step += 1
        this_layer = next_layer

5 练习

5.1 数据流中的移动平均值

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

class MovingAverage:
 
    def __init__(self, size: int):
        """
        Initialize your data structure here.
        """

        from collections import deque
        self.queue = deque(maxlen=size)
 
 
    def next(self, val: int) -> float:
        self.queue.appendleft(val)
        return sum(self.queue)/ len(self.queue)

5.2 墙与门 286

你被给定一个 m × n 的二维网格,网格中有以下三种可能的初始化值:

-1 表示墙或是障碍物;0 表示一扇门;INF 无限表示一个空的房间。然后,我们用 代表 INF。你可以认为通往门的距离总是小于 2147483647 的。 你要给每个空房间位上填上该房间到 最近 门的距离,如果无法到达门,则填 INF 即可。

from collections import deque

class Solution:
    def wallsAndGates(self, rooms):
        if not rooms:
            return
        row = len(rooms)
        col = len(rooms[0])
        empty = 2 ** 31 - 1
        door = 0
        wall = -1
        neighbors = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        search_list = deque()
        # 将门作为根节点,开始遍历
        for i in range(row):
            for j in range(col):
                if rooms[i][j] == door:
                    search_list.append([i, j])
        while search_list:
            d_row, d_col = search_list.popleft()
            distance = rooms[d_row][d_col] + 1
            for x, y in neighbors:
                neighbor_row = d_row + x
                neighbor_col = d_col + y
                # 给遇到的所有空房间都标上距离,BFS保证第一次标上的距离一定是最短距离
                if 0 <= neighbor_row < row and 0 <= neighbor_col < col and rooms[neighbor_row][neighbor_col] == empty:
                    rooms[neighbor_row][neighbor_col] = distance
                    search_list.append([neighbor_row, neighbor_col])

5.3 岛屿数量 200

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

from collections import deque

class Solution:
    def numIslands(self, grid):
        """
        思路:1. 遍历网络,如果为1,则加入队列进行BFS; 
             2. 并将遍历过的位置置为0
        """

        if not grid:
            return 0
        row = len(grid)
        col = len(grid[0])
        neighbors = [(-10), (10), (0-1), (01)]
        search_list = deque()
        num_islands = 0
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1':
                    search_list.append([i, j])
                    num_islands += 1
                    grid[i][j] = '0'
                    while search_list:
                        d_row, d_col = search_list.popleft()
                        for x, y in neighbors:
                            neighbor_row = d_row + x
                            neighbor_col = d_col + y
                            if 0 <= neighbor_row < row and 0 <= neighbor_col < col and grid[neighbor_row][neighbor_col] == '1':
                                grid[neighbor_row][neighbor_col] = '0'
                                search_list.append([neighbor_row, neighbor_col])
        return num_islands

5.4 打开转盘锁 752

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

from collections import deque

class Solution(object):
    def openLock(self, deadends, target):
        deadends = set(deadends)
        if "0000" in deadends: # 如果连起点都不能走就88
            return -1
        queue = deque()
        queue.append(["0000"0])
        while queue:
            node, cnt = queue.popleft() # 取一个点出来,cnt是当前走的步数
            if node == target: # 找到了
                return cnt     
            for i in range(4):
                for j in [1-1]:
                    next_node = node[:i] + str((int(node[i]) + j) % 10) + node[i + 1:] 
                    if next_node not in deadends: # 新的点可以走而且没走过
                        deadends.add(next_node) # 避免重复
                        queue.append([next_node, cnt + 1])
        return -1

5.5 完全平方数 279

给定正整数 n,找到若干个完全平方数(比如 1, 4, 9, 16, ...)使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ,返回和为 n 的完全平方数的 最少数量 。

from collections import deque
import math

class Solution:
    def numSquares(self, n):
        queue = deque()
        queue.append(n)
        cnt = 0
        while queue:
            for i in range(len(queue)):
                tmp_n = queue.popleft()
                if tmp_n == 0:
                    return cnt
                sqrt_tmp = math.sqrt(tmp_n)
                if int(sqrt_tmp) == sqrt_tmp:
                    return cnt + 1
                for i in range(int(sqrt_tmp), 0-1):
                    queue.append(tmp_n - i * i)
            cnt += 1

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

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

algolearn

2021/09/22  阅读:28  主题:默认主题

作者介绍

algolearn