本文共 6022 字，大约阅读时间需要 20 分钟。

优化后的内容

LeetCode 225: 用队列实现栈

问题描述

栈是先进后出的数据结构，而队列是先进先出的。我们需要使用队列来实现栈的常见操作：push、pop、top和empty。以下是具体的操作定义：

• push(x): 将元素x推入栈顶。
• pop(): 移除栈顶元素。
• top(): 获取栈顶元素。
• empty(): 检查栈是否为空。

解决思路

为了实现栈的功能，我们可以利用两个队列来模拟栈的行为。具体来说，我们可以将一个队列用作入栈栈，另一个队列用作出栈栈。通过适当的逻辑操作，可以模拟栈的先进后出特性。

解决代码

class MyStack:    def __init__(self):        self.q1 = collections.deque()        self.q2 = collections.deque()        def push(self, x):        if self.q1.empty():            self.q2.append(x)        else:            self.q1.append(x)        def pop(self):        if self.q1.empty():            if not self.q2.empty():                while len(self.q2) > 1:                    self.q1.append(self.q2.popleft())                return self.q2.popleft()        else:            while not self.q2.empty() or not self.q1.empty():                if self.q1.empty():                    self.q2.append(self.q1.popleft())                else:                    return self.q1.popleft()        def top(self):        if self.q1.empty():            if self.q2.empty():                return 0            else:                return self.q2[-1]        else:            return self.q1[-1]        def empty(self):        return self.q1.empty() and self.q2.empty()

解释

• push(x): 判断入栈队列q1是否为空。如果为空，则将x推入出栈队列q2中；否则，将x推入入栈队列q1中。
• pop(): 如果入栈队列q1为空，说明所有元素都已经被移到q2中，取出q2的最后一个元素。否则，取出q1的最后一个元素。
• top(): 返回栈顶元素。如果q1为空，返回q2的最后一个元素；否则，返回q1的最后一个元素。
• empty(): 检查q1和q2是否都为空。如果都为空，返回True，否则返回False。

通过这种方法，我们可以使用队列来实现栈的基本操作，保持了先进后出的特性。

LeetCode 232: 用栈实现队列

问题描述

队列是先进先出的数据结构，而栈是先进后出的。我们需要使用栈来实现队列的常见操作：push、pop、peek和empty。以下是具体的操作定义：

• push(x): 将元素x推入队列的尾部。
• pop(): 从队列首部移除元素。
• peek(): 返回队列首部的元素。
• empty(): 检查队列是否为空。

解决思路

为了实现队列的功能，我们可以利用两个栈来模拟队列的行为。具体来说，我们可以将一个栈用作出队栈，另一个栈用作入队栈。通过适当的逻辑操作，可以模拟队列的先进先出特性。

解决代码

class MyQueue:    def __init__(self):        self.in_stack = collections.deque()        self.out_stack = collections.deque()        def push(self, x):        self.in_stack.append(x)        def pop(self):        if not self.out_stack:            while self.in_stack:                self.out_stack.append(self.in_stack.popleft())        return self.out_stack.popleft()        def peek(self):        if not self.out_stack:            while self.in_stack:                self.out_stack.append(self.in_stack.popleft())        return self.out_stack[0]        def empty(self):        return not self.in_stack and not self.out_stack

解释

• push(x): 将元素x推入入队栈in_stack中。
• pop(): 如果出队栈out_stack为空，取出入队栈in_stack中的所有元素，并将它们推入out_stack中，然后取出out_stack的第一个元素。
• peek(): 如果出队栈out_stack为空，取出入队栈in_stack中的所有元素，并将它们推入out_stack中，然后返回out_stack的第一个元素。
• empty(): 检查in_stack和out_stack是否都为空。如果都为空，返回True，否则返回False。

通过这种方法，我们可以使用栈来实现队列的基本操作，保持了先进先出的特性。

LeetCode 155: 最小栈

问题描述

我们需要设计一个支持push、pop、top和getMin操作的栈，且在常数时间内能够检索到栈中的最小元素。以下是具体的操作定义：

• push(x): 将元素x推入栈中。
• pop(): 删除栈顶的元素。
• top(): 获取栈顶元素。
• getMin(): 检索栈中的最小元素。

解决思路

为了实现这个栈，我们可以使用两个栈来存储元素。一个栈用于正常的栈操作，另一个栈用于存储当前栈中最小元素。每当push操作执行时，我们需要检查当前栈是否为空以及最小栈是否为空，以决定如何更新栈的状态。

