数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
广告