LeetCode算法题整理（堆篇）Heap

Posted on   |   Updated on | In | | Visitors

1606. Find Servers That Handled Most Number of Requests

有k个服务器处理一些请求，第i个请求需要第i%k服务器来处理，如果服务器繁忙，则按序号向下找；找到末尾后再从头开始，如果所有的服务器都忙，那么该请求被丢弃。给定一些请求的到达时间和需要处理的时间，问处理最多个请求的服务器有哪些。

方法一：比赛时没有做出，后来想想发现挺简单的，用一个堆来维护繁忙的服务器，用一个有序的列表维护可用的服务器，环的问题比较难想，但是其实处理起来很简单，就是当找到末尾不够用时，使用队首的服务器就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
    cnt = [0] * k
    available_servers = list(range(k))
    busy_servers = []  # (endtime, server_id)
    for i, (at, rt) in enumerate(zip(arrival, load)):
        # release busy servers
        while busy_servers and busy_servers[0][0] <= at:
            _, server = heapq.heappop(busy_servers)
            bisect.insort(available_servers, server)
        if len(available_servers) == 0: 
            continue
        cur_server = i % k
        index = bisect.bisect_left(available_servers, cur_server) % (len(available_servers))
        server = available_servers.pop(index)
        cnt[server] += 1
        heapq.heappush(busy_servers, (at+rt, server))
        
    max_cnt = max(cnt)
    return [i for i, s in enumerate(cnt) if s==max_cnt]

215. Kth Largest Element in an Array

找出数组中最大的第K个数。原题

快排的思想，没有通过LeetCode测试用例，因为内存超出了限制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def findKthLargest(self, nums, k):
    if not nums:
        return 
    pivot = nums[0]
    left, medium, right = [], [], []
    for num in nums:
        if num < pivot:
            left.append(num)
        elif num == pivot:
            medium.append(num)
        else:
            right.append(num)
    
    if k <= len(right):
        return self.findKthLargest(right, k)
    elif k-len(right) <= len(medium):
        return pivot
    else:
        return self.findKthLargest(left, k-len(right)-len(medium))
考虑在原数组上进行修改。Time-O(n) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def findKthLargest(self, nums: List[int], k: int) -> int:
    random.shuffle(nums)
    l, r = 0, len(nums)-1

    def partition(l, r):
        for i, v in enumerate(nums[l:r+1], l):
            if nums[i] >= nums[r]:
                nums[i], nums[l] = nums[l], nums[i]
                l += 1
        return l-1  # return the index of pivot

    while True:
        pos = partition(l, r)   # pos是索引，所以要与k-1比较
        if pos < k-1:
            l = pos + 1
        elif pos > k-1:
            r = pos - 1
        else:
            return nums[pos]
使用堆。Time-O(nlogk) 
1
2
3
4
5
6
7
8
def findKthLargest(self, nums: List[int], k: int) -> int:
    import heapq as hq
    heap = nums[:k]
    hq.heapify(heap)
    for num in nums[k:]:
        if num > heap[0]:
            hq.heapreplace(heap, num)
    return heap[0]

703. Kth Largest Element in a Stream

流中第K个大的数。原题

1
2
3
4
5
6
7
8
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

方法一：还是使用堆，一开始没想到切分，所以超时了。注意是heapreplace。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class KthLargest:
    
    def __init__(self, k, nums):
        import heapq
        self.heap = list(nums)
        self.k = k
        heapq.heapify(self.heap)
        while len(self.heap) > k:
            heapq.heappop(self.heap)

    def add(self, val):
        if len(self.heap) < self.k:
            heapq.heappush(self.heap, val)
        elif val > self.heap[0]:
            heapq.heapreplace(self.heap, val)
        return self.heap[0]

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

最长的连续子数组，绝对值不大于limit。原题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

方法一：堆，Time: O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
def longestSubarray(self, nums: List[int], limit: int) -> int:
    maxd, mind = [], []
    res = i = 0
    for j, a in enumerate(nums):
        heapq.heappush(maxd, (-a, j))
        heapq.heappush(mind, (a, j))
        while -maxd[0][0] - mind[0][0] > limit:
            i = min(maxd[0][1], mind[0][1]) + 1
            while maxd[0][1] < i: heapq.heappop(maxd)
            while mind[0][1] < i: heapq.heappop(mind)
        print(maxd, '--', mind)
        res = max(res, j - i + 1)
    return res

1631. Path With Minimum Effort

找出一条左上到右下的路径，路径中体力消耗为最大的两个格子的差，找到能走到右下的最小消耗值，可以走上下左右。

1
2
3
4
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.

方法一：作为竞赛3题，1个小时都没有想出来，想法想偏了，因为如果只能走右和下，那么问题很简单，是一个dp问题。所以一开始也往dp方向考虑。实际上通过数据范围的上限可以考虑二分法 + bfs。效率不高，4000ms。

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
def minimumEffortPath(self, g: List[List[int]]) -> int:

    lo, hi = 0, 10**6
    M, N = len(g), len(g[0])
    def check(d):
        q = [(0, 0)]
        seen = [[False]*N for _ in range(M)]
        seen[0][0] = True
        for i, j in q:
            if i==M-1 and j==N-1:
                return True
            for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
                if 0<=x<M and 0<=y<N and abs(g[x][y]-g[i][j])<=d and \
                    not seen[x][y]:
                    q.append((x, y))
                    seen[x][y] = True
        return False

    while lo < hi:
        mid = (lo + hi) >> 1
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

