Куча и стек python

2. LeetCode 225 реализует стек с использованием очередей

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Notes:
You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

2.2 Идеи

Стек идет последним, первым вышел, очередь — первым пришел, первым вышел, а очередь должна использовать collections.dequeue () в python
Чтобы использовать очередь для представления стека, порядок элементов стека корректируется, когда элементы помещаются в стек, и элементы перед последним элементом последовательно перемещаются в конец последний элемент, так что последний входит. Элемент находится в начале очереди.

2.3 код

class MyStack(object): def __init__(self): """ Initialize your data structure here. """ self.stack = collections.deque([]) def push(self, x): """ self.stack = [] Push element x onto stack. :type x: int :rtype: void """ self.stack.append(x) q = self.stack for i in range(len(q) - 1): q.append(q.popleft()) def pop(self): """ Removes the element on top of the stack and returns that element. :rtype: int """ return self.stack.popleft() def top(self): """ Get the top element. :rtype: int """ return self.stack[0] def empty(self): """ Returns whether the stack is empty. :rtype: bool """ if len(self.stack) == 0: return True else: return False

3. Используйте стек для реализации очереди (LeetCode 232)

3.1 Название

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Notes:
You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

3.2 Идеи

Стек идет последним, первым вышел, а очередь — первым пришел, первым ушел
может быть представлен двумя стеками, один для вставки в стек, а другой для выталкивания из стека. Порядок выхода из стека противоположен порядку вставки в стек.

3.3 код

class MyQueue(object): def __init__(self): """ Initialize your data structure here. """ self.input = [] self.output = [] def push(self, x): """ Push element x to the back of queue. :type x: int :rtype: void """ self.input.append(x) def pop(self): """ Removes the element from in front of queue and returns that element. :rtype: int """ self.peek() return self.output.pop() def peek(self): """ Get the front element. :rtype: int """ if self.output == []: while self.input: self.output.append(self.input.pop()) return self.output[-1] def empty(self): """ Returns whether the queue is empty. :rtype: bool """ return self.input == [] and self.output == []

4. Стек, содержащий функцию min (LeetCode 155 Min Stack)

4.1 Название

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.

4.2 Идеи

Используются два списка: один используется для представления стека, который используется для передачи данных и извлечения данных, а другой — это минимальный минимальный стек списка. Когда minstack == [] или текущий элемент меньше верхнего элемента minstack, this Элементы помещаются в minstack, чтобы гарантировать, что последний элемент minstack является наименьшим среди всех текущих элементов. При извлечении стека обратите внимание на то, равен ли верхний элемент стека верхнему элементу минимального стека. Если они равны, будут выталкиваться верхние элементы двух списков, в противном случае — только верхний элемент стека данных. будет всплывать

4.3 код

class MinStack(object): def __init__(self): """ initialize your data structure here. """ self.stack = [] self.minstack = [] def push(self, x): """ :type x: int :rtype: void """ self.stack.append(x) if self.minstack == [] or x 1]: self.minstack.append(x) def pop(self): """ :rtype: void """ if self.stack != []: if self.stack[-1] == self.minstack[-1]: self.minstack.pop() self.stack.pop() def top(self): """ :rtype: int """ if self.stack != []: return self.stack[-1] else: return None def getMin(self): """ :rtype: int """ if self.minstack != []: return self.minstack[-1] else: return None 

5. Юридическая последовательность

5.1 вопросы

Введите две целочисленные последовательности. Первая последовательность указывает порядок, в котором стек перемещается. Оцените, является ли вторая последовательность порядком всплывающих окон стека. Предположим, что все числа, помещенные в стек, не равны. Например, последовательность 1, 2, 3, 4, 5 — это порядок выталкивания определенного стека, а последовательность 4, 5, 3, 2, 1 — последовательность поп, соответствующая последовательности нажатия, но 4, 3, 5, 1, 2 Это не может быть последовательность pop последовательности push. (Примечание: длины этих двух последовательностей равны)

