1266. Minimum Time Visiting All Points
給你一個座標陣列
依序走完所有地點
每一個單位的時間你可以直的(1)、橫的(1)、斜的走(2^1/2)一步
回傳最短需要花費的時間
Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
[1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Input: points = [[3,2],[-2,2]]
Output: 5
Intuition:
取max(Δx,Δy)之後加總就好。
Approach:
可以走直的、橫的、斜的的話
最短路徑 = max(Δx,Δy)
題目要求依照給的順序走
不用自己找最短路徑
所以用一個for迴圈跑完全部元素就好
TS Code:
function getPath (p1: number[], p2: number[]): number {
return Math.max(Math.abs(p1[0] - p2[0]), Math.abs(p1[1] - p2[1]))
}
function minTimeToVisitAllPoints (points: number[][]): number {
return points.reduce<{ lastPoint: number[], totalTime: number }>(
(prev, curr) => ({ lastPoint: curr, totalTime: prev.totalTime +
getPath(curr, prev.lastPoint) }),
{ lastPoint: points[0], totalTime: 0 })
.totalTime
}