解决代码

class MinStack:    def __init__(self):        self.normal = collections.deque()        self.min = collections.deque()        def push(self, x):        self.normal.append(x)        if not self.min:            self.min.append(x)        else:            if x < self.min[-1]:                self.min.append(x)            else:                self.min.append(self.min[-1])        def pop(self):        if self.normal:            self.normal.pop()            if self.min and self.min[-1] == self.normal.pop():                self.min.pop()        def top(self):        return self.normal[-1] if self.normal else 0        def getMin(self):        return self.min[-1] if self.min else 0

解释

• push(x): 将元素x推入normal栈中。如果min栈为空，则将x推入min栈中；否则，检查x是否小于min栈的栈顶元素。如果是，将x推入min栈中；否则，将min栈的栈顶元素推入min栈中。
• pop(): 如果normal栈不为空，移除栈顶元素。同时，如果该元素等于min栈的栈顶元素，则移除min栈的栈顶元素。
• top(): 返回normal栈的栈顶元素，如果normal栈为空，则返回0。
• getMin(): 返回min栈的栈顶元素，如果min栈为空，则返回0。

通过这种方法，我们可以在常数时间内检索到栈中的最小元素，同时支持栈的基本操作。

LeetCode 215: 找出第k大的元素

问题描述

在未排序的数组中找到第k大的元素。请注意，我们需要找的是数组排序后的第k大的元素，而不是第k个不同的元素。

解决思路

我们可以使用一个小顶堆来实现这个算法。小顶堆有一个特性是，堆顶是最小的元素。我们可以通过以下步骤来实现：

解决代码

import heapqclass Solution:    def findKthLargest(self, nums, k):        heap = []        for num in nums:            if len(heap) < k:                heapq.heappush(heap, num)            else:                if num > heap[0]:                    heapq.heappop(heap)                    heapq.heappush(heap, num)        return heap[0]

解释

• findKthLargest(nums, k): 初始化一个空的小顶堆heap。
• 遍历数组nums：对于每个元素num，判断堆的大小是否小于k。如果是，将num推入堆中。
• 如果堆的大小等于k：比较num和堆顶元素。如果num更大，则弹出堆顶元素，并将num推入堆中；否则，将num推入堆中。
• 返回结果：堆的顶部即为第k大的元素。

通过这种方法，我们可以在O(n log n)的时间复杂度内找到数组中的第k大的元素。

LeetCode 295: 找中位数

问题描述

中位数是有序列表中间的数。如果列表长度是偶数，中位数是中间两个数的平均值。我们需要设计一个数据结构，支持以下操作：

• addNum(int num): 添加一个整数到数据结构中。
• findMedian(): 返回当前所有元素的中位数。

解决思路

我们可以使用两个堆来实现这个数据结构：一个小顶堆和一个大顶堆。小顶堆用于存储较小的一半元素，大顶堆用于存储较大的一半元素。通过维护这两个堆的大小关系，可以实现中位数的计算。

具体步骤如下：

解决代码

import heapqclass MedianFinder:    def __init__(self):        self.small = []        self.big = []        def addNum(self, num):        if not self.big:            heapq.heappush(self.big, num)        else:            if num > self.big[0]:                heapq.heappush(self.big, num)            else:                heapq.heappush(self.small, num)                if len(self.small) > len(self.big):                    val = self.small.pop()                    heapq.heappush(self.big, val)        def findMedian(self):        if len(self.big) > len(self.small):            return self.big[0]        else:            return (self.small[0] + self.big[0]) / 2.0

解释

• addNum(num): 如果大顶堆为空，将num推入大顶堆中；否则，比较num与大顶堆的栈顶元素。如果num大于栈顶元素，将num推入大顶堆中；否则，将num推入小顶堆中。
• 维护堆的平衡：如果小顶堆的大小大于大顶堆的大小，将小顶堆的栈顶元素推入大顶堆中。
• findMedian(): 如果大顶堆的大小大于小顶堆的大小，返回大顶堆的栈顶元素；否则，返回小顶堆和大顶堆栈顶元素的平均值。

通过这种方法，我们可以在O(log n)的时间复杂度内进行addNum和findMedian操作，实现中位数的计算。

转载地址：http://vyfq.baihongyu.com/