5.2 Идеи

Создайте новый стек, чтобы имитировать толкание и выталкивание стека. Если последовательность выталкивания верна, вновь созданный стек должен быть пустым.

5.3 Код

Class Solution: def IsPopOrder(self, pushV, popV): if pushV == [] or popV == []: return False stack = [] for i in pushV: stack.append(i) while len(stack) and stack[-1] == popV[0]: stack.pop() popV.pop(0) if stack != []: return False else: return True

6. Базовые знания о куче

Двоичная куча: специальное полное двоичное дерево, его характеристики:

• Значение всех родительских узлов в двоичном дереве не больше / не меньше его дочерних узлов;
• Значение корневого узла должно быть наименьшим / наибольшим среди всех узлов.

Значение родительского узла не больше, чем значение дочернего узла, а значение корневого узла является наименьшим, называется наименьшей кучей, и наоборот, наибольшей кучей. Куча — это расширенная структура данных, в python есть соответствующий модуль deapq

7. K-й по величине элемент в массиве (LeetCode 215 K-й по величине элемент в массиве)

7.1 Вопросы

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.**

7.2 Мышление

Идея 1: сначала отсортируйте массив, а затем решите k-й элемент
Идея 2. Используйте наименьшую кучу, k-е наибольшее число — это элемент с наименьшим len (q) -k

7.3 Код

# Метод сортировки class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ nums.sort() return nums[-k] # Метод минимальной кучи class Solution(object): def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ heap = [] for num in nums: heapq.heappush(heap, num) for i in range(len(nums) - k): heapq.heappop(heap) return heapq.heappop(heap) 

8. Найдите медиану из потока данных (LeetCode 295 Найдите медиану из потока данных)

8.1 Вопросы

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) — Add a integer number from the data stream to the data structure.
double findMedian() — Return the median of all elements so far.

8.2 Мышление

Поддерживайте две кучи, одна — это большая верхняя куча, а другая — небольшая верхняя куча, используя встроенную библиотеку python heapq.

Как показано на рисунке выше, каждый раз, когда вы добавляете элемент, убедитесь, что 0 Поскольку куча [0] представляет собой наименьший элемент в куче, поэтому, если куча [0] представляет самый большой элемент в куче, все элементы, добавленные в кучу, будут отрицательными. При добавлении элемента сначала возьмите отрицательный элемент и добавьте его в maxheap, а затем настройте maxheap и minheap: если самый большой элемент в maxheap больше, чем самый маленький элемент в minheap или l e n ( m a x h e a p ) > l e n ( m i n h e a p ) + 1 , Откройте самый большой элемент в maxheap и присоединитесь к minheap; если l e n ( m a x h e a p ) < l e n ( m i n h e a p ) , Наименьший элемент minheap добавляется в maxheap.
При нахождении медианы, если длина массива нечетная, возвращается m a x , Является четным числом, тогда верните ( m a x + m i n ) / 2

8.3 Код

from heapq import * class MedianFinder(object): def __init__(self): """ initialize your data structure here. """ self.minHeap = [] self.maxHeap = [] def addNum(self, num): """ :type num: int :rtype: void """ heappush(self.maxHeap, -num) minTop = self.minHeap[0] if len(self.minHeap) else None maxTop = self.maxHeap[0] if len(self.maxHeap) else None if minTop < -maxTop or len(self.minHeap) + 1 < len(self.maxHeap): heappush(self.minHeap, -heappop(self.maxHeap)) if len(self.maxHeap) < len(self.minHeap): heappush(self.maxHeap, -heappop(self.minHeap)) def findMedian(self): """ :rtype: float """ if len(self.minHeap) < len(self.maxHeap): return -1.0 * self.maxHeap[0] else: return (self.minHeap[0] - self.maxHeap[0]) / 2.0

Источник