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
}