herrDeng網內搜尋

自訂搜尋

Ads

2025年1月19日 星期日

Python C++BFS /heap解Leetcode難題407 Trapping Rain Water II


Py3 cpp BFS /heap解Leetcode難題407 Trapping Rain Water II
解題要訣:boundary由外而內,容器採min heap,BFS走訪
[Py3解請進]

-----
Tips for solving problems: boundary from outside toward inside, container using min heap, BFS transversal

  1. class Solution:
  2. def trapRainWater(self, height: List[List[int]]) -> int:
  3. dir = (0, 1, 0, -1, 0)
  4. m, n = len(height), len(height[0])
  5. if m <= 2 or n <= 2:
  6. return 0
  7.  
  8. boundary = []
  9. for i in range(m):
  10. boundary.append((height[i][0], i, 0))
  11. boundary.append((height[i][-1], i, n - 1))
  12. height[i][0] = height[i][-1] = -1
  13.  
  14. for j in range(1, n - 1):
  15. boundary.append((height[0][j], 0, j))
  16. boundary.append((height[-1][j], m - 1, j))
  17. height[0][j] = height[-1][j] = -1
  18.  
  19. heapify(boundary)
  20. ans, water_level = 0, 0
  21.  
  22. while boundary:
  23. h, i, j = heappop(boundary)
  24.  
  25. water_level = max(water_level, h)
  26.  
  27. for a in range(4):
  28. i0, j0 = i + dir[a], j + dir[a + 1]
  29. if i0 < 0 or i0 >= m or j0 < 0 or j0 >= n or height[i0][j0] == -1:
  30. continue
  31. currH = height[i0][j0]
  32. if currH < water_level:
  33. ans += water_level - currH
  34.  
  35. height[i0][j0] = -1
  36. heappush(boundary, (currH, i0, j0))
  37. return ans
  38.  

沒有留言:

Related Posts Plugin for WordPress, Blogger...

熱門文章