最少时间访问所有积分Leetcode解决方案


难度级别 易得奖学金
经常问 亚马逊 彭博 Facebook Media.net
排列 几何

最短时间访问所有积分Leetcode解决方案的问题为我们提供了一个 排列 或坐标轴上的点向量。 向我们提供输入后的问题要求我们找到访问输入中所有要点的最短时间。 当您在x或y方向上移动一个单位时,将花费1个单位时间。 当您沿对角线移动时,将同时在两个方向上移动1个单位。 您遇到1个单位时间。 现在,找出访问所有给定点所需的最短时间。 还有另一个条件。 条件表明我们需要按照输入中给出的相同顺序移动所有点。 因此,让我们来看一些示例,而无需直接转向解决方案。

最少时间访问所有积分Leetcode解决方案

[[1,1],[3,4],[-1,0]]
7

说明:如图所示,我们需要3个单位时间才能从第一个点移动到第二个点。 然后4个单位时间从第二个点移动到最后一个点。 因此,总共需要7个时间单位。

最短时间访问所有点Leetcode解决方案的方法

最短时间访问所有点的问题Leetcode解决方案询问我们访问输入中给定的所有点的最短时间是多少。 这个问题也使我们不得不按照输入中提供的相同顺序来移动这些点。 我们也被告知每一步的费用。 我们可以在两个方向中的任何一个方向上移动1个单位,也可以在两个方向中的同时移动1个单位。 所有这些举动花费了我们1个单位时间。 因此,通常人们会尝试对角移动,直到x或y值之一等于下一个点的x或y值。 现在,我们确定x或y之一等于当前点的x或y。 现在我们只需要垂直或水平移动。

这种想法似乎有点棘手,但事实证明,解决问题要简单得多。 在这里,我们不是先分开进行处理,而是先对角线移动,然后再向一个方向移动。 我们只需找到当前点和下一点的x和y值的最大差即可。 这为我们提供了一个简单的公式。

代码

最少时间访问所有积分Leetcode解决方案的C ++代码

#include <bits/stdc++.h>
using namespace std;

int minTimeToVisitAllPoints(vector<vector<int>>& points) {
    int ans = 0;
    int n = points.size();
    for(int i=1;i<n;i++){
        vector<int> cur = points[i], prev = points[i-1];
        int curVal = max(abs(cur[0] - prev[0]), abs(cur[1] - prev[1]));
        ans += curVal;
    }
    return ans;
}

int main(){
    vector<vector<int>> points({{1,1},{3,4},{-1,0}});
    cout<<minTimeToVisitAllPoints(points);
}
7

最少时间访问所有积分Leetcode解决方案的Java代码

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static int minTimeToVisitAllPoints(int[][] points) {
        int ans = 0;
        int n = points.length;
        for(int i=1;i<n;i++){
            int[] cur = points[i];
            int[] prev = points[i-1];
            int curVal = Math.max(Math.abs(cur[0] - prev[0]), Math.abs(cur[1] - prev[1]));
            ans += curVal;
        }
        return ans;
    }
    
  public static void main (String[] args) throws java.lang.Exception {
    int[][] points = {{1,1},{3,4},{-1,0}};
    System.out.println(minTimeToVisitAllPoints(points));
  }
}
7

复杂度分析

时间复杂度

上), 因为我们必须遍历整个列表,因此时间复杂度是线性的。

空间复杂度

O(1), 因为我们只使用一个变量来存储答案,所以空间复杂度是恒定的。