Giải bài 407 trapping rain water II O(N^2)

interview
heap
leetcode
hard
bfs

(Lê Trần Đạt) #1

Đề bài

Bài giải

Code Python

class Solution(object):
    def trapRainWater(self, hm):
        """
        :type hm: List[List[int]]
        :rtype: int
        """
        if not hm or not hm[0]: return 0
        m, n = len(hm), len(hm[0])
        visit = [[0] * n for _ in xrange(m)]
        h = []
        
        for i in xrange(m):
            for j in xrange(n):
                if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                    heapq.heappush(h, (hm[i][j], i, j))
                    visit[i][j] = 1
                    
        water = 0
        while h:
            v, i, j = heapq.heappop(h)
            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 not visit[x][y]:
                    water += max(0, v - hm[x][y])
                    heapq.heappush(h, (max(v, hm[x][y]), x, y))
                    visit[x][y] = 1
        return water

Nhờ các bạn giải với các ngôn ngữ khác.

Sau hôm nay mình bận công việc sẽ tạm không quay được video, sau tết sẽ sắp xếp được thời gian. Chúc ae ăn tết vui vẻ :slight_smile:


Topic tổng hợp các video chia sẻ về interview của ltd
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?