모든 포인트를 방문하는 최소 시간 Leetcode 솔루션-TutorialCup

모든 포인트를 방문하는 최소 시간 Leetcode 솔루션의 문제는 우리에게 정렬 또는 좌표축상의 점으로 구성된 벡터. 입력을 제공 한 후의 문제는 입력에 제공된 모든 포인트를 방문 할 최소 시간을 찾도록 요청합니다. x 또는 y 방향으로 한 단위를 이동하면 1 단위의 시간이 걸립니다. 대각선으로 이동하면 동시에 양방향으로 1 단위 이동합니다. 당신은 1 단위 시간을 만납니다. 이제 주어진 모든 지점을 방문하는 데 필요한 최소 시간을 알아보십시오. 또 다른 조건이 있습니다. 조건은 입력에 제공된 것과 동일한 순서로 모든 지점을 이동해야 함을 나타냅니다. 따라서 솔루션으로 직접 이동하지 않고 몇 가지 예를 살펴 보겠습니다.

핀

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

설명 : 이미지에서도 볼 수 있듯이 첫 번째 지점에서 두 번째 지점으로 이동하려면 3 단위 시간이 필요합니다. 그런 다음 두 번째에서 마지막 지점으로 이동하는 데 4 단위 시간이 걸립니다. 따라서 총 7 단위의 시간이 필요합니다.

차례

모든 포인트를 방문하는 최소 시간을위한 접근법 Leetcode 솔루션

모든 포인트를 방문하는 최소 시간 문제 Leetcode 솔루션은 입력에 주어진 모든 포인트를 방문하는 최소 시간이 얼마인지 묻습니다. 이 문제는 또한 입력에 제공된 것과 동일한 순서로 포인트를 이동하도록 제한합니다. 우리는 또한 각 이동의 비용에 대해서도 들었습니다. 두 방향 중 하나로 1 단위를 이동하거나 양쪽 방향으로 동시에 1 단위를 이동할 수 있습니다. 이 모든 이동에는 1 단위의 시간이 소요됩니다. 따라서 일반적으로 x 또는 y 값 중 하나가 다음 점의 x 또는 y 값과 같을 때까지 대각선으로 이동하려고합니다. 이제 x 또는 y 중 하나가 현재 점의 x 또는 y와 동일하다는 것을 확신합니다. 이제 수직 또는 수평으로 만 움직여야합니다.

생각은 조금 힘들어 보이지만 문제의 구현은 훨씬 더 간단합니다. 여기서는 먼저 대각선으로 이동 한 다음 한 방향으로 이동하는 프로세스를 별도로 수행하는 대신. 우리는 단순히 현재와 다음 점의 x와 y 값의 최대 차이를 찾습니다. 이것은 우리에게 각 움직임에 대한 간단한 공식을 제공합니다.

암호

모든 포인트 방문 최소 시간을위한 C ++ 코드 Leetcode 솔루션

#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);
}

모든 포인트를 방문하는 최소 시간을위한 Java 코드 Leetcode 솔루션

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));
  }
}

복잡성 분석

시간 복잡성

의 위에), 목록 전체를 순회해야하기 때문에 시간 복잡도는 선형 적입니다.

공간 복잡성

O (1), 답을 저장하기 위해 하나의 변수 만 사용했기 때문에 공간 복잡도는 일정합니다.

모든 포인트 Leetcode 솔루션을 방문하는 최소 시간