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
(Trần Nhật Anh) #2

Em đã xem hết các videos về interview của anh. Cảm ơn anh đã chia sẻ. Hi vọng anh sẽ làm thêm nhiều video nữa.


83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?