資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python 中求最大最小值路徑
假設我們有一個包含 R 行 C 列的整數矩陣 A，我們需要找到從 [0,0] 到 [R-1,C-1] 的路徑的最大得分。這裡的評分技術將是該路徑中的最小值。例如，路徑 8 → 4 → 5 → 9 的值為 4。路徑從一個已訪問的單元格移動到四個基本方向（北、東、西、南）中的任何一個相鄰的未訪問單元格若干次。
例如，如果網格如下所示：
| 5 | 4 | 5 |
| 1 | 2 | 6 |
| 7 | 4 | 6 |
橙色單元格將是路徑。輸出為 4
為了解決這個問題，我們將遵循以下步驟：
- r := 行數，c := 列數
- ans := A[0, 0] 和 A[r – 1, c – 1] 的最小值
- 建立一個名為 visited 的矩陣，其順序與 A 相同，並將其全部填充為 FALSE
- h := 一個列表，其中我們儲存一個元組 (-A[0, 0], 0, 0)
- 從 h 建立堆
- 當 h 不為空時
- v, x, y := 從堆中刪除 h，並存儲三個值
- 如果 x = r – 1 且 y := c – 1，則退出迴圈
- ans := ans 和 A[x, y] 的最小值
- visited[x, y] := true
- 對於列表 [(-1, 0), (1, 0), (0, 1), (0, -1)] 中的 dy, dx，執行以下操作：
- a := x + dx 且 b := y + dy
- 如果 a 在 0 到 r – 1 的範圍內，並且 b 在 0 到 c – 1 的範圍內，並且 visited[a, b] 為假，
- 將 (-A[a, b], a, b) 插入到堆 h 中
- 返回 ans
讓我們看看以下實現，以便更好地理解：
示例
import heapq
class Solution(object):
def maximumMinimumPath(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
r,c = len(A),len(A[0])
ans = min(A[0][0],A[-1][-1])
visited = [[False for i in range(c)] for j in range(r)]
h = [(-A[0][0],0,0)]
heapq.heapify(h)
while h:
# print(h)
v,x,y = heapq.heappop(h)
if x== r-1 and y == c-1:
break
ans = min(ans,A[x][y])
visited[x][y]= True
for dx,dy in {(-1,0),(1,0),(0,1),(0,-1)}:
a,b = x+dx,y+dy
if a>=0 and a<r and b>=0 and b<c and not visited[a][b]:
heapq.heappush(h,(-A[a][b],a,b))
return ans輸入
[[5,4,5],[1,2,6],[7,4,6]]
輸出
4
更新於: 2020-03-05
400 次瀏覽
廣告