【leetcode】1266. Minimum Time Visiting All Points

题目如下：

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:

In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).

You have to visit the points in the same order as they appear in the array.

Example 1:
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
Example 2:
Input: points = [[3,2],[-2,2]]

Output: 5
Constraints:

points.length == n

1 <= n <= 100

points[i].length == 2

-1000 <= points[i][0], points[i][1] <= 1000

解题思路：优先走斜线，直到满足起点的x坐标等于终点的x坐标或者起点的y坐标等于终点的y坐标；然后走直线，直至到达终点。

代码如下：

class Solution(object):

    def minTimeToVisitAllPoints(self, points):

        """

        :type points: List[List[int]]

        :rtype: int

        """

        def calc(x1,y1,x2,y2):

            distance = min(abs(x1-x2),abs(y1-y2))

            return distance + abs(abs(x1-x2) - distance) + abs(abs(y1-y2) - distance)

        res = 0

        for i in range(len(points)-1):

            res += calc(points[i][0],points[i][1],points[i+1][0],points[i+1][1])

        return res

巴特西

【leetcode】1266. Minimum Time Visiting All Points

最新文章

热门文章