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

난이도 쉽게
자주 묻는 질문 아마존 블룸버그 게시물에서 Facebook Media.net
알고리즘 배열 코딩 기하학 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions조회수 74

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

모든 포인트를 방문하는 최소 시간 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 값의 최대 차이를 찾습니다. 이것은 우리에게 각 움직임에 대한 간단한 공식을 제공합니다.

암호

모든 포인트 방문 최소 시간을위한 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);
}
7

모든 포인트를 방문하는 최소 시간을위한 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));
  }
}
7

복잡성 분석

시간 복잡성

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

공간 복잡성

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

균열 시스템 설계 인터뷰
Translate »
1