직선 Leetcode 솔루션인지 확인-TutorialCup

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

차례

예

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

true

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

핀

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) 기준 위에서 본 것처럼 교차 제품 검사.

암호알고리즘

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

직선 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) 일정한 메모리 공간 만 사용하기 때문입니다.

예

접근