LeetCode 1266. Minimum Time Visi

2020-11-28  本文已影响0人  LiNGYu_NiverSe

On a plane there are n points with integer coordinates points[i] = [xi, yi]. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

Example 1:

image

Input: points = [[1,1],[3,4],[-1,0]]
Output: 7
Explanation: One optimal path is [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds</pre>

Example 2:

Input: points = [[3,2],[-2,2]]
Output: 5
</pre>

Constraints:

Solution:

class Solution:
    def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
        ans = 0
        for i in range(len(points) - 1):
            cur, nxt = points[i], points[i+1]
            ans += max(
                abs(nxt[0] - cur[0]), abs(nxt[1] - cur[1])
                       )
        return ans

The idea is to loop all points by calculating the time spent of current point and next point. Since we can either move diagonally, horizontally or vertically once at a time, it is clear the time spent is determined by the longest distance of dx or dy, because when we can consume dx and dy at the same time by moving diagonally.
本题解法是循环所有点并计算当前点和下一个点所花费的时间。由于我们每次可以沿对角线,水平或垂直移动一次,因此很明显,花费的时间取决于dx或dy的最长距离,因为当我们可以通过对角线移动同时消耗dx和dy。

上一篇 下一篇

猜你喜欢

热点阅读