LeetCode - Easy - 1266. Minimum Time Visiting All Points

左手的ㄟ右手 2022-10-16 04:46 35阅读 0赞

## Topic ##

*  Array
 *  Geometry

## Description ##

[https://leetcode.com/problems/minimum-time-visiting-all-points/][https_leetcode.com_problems_minimum-time-visiting-all-points]

On a 2D plane, there are `n` points with integer coordinates `points[i] = [xi, yi]`. Return the **minimum time** in seconds to visit all the points in the order given by `points`.

You can move according to these rules:

*  In `1` second, you can either:
    
     *  move vertically by one unit,
     *  move horizontally by one unit, or
     *  move diagonally `sqrt(2)` units (in other words, move one unit vertically then one unit horizontally in `1` second).
 *  You have to visit the points in the same order as they appear in the array.
 *  You are allowed to pass through points that appear later in the order, but these do not count as visits.

**Example 1:**

![d5c370d72f780185c9614d5ca5535c3b.png][]

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

## Analysis ##

观察并得出过滤。

## Submission ##

public class MinimumTimeVisitingAllPoints { 
        public int minTimeToVisitAllPoints(int[][] points) { 
        	int sum = 0;
        	for(int i = 1; i < points.length; i++) { 
        		sum += (Math.max(Math.abs(points[i][0] - points[i - 1][0]), // 
        					Math.abs(points[i][1] - points[i - 1][1])));
        	}
            return sum;
        }
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class MinimumTimeVisitingAllPointsTest { 
    
    	@Test
    	public void test() { 
    		MinimumTimeVisitingAllPoints obj = new MinimumTimeVisitingAllPoints();
    
    		assertEquals(7, obj.minTimeToVisitAllPoints(new int[][] { { 1, 1}, { 3, 4}, { -1, 0}}));
    		assertEquals(5, obj.minTimeToVisitAllPoints(new int[][] { { 3, 2},{ -2, 2}}));
    	}
    }

[https_leetcode.com_problems_minimum-time-visiting-all-points]: https://leetcode.com/problems/minimum-time-visiting-all-points/
[d5c370d72f780185c9614d5ca5535c3b.png]: /images/20221014/efab76e4448645f3a7929b34d85b249e.png