資料結構
網路
關係型資料庫管理系統 (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 次檢視
廣告