数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python 中计算访问城市街区的总距离
假设我们有一个由唯一字符串表示的城市街区的矩阵，以及另一个包含要访问的街区的字符串列表。如果我们位于街区 matrix[0][0]，则查找按顺序访问每个街区所需的总曼哈顿距离。
因此，如果输入类似于
| Q | B | C |
| D | E | Z |
| G | G | i |
Block = [H,B,C]
那么输出将为 6，因为“h”在下方（南）2 个街区，右侧（东）1 个街区，“b”在上方（北）2 个街区，“c”在右侧（东）1 个街区。
要解决此问题，我们将遵循以下步骤：
- coords := 一个键为 'start'，值为 (0, 0) 的映射
- 对于 mat 中的每一行，执行
- 对于 mat 中的每一列，执行
- 将 (row,col) 插入到 coords[mat[row, col]] 中
- 对于 mat 中的每一列，执行
- dist := 0
- 更新 blocks，在开头添加 'start'
- 对于 i 在 0 到 blocks 大小 -1 的范围内，执行
- c1 := coords[blocks[i]]
- c2 := coords[blocks[i+1]]
- d := |c1[0]-c2[0]| + |c1[1]-c2[1] |
- dist := dist + d
- 返回 dist
让我们看看以下实现以更好地理解：
示例
class Solution:
def solve(self, mat, blocks):
coords = {'start': (0,0)}
for row in range(len(mat)):
for col in range(len(mat[row])):
coords[mat[row][col]] = (row,col)
dist = 0
blocks = ['start']+blocks
for i in range(len(blocks)-1):
c1 = coords[blocks[i]]
c2 = coords[blocks[i+1]]
d = abs(c1[0]-c2[0]) + abs(c1[1]-c2[1])
dist += d
return dist
ob = Solution()
inp = [["q", "b", "c"],
["d", "e", "z"],
["g", "h", "i"]]
blk = ["h", "b", "c"]
print(ob.solve(inp, blk))输入
[["q", "b", "c"],["d", "e", "z"],["g", "h", "i"]]
输出
6
更新于： 2020-09-22
175 次查看
广告