leetcodede_队列

发表于 | 分类于 | 页面访问量 次
字数统计: 2.4k 字 | 阅读时长 ≈ 11 分钟
  • 菜 933（B+）
  • 中 621（A-） 、622（C+） 、641（C+）
  • 危 862（A+）

个人总结：队列的题普遍综合性，理解题意就需要花费一定时间。队列是先进先出。有几道都是自定义构造类，实现功能。还是比较锻炼代码基础的。逻辑性还是不好，代码构建时有一些心浮气躁。需要沉下心，慢慢努力。

额外扩展：collections模块的Counter类

933. 最近的请求次数（B）

分析：蛤？看题看了三遍，也没读懂要求到底是什么。不是出题人表达能力欠佳，要不就是我理解欠佳。暂且归于后者吧。看了评论知道了题意。如下：

1
2
3
4
5
6
7
8
9
/*法1：其实这题很简单的，用队列的enqueue和dequeue做很简洁（队列用C语言做要啰嗦点）*/
/*比如输入是["RecentCounter","ping","ping","ping","ping"]
           [[],[1],[100],[3001],[3002]]
第一组是(RecentCounter, [])这个意思我觉得是创立一个RecentCounter型的指针并返回，就如这个函数RecentCounter* recentCounterCreate() 
第二组是(ping, [1])调用了ping函数，就是这个int recentCounterPing(RecentCounter* obj, int t) ，1时刻和它之前的1-3000时刻之内都应记录好，其实应该是从0开始递增下去的吧，1-3000到1内的负数不用考虑，所以返回值是1；
第三组是(ping, [100])，(100 - 3000, 100)这个范围之内的值都应记录起来，就是要包括第二组的
(ping, [1])，所以返回值是2；
第四组是(ping, [3001])，(3001 - 3000, 3001)这个范围之内，也就是包括了第二组的(ping, [1])和第三组的(ping, [100])，返回值是3；
第五组是(ping, [3002])，(3002 - 3000, 3002)这个范围之内，也就是包括了第三组的(ping, [100])和第四组的(ping, [3001])，第二组的(ping, [1])不在范围内，舍掉，此时返回值是3；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class RecentCounter:

    def __init__(self):
        self.pinglist=[]
        self.minindex=0

    def ping(self, t: int) -> int:
        self.pinglist.append(t)
        while t > self.pinglist[self.minindex] + 3000:
            self.minindex += 1
        return len(self.pinglist) - self.minindex


# Your RecentCounter object will be instantiated and called as such:
# obj = RecentCounter()
# param_1 = obj.ping(t)

621. 任务调度器（A-）

分析：CPU调度，一开始就被这标题吓唬住了。了解题意后，也没有什么好的想法。看答案，基本都是一个路子。找到一个计算公式。 (count[25] - 1) * (n + 1) + maxCount

公式详解：

  • 假设数组 [“A”,”A”,”A”,”B”,”B”,”C”]，n = 2，A的频率最高，记为count = 3，所以两个A之间必须间隔2个任务，才能满足题意并且是最短时间（两个A的间隔大于2的总时间必然不是最短），因此执行顺序为： A->X->X->A->X->X->A，这里的X表示除了A以外其他字母，或者是待命，不用关心具体是什么，反正用来填充两个A的间隔的。上面执行顺序的规律是： 有count - 1个A，其中每个A需要搭配n个X，再加上最后一个A，所以总时间为 (count - 1) * (n + 1) + 1
  • 要注意可能会出现多个频率相同且都是最高的任务，比如 [“A”,”A”,”A”,”B”,”B”,”B”,”C”,”C”]，所以最后会剩下一个A和一个B，因此最后要加上频率最高的不同任务的个数 maxCount
  • 公式算出的值可能会比数组的长度小，如[“A”,”A”,”B”,”B”]，n = 0，此时要取数组的长度
1
2
3
4
5
6
7
8
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        count = collections.Counter(tasks)
        most = count.most_common()[0][1]
        #most_common()返回一个TopN列表。如果n没有被指定，则返回所有元素。当多个元素计数值相同时，排列是无确定顺序的。
        num_most = len([i for i, v in count.items() if v == most])
        time = (most - 1) * (n + 1) + num_most
        return max(time, len(tasks))

扩展：collections模块的Counter类

Counter类的目的是用来跟踪值出现的次数。它是一个无序的容器类型，以字典的键值对形式存储，其中元素作为key，其计数作为value。计数值可以是任意的Interger（包括0和负数）。Counter类和其他语言的bags或multisets很相似。

参考：http://www.pythoner.com/205.html

第二种方法，基本上区别不大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        output = [0]*26
        for i in tasks:
            output[ord(i)-ord('A')] = output[ord(i)-ord('A')]+1   #返回ASCII值
 
        count = 0
        len_o = 0
        max_o = max(output)
        for i in output:
            if i==max_o:
                count = count+1
                    
        return max(len(tasks),(max_o-1)*(n+1)+count)

ord() 函数是 chr() 函数（对于8位的ASCII字符串）或 unichr() 函数（对于Unicode对象）的配对函数，它以一个字符（长度为1的字符串）作为参数，返回对应的 ASCII 数值，或者 Unicode 数值，如果所给的 Unicode 字符超出了你的 Python 定义范围，则会引发一个 TypeError 的异常。

622. 设计循环队列（C）

分析：构建类，设计循环队列。很好理解，也算是第一次见这种题型。构建循环队列可以使用数组或者是链表。

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

循环队列关键点在于avail = (self._front + self._size ) % len(self._data)第一个数位置变动，如果大于循环数组长度，就可以在队列前面添加元素。其他“%”皆是如此。

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
40
class MyCircularQueue(object):

    def __init__(self, k):      
        self._data = [None] * k   # 数据
        self._size = 0            # 目前储存的个数
        self._front = 0           # 第一个数的位置

    def enQueue(self, value):
        if self.isFull():
            return False 
        avail = (self._front + self._size ) % len(self._data)  # （第一个数的位置 + 目前储存的个数） % 循环数组长度
        self._data[avail] = value
        self._size += 1
        return True
        
    def deQueue(self):       
        if self.isEmpty()：
            return False
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data) # （第一个数的位置 + 1） % 循环数组长度
        self._size -= 1
        return True

        
    def Front(self):       
        if self.isEmpty():
            return -1
        return self._data[self._front]

    def Rear(self):      
        if self.isEmpty():
            return -1
        return self._data[(self._front + self._size - 1) % len(self._data)]  # （第一个数的位置 + 目前储存的个数 - 1 ） % 循环数组长度

    def isEmpty(self):       
        return self._size == 0

    def isFull(self):      
        return self._size == len(self._data)

641. 设计循环双端队列（C）

分析：跟前一题基本类似。加了一个双端要求。题中要求不可以使用内置的双端队列。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class MyCircularDeque:

    def __init__(self, k):
        """
        Initialize your data structure here. Set the size of the deque to be k.
        :type k: int
        """
        self.queue = []
        self.size = k

    def insertFront(self, value):
        """
        Adds an item at the front of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.insert(0,value)
            return True
        else:
            return False

    def insertLast(self, value):
        """
        Adds an item at the rear of Deque. Return true if the operation is successful.
        :type value: int
        :rtype: bool
        """
        if not self.isFull():
            self.queue.append(value)
            return True
        else:
            return False

    def deleteFront(self):
        """
        Deletes an item from the front of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop(0)
            return True
        else:
            return False

    def deleteLast(self):
        """
        Deletes an item from the rear of Deque. Return true if the operation is successful.
        :rtype: bool
        """
        if not self.isEmpty():
            self.queue.pop()
            return True
        else:
            return False

    def getFront(self):
        """
        Get the front item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[0]

    def getRear(self):
        """
        Get the last item from the deque.
        :rtype: int
        """
        if self.isEmpty():
            return -1
        else:
            return self.queue[-1]

    def isEmpty(self):
        """
        Checks whether the circular deque is empty or not.
        :rtype: bool
        """
        return len(self.queue) == 0

    def isFull(self):
        """
        Checks whether the circular deque is full or not.
        :rtype: bool
        """
        return len(self.queue) == self.size

第二种。是同622一样的做法。

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class MyCircularDeque:
    def __init__(self, k: 'int'):
        self.a = [None] * k # internal buffer
        self.k = k # capacity - max number of elements that deque can hold
        self.sz = 0 # current size
        self.b = k - 1 # points to current 'back' element
        self.f = 0 # points to current 'front' element        
        
    def prev_idx(self, i): 
        if i == 0: return self.k - 1
        else: return i - 1
        
    def next_idx(self, i): 
        return (i + 1) % self.k

    def insertFront(self, v: 'int') -> 'bool':
        if self.sz == self.k: return False
        
        self.f = self.prev_idx(self.f)
        self.a[self.f] = v
        self.sz += 1
        
        return True
        

    def insertLast(self, v: 'int') -> 'bool':
        if self.sz == self.k: return False
        
        self.b = self.next_idx(self.b)
        self.a[self.b] = v
        self.sz += 1
        
        return True

    def deleteFront(self) -> 'bool':
        if self.sz == 0: return False
        
        self.f = self.next_idx(self.f)
        self.sz -= 1
        
        return True

    def deleteLast(self) -> 'bool':
        if self.sz == 0: return False
        
        self.b = self.prev_idx(self.b)
        self.sz -= 1
        
        return True

    def getFront(self) -> 'int':
        if self.sz == 0: return -1
        
        return self.a[self.f]

    def getRear(self) -> 'int':
        if self.sz == 0: return -1
        
        return self.a[self.b]


    def isEmpty(self) -> 'bol': 
        return self.sz == 0        


    def isFull(self) -> 'bool':
        return self.sz == self.k

862. 和至少为 K 的最短子数组（A+）

分析：结合了队列和动态规划。由于题中给了 （1 <= K）所以，必须要保证，dp 后一个值减去前一个值，而且是必须大于0才是有效的。从双端队列左侧出队，来寻求最短的字数组是精华所在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import collections
class Solution:
    def shortestSubarray(self, A: List[int], K: int) -> int:        
 
        n, dp = len(A), [0]  # 初始化dp[i] = A[0]+A[1]+...+A[i-1]
        for v in A: 
            dp.append(dp[-1] + v)
 
        queue, res = collections.deque(), n + 1  # 初始化双端队列、结果变量
        for i in range(n+1):
            while queue and dp[i] <= dp[queue[-1]]: #因为K >= 1
                queue.pop()  # 出队, 删除不符合的
 
            while queue and dp[i] - dp[queue[0]] >= K:  #满足题意。
                res = min(res, i - queue.popleft())  # 从双端队列左边出队，并更新最短距离。
 
            queue.append(i)  # 入队
 
        return res if res < n + 1 else -1  #返回最优解，限制不可能超过列表元素。

if __name__ == '__main__':
    solu = Solution()
    A, K = [2, -1, 2], 3
    print(solu.shortestSubarray(A, K))
0%
undefined