Series of articles:
View all series: xiaozhuanlan.com/leetcode_tc
Algorithm interview (1) linked list algorithm interview (7) breadth and depth first algorithm
1. The concept
Priority queue, comparison queue, as the name implies, is normal in, by priority out. You can press small to large, or press large to small, or customize an attribute to queue according to its characteristics.
2. Implementation mechanism
2.1 Heap Heap
Heap is a small top Heap and a large top Heap.
There are many different implementations of the Heap, and you can find them by sharing a link with Google Heap. En.wikipedia.org/wiki/Heap_ (…
There is a picture in this content for you to share
2.2 Binary Search Tree Binary Search Tree
Binary search trees, also known as binary search trees, are described in more detail in a later section. A brief introduction to one feature:
- If the left subtree of any node is not empty, the value of all nodes in the left subtree is less than the value of its root node.
- If the right subtree of any node is not empty, the value of all nodes in the right subtree is greater than the value of its root node.
- The left and right subtrees of any node are binary search trees respectively.
3. The interview questions
Kth Largest Element in a Stream Returns the Largest Element in a Stream
Leetcode 703 questions
Topic request
Design a class to find the kth largest element in a stream. Design a class that finds the KTH largest element in the data streamCopy the codeExample:
int k = 3;
int[] arr = [4.5.8.2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
Copy the codeTheir thinking
If K=1, which is actually the maximum value in the data stream, it is easier to record the maximum value each time, such as [4,5,8,2]. Similarly, if you want to find the KTH largest element, there are two solutions:
- The first is to keep the first K largest elements in an array and sort them. That is, one element at a time is compared to the smallest value in the array. If the value of the element is greater than the smallest value, the smallest element in the array is popped, the current element is inserted into the array, and sorted again. The time complexity is N * klogk, which is the time complexity of sorting (counting the fastest quicksort).
- The first is still a bit slow, and the second is implemented using today’s topic priority queue, maintaining a small top heap MinHeap at a time. The size of the MinHeap is K. Each incoming element is compared to the top element, and if the element is smaller than the top element, it continues down. If the element is larger than the top element, the top element is removed, the current element is inserted into the MinHeap, and the heap order is rearranged. Time, N * (1 or log2K), worst case is to adjust the heap every time, the time to adjust the heap is log2K. O(1) if no adjustment is required.
Code implementation
The code is implemented in the second way.
import heapq
class KthLargest(object):
def __init__(self, k, nums):
""" :type k: int :type nums: List[int] """
self.k = k
self.min_heap = []
for i in nums:
self.add(i)
def add(self, val):
""" :type val: int :rtype: int """
if len(self.min_heap) < self.k:
heapq.heappush(self.min_heap, val)
else:
if val > self.min_heap[0]:
heapq.heappop(self.min_heap)
heapq.heappush(self.min_heap, val)
return self.min_heap[0]
Copy the codeHeapq is a python module that implements the small top heap. If it were a different language, it would have a function that implements the heapq internally. Heappush is inserting elements into the heap, the function rearranges the order again, and heappop is the top of the heap element pop. The code is consistent with the above text description.
Sliding Window Maximum Returns the Maximum value of the Window
Leetcode 239 questions
Given an array nums, a sliding window of size K moves from the leftmost part of the array to the rightmost part of the array. Returns the maximum sliding window value.
Example:
Input: nums = [1, 3, 1, 3,5,3,6,7], and the Output: k = 3,3,5,5,6,7 [3] Explanation: Window position Max --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 1. [5 3 6] 7 6 1 3-1-3 5 [3 6 7] 7Copy the codeThere are also two ways to solve this problem.
- The first solution is a big top implementation that maintains a size= K MaxHeap and a Count Map for each worthy location. For example, if you start [1,3,-1], the top of the heap is 3, and you return a maximum of 3, and if you do another -3, which is less than 3, the top of the heap is still 3, but the original 1 needs to be removed from the heap and -3 needs to be added. So you need to maintain the heap, remove old elements, add new ones, and the result is the top of the heap. I’ll show you the code in a second. The time is NlogK.
- The second one is more complicated and can be simplified. The problem is that the number of Windows to be maintained is fixed, that is, size=k, so we can use Queue as described in the previous section. However, there is a slight difference between Queue deque and Queue deque, that is, both sides can enter and exit. How did that happen? Add k elements to the deque one by one, and maintain the queue each time a new element comes in. The focus is on the logic of maintenance. First, ensure that the length of the deque cannot be greater than K, and the leftmost element is always the largest element. For example, [1,3,-1], then the deque becomes [3, -1] after maintenance, because 1 is smaller than 3, and it’s older than 3, so that’s definitely not the element we’re looking for, so it’s 3. Add another -3, and the deque becomes [3,-1,-3], because -3 is smaller than 3, so add it to the latest position, and you get 3 again. First, remove the old element -3 and turn it into [-1,-3,5]. If these three elements are compared and it is found that both -1 and -3 are smaller than 5, remove them again and turn them into [5], so the result is 5. The output for the text description example is [3,3,5]
Code implementation
- The first solution: MaxHeap implementation
import collections
import heapq
class Solution(object):
def maxSlidingWindow(self, nums, k):
""" :type nums: List[int] :type k: int :rtype: List[int] """
count_map, max_heap, result = collections.Counter(), [], []
for i, num in enumerate(nums):
heapq.heappush(max_heap, -num)
count_map[num] += 1 # Count for each element
while not count_map[-max_heap[0]] :Remove old elements from the top of the heap
heapq.heappop(max_heap)
if i >= k - 1:
result.append(-max_heap[0])
count_map[nums[i - k + 1- =]]1 # change count before k to 0
return result
Copy the codeCountMap uses python Counter(), which is a Map with num as the key and count as the value. [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] [-1,-2,-3] The other thing to notice is that instead of going to the old element that’s not at the top of the heap and count=0, we’re going to wait until it’s at the top of the heap, and if it’s less than size=k, we’re going to clear it. That’s a little bit easier to implement, maybe a little bit harder to understand.
- Second solution: Deque double-ended queue (recommended solution)
class Solution(object):
""" deque implementation """
def maxSlidingWindow(self, nums, k):
""" :type nums: List[int] :type k: int :rtype: List[int] """
if not nums:
return []
result, window = [], []
for i, num in enumerate(nums):
if i >= k and window[0] <= i - k:
window.pop(0) Clear old elements from the leftmost part of the queue
while window and nums[window[- 1]] <= num:
window.pop() Clear elements smaller than the current element from the right side of the queue
window.append(i)
if i >= k - 1:
result.append(nums[window[0]])
return result
Copy the codeThe second solution uses a double-ended queue, iteratively enumerating nums. Window is the index of the NUMS element, not the value. If the index of the leftmost element of window exceeds i-K, the element becomes obsolete and needs to be culled from the leftmost element of the queue. If the element to the right of the window is found to be smaller than the current element, then all elements are removed. The current element must be newer than these elements. Insert the current element into the window and take the value to the left of the window as the result, because the value to the left is always the largest.
The full code has been uploaded to github github.com/CrystalSkyZ…
More exciting articles please pay attention to the public account ChengTian_Tech notes (ChengTian_Tech)