方法二：Dijikstra’s算法。堆，堆的方法比方法一快很多，哟还那个是700ms。核心是维护一个dist用来记录每个点的最小距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def minimumEffortPath(self, g: List[List[int]]) -> int:
    heap = [(0, 0, 0)]        
    M, N = len(g), len(g[0])
    dist = [[float('inf')]*N for _ in range(M)]
    while heap:
        d, i, j = heapq.heappop(heap)
        if i==M-1 and j==N-1:
            return d
        cur = g[i][j]
        for x, y in ((i-1, j), (i+1, j), (i, j+1), (i, j-1)):
            if 0<=x<M and 0<=y<N:
                new_dist = max(d, abs(g[x][y]-cur))
                if dist[x][y] > new_dist:
                    dist[x][y] = new_dist
                    heapq.heappush(heap, (max(d, abs(g[x][y]-cur)), x, y))

778. Swim in Rising Water

和1631几乎一样，从左上到右下，经过的所有点的最大值最小。

1
2
3
4
5
6
7
8
9
10
11
Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

方法一：二分法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def swimInWater(self, grid: List[List[int]]) -> int:
    lo, hi = max(grid[0][0], grid[-1][-1]), 50*50
    M, N = len(grid), len(grid[0])

    def check(d):
        q = [(0, 0)]
        seen = [[False]*N for _ in range(M)]
        seen[0][0] = True
        for i, j in q:
            if i==M-1 and j==N-1:
                return True
            for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
                if 0<=x<M and 0<=y<N and grid[x][y]<=d and not seen[x][y]:
                    q.append((x, y))
                    seen[x][y] = True
        return False

    while lo < hi:
        mid = (lo + hi) >> 1
        if check(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo
方法二：Dijikstra’s。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def swimInWater(self, grid: List[List[int]]) -> int:
    heap = [(grid[0][0], 0, 0)]
    M, N = len(grid), len(grid[0])
    res = [[inf]*N for _ in range(M)]
    while heap:
        d, i, j = heapq.heappop(heap)
        if i==M-1 and j==N-1:
            return d
        cur = grid[i][j]
        for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
            if 0<=x<M and 0<=y<N:
                new_d = max(d, grid[x][y])
                if new_d < res[x][y]:
                    res[x][y] = new_d
                    heapq.heappush(heap, (new_d, x, y))

1642. Furthest Building You Can Reach

一个人在爬一群建筑物，当建筑物比当前高时，需要一个梯子和高度差个砖块，给你一些梯子和砖块，问最远能走到哪里。

1
2
3
4
5
6
7
8
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.

方法一：竞赛时想偏了，超时了。这里有点贪心的思维，需要爬升的次数优先使用梯子，如果不够了，使用高度差最小的用砖块替代，如果不够了，证明走得是最远了。

1
2
3
4
5
6
7
8
9
10
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
    upstairs = []
    for i in range(len(heights)-1):
        if heights[i+1] > heights[i]:
            heapq.heappush(upstairs, heights[i+1]-heights[i])
        if len(upstairs) > ladders:
            bricks -= heapq.heappop(upstairs)
        if bricks < 0:
            return i
    return len(heights) - 1

1675. Minimize Deviation in Array

将奇数*2，或者偶数除2，返回可以将数组最大值最小值差最小是多少。

1
2
3
Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.

方法一：将所有奇数变成偶数，这个时候所有的值都是最大的，包括最小值。然后每次将最大的值除2，来降低上限。注意这个过程中最小值可能更新。使用堆来做优先级队列。

1
2
3
4
5
6
7
8
9
10
11
def minimumDeviation(self, nums: List[int]) -> int:
    nums = [n*2 if n&1==1 else n for n in nums]
    mi = min(nums)
    heap = [-n for n in nums]
    heapq.heapify(heap)
    res = inf
    while heap[0] & 1 == 0:
        mi = min(mi, -heap[0]//2)
        heapq.heapreplace(heap, heap[0]//2)
        res = min(res, abs(-heap[0] - mi))
    return res

1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

二维数组每行有序，从每行选出一个数字，所有的行累加和第K小的是多少。

1
2
3
4
Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

方法一：可以暴力，但是不能使用product，那样复杂度太高了

1
2
3
4
5
def kthSmallest(self, mat: List[List[int]], k: int) -> int:
    h = mat[0][:]
    for row in mat[1:]:
        h = sorted([i+j for i in row for j in h])[:k]
    return h[-1]

方法二：使用堆作为优先级队列，枚举每行向右移动一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def kthSmallest(self, mat: List[List[int]], k: int) -> int:
    M, N = len(mat), len(mat[0])
    p = [0] * M
    cur_sum = 0
    for row in mat:
        row.append(inf)
        cur_sum += row[0]

    seen = {tuple(p)}
    heap = [(cur_sum, tuple(p))]
    for _ in range(k-1):
        cur_sum, p = heapq.heappop(heap)
        for i, d in enumerate(p):
            if d < N-1:
                tp = p[:i] + (d+1, ) + p[i+1:]
                if tp not in seen:
                    heapq.heappush(heap, (cur_sum+mat[i][d+1]-mat[i][d], tp))
                    seen.add(tp)
    return heap[0][0]