Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

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
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701570204.A.740.html
推 wwndbk: 大師
→ wwndbk: 怎麼又是簡單==
→ sixB: ez
→ ZooseWu: 我原本以為要自己找最短路徑 結果只要照著順序跑