직선 Leetcode 솔루션인지 확인

난이도 쉽게
자주 묻는 질문 Palantir Technologies
알고리즘 배열 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 수학조회수 88

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

이 문제에서 우리는 정렬 포인트 이것은 XY 2-D 평면에있는 일부 점의 x 좌표 및 y 좌표 목록을 나타냅니다. 이 점들이 직선을 이루는 지 확인해야합니다. 입력에 최소 2 개의 포인트가 있으며 절대 값은 10 ^ 4를 초과하지 않습니다.

Co-ordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}}
true

설명 다음 다이어그램은 모든 점이 동일 선상에 있음을 확인합니다.

직선 Leetcode 솔루션인지 확인

Co-ordinates = {{1 , 2} , {3 , 4}}
true

설명: 두 개의 연결된 점이 항상 직선을 형성합니다.

접근

주어진 목록에 점이 두 개뿐이면 항상 직선을 형성하고 결과가 참이라는 것을 쉽게 알 수 있습니다. 그러나 세 개의 점이있는 경우 모두 동일 선상에있을 수도 있고 그렇지 않을 수도 있습니다. 따라서 두 점을 고정하고 통과하는 선을 형성하고 다른 모든 점이 동일한 선에 있는지 확인할 수 있습니다. 수학적으로 이것은 다음을 확인하여 수행 할 수 있습니다. 경사 두 점 사이에 형성된 선의 예를 들어, 세 가지 점이 있다고 생각해 봅시다. P1 = (x1, y1) , p2 = (x2, y2) 및 P3 = (x3, y3).

이제 P1과 P2를 지나는 선을 만들어 봅시다. 이 선의 기울기는 다음과 같습니다.

경사 = (Y2 - Y1) / (x2 - x1)

P3이 P1 및 P2와 동일 선상에 있는지 확인하기 위해 먼저 점 P2 및 P3에 의해 형성된 선의 기울기를 찾으십시오. 그건,

경사(P2 및 P3) = (Y3 - Y2) / (x3 - x2)

이제 점은 다음과 같은 경우에만 동일 선상에 있습니다. P1 및 P2에 의해 형성된 선의 기울기 = P2 및 P3에 의해 형성된 선의 기울기.

따라서 P1, P2 및 P3이 동일 선상에 있으면

(y2 – y1) : (x2 – x1) :: (y3 – y2) : (x3 – x2), 또는

(y2 – y1) * (x3 – x2) = (x2 – x1) * (y3 – y2)

따라서 P1과 P2의 두 점을 수정할 수 있으며 i > 2 입력 목록에서 기울기 (1, 2) 동일하다 기울기 (1, i) 기준 위에서 본 것처럼 교차 제품 검사.

암호알고리즘

  1. 부울 함수를 사용합니다. checkStraightLine () 전달 된 점 배열이 직선을 형성하는지 여부를 반환합니다.
  2. 어레이에 2 포인트들:
    • 참을 돌려 주다
  3. 초기화 x0 첫 번째 점의 x 좌표로 y0 두 번째 점의 y 좌표로. 비슷하게, (x1, y1) 두 번째 점의 좌표
  4. 제품 간 확인을 위해 차이가 필요하므로 차이를 다음과 같이 저장하십시오.
    • dx = x1 - x0.
    • 다이 = y1 – y0
  5. 이제 두 번째 점 이후 배열의 모든 점에 대해 :
    1. 이 점의 x 및 y 좌표를 변수에 저장 xy
    2. 이제 처음 두 점의 기울기와이 점과 첫 번째 점의 기울기가 동일한 지 확인합니다.
      • If 다이 * (x – x0) is 지원 동일 dx * (y – y0)
        • 거짓 반환
  6. 참 반환
  7. 결과 인쇄

직선 Leetcode 솔루션인지 확인 구현

C ++ 프로그램

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

bool checkStraightLine(vector <vector <int> > &coordinates)
{
    if(coordinates.size() == 2)
        return true;

    int x0 = coordinates[0][0] , x1 = coordinates[1][0];
    int y0 = coordinates[0][1] , y1 = coordinates[1][1];

    int dx = x1 - x0 , dy = y1 - y0;
    for(int i = 2 ; i < coordinates.size() ; i++)
    {
        int x = coordinates[i][0] , y = coordinates[i][1];
        if(dy * (x - x0) != dx * (y - y0))
            return false;
    }
    return true;
}

int main()
{
    vector <vector <int> > coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
    cout << (checkStraightLine(coordinates) ? "true\n" : "false\n");
}

자바 프로그램

class check_straight_line
{
    public static void main(String args[])
    {
        int[][] coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
        System.out.println(checkStraightLine(coordinates) ? "true" : "false");
    }

    static boolean checkStraightLine(int[][] coordinates)
    {
        if(coordinates.length == 2)
            return true;

        int x0 = coordinates[0][0] , x1 = coordinates[1][0];
        int y0 = coordinates[0][1] , y1 = coordinates[1][1];

        int dx = x1 - x0 , dy = y1 - y0;
        for(int i = 2 ; i < coordinates.length ; i++)
        {
            int x = coordinates[i][0] , y = coordinates[i][1];
            if(dy * (x - x0) != dx * (y - y0))
                return false;
        }
        return true;
    }
}
true

직선 Leetcode 솔루션인지 확인의 복잡성 분석

시간 복잡성

의 위에) 여기서 N = 배열의 포인트 수입니다. 어레이의 단일 패스를 수행하고 그 안에서 수행되는 모든 작업에는 일정한 시간이 걸립니다.

공간 복잡성

O (1) 일정한 메모리 공간 만 사용하기 때문입니다.

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