访问所有点的最小时间

1266. 访问所有点的最小时间

平面上有 n 个点，点的位置用整数坐标表示 points[i] = [x_i, y_i] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。

你需要按照下面的规则在平面上移动：

每一秒内，你可以：
- 沿水平方向移动一个单位长度，或者
- 沿竖直方向移动一个单位长度，或者
- 跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
必须按照数组中出现的顺序来访问这些点。
在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。

示例 1：

输入：points = [[1,1],[3,4],[-1,0]]
输出：7
解释：一条最佳的访问路径是： [1,1] -> [2,2] -> [3,3] -> [3,4] -> [2,3] -> [1,2] -> [0,1] -> [-1,0]   
从 [1,1] 到 [3,4] 需要 3 秒 
从 [3,4] 到 [-1,0] 需要 4 秒
一共需要 7 秒

示例 2：

输入：points = [[3,2],[-2,2]]
输出：5

提示：

points.length == n
1 <= n <= 100
points[i].length == 2
-1000 <= points[i][0], points[i][1] <= 1000

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minTimeToVisitAllPoints(vector<vector<int>>& points) { } };

rust 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-09-13 10:27:03

// 解法一
/*
impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        let mut time = 0;
        let mut t1;
        let mut t2;
        for i in 1..points.len() {
            t1 = (points[i][0] - points[i-1][0]).abs();
            t2 = (points[i][1] - points[i-1][1]).abs();
            if t1>t2 {
                time += t1;
            } else {
                time += t2;
            }
        }
        time
    }
}
*/

// 解法二
/*
impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        let mut ret = 0;

        for i in 0..(points.len() - 1) {
            let (x0, y0) = (points[i][0], points[i][1]);
            let (x1, y1) = (points[i + 1][0], points[i + 1][1]);
            ret += (x0 - x1).abs().max((y0 - y1).abs());
        }

        ret
    }
}
*/

// 解法三：函数式
impl Solution {
    pub fn min_time_to_visit_all_points(points: Vec<Vec<i32>>) -> i32 {
        points.windows(2)
            .map(|ele| Solution::getMax(&ele[0], &ele[1]) )
            .sum()
    }

    fn getMax(prev: &Vec<i32>, next: &Vec<i32>) -> i32 {
        prev.iter()
            .zip(next.iter())
            .map(|(i, j)| (j-i).abs())
            .max()
            .unwrap()
    }

}

cpp 解法, 执行用时: 8 ms, 内存消耗: 10 MB, 提交时间: 2023-09-13 10:24:31

class Solution {
public:
    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        int x0 = points[0][0], x1 = points[0][1];
        int ans = 0;
        for (int i = 1; i < points.size(); ++i) {
            int y0 = points[i][0], y1 = points[i][1];
            ans += max(abs(x0 - y0), abs(x1 - y1));
            x0 = y0;
            x1 = y1;
        }
        return ans;
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 41.9 MB, 提交时间: 2023-09-13 10:23:28

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

golang 解法, 执行用时: 0 ms, 内存消耗: 3.2 MB, 提交时间: 2023-09-13 10:21:47

func minTimeToVisitAllPoints(points [][]int) int {
    ans := 0
    n := len(points)
    for i := 1; i < n; i++ {
        ans += max(abs(points[i][0]-points[i-1][0]), abs(points[i][1]-points[i-1][1]))
    }
    return ans
}

func abs(a int) int { if a < 0 { return -a }; return a }
func max(a, b int) int { if a < b { return b }; return a }

python3 解法, 执行用时: 44 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-13 10:20:17

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

php 解法, 执行用时: 24 ms, 内存消耗: 15.3 MB, 提交时间: 2021-06-09 11:25:19

class Solution {

    /**
     * @param Integer[][] $points
     * @return Integer
     */
    function minTimeToVisitAllPoints($points) {
        $ans = 0;
        $n = count($points);
        for($i=1;$i<$n;$i++) {
            $ans += max(abs($points[$i][0]-$points[$i-1][0]), abs($points[$i][1]-$points[$i-1][1]));
        }
        return $ans;
    }
}

上一题

下一题

详情