Ստուգեք, արդյոք դա ուղիղ գծի Leetcode լուծում է


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Պալանտիր տեխնոլոգիաներ
Դասավորություն Մաթեմատիկա

Այս խնդրում մեզ տրվում է ան դասավորություն միավորների Սա ներկայացնում է 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. initialize x0 որպես առաջին կետի x- կոորդինատ և y0 որպես երկրորդ կետի y- կոորդինատ: Նմանապես, (x1, y1) երկրորդ կետի կոորդինատների համար
  4. Քանի որ մեզ անհրաժեշտ է դրանց տարբերությունը արտադրանքների ստուգման համար, պահպանեք դրանց տարբերությունները ՝
    • dx = x1 - x0
    • dy = y1 - y0
  5. Այժմ երկրորդ կետից հետո զանգվածի յուրաքանչյուր կետի համար.
    1. Այս կետի x և y կոորդինատները պահեք փոփոխականների մեջ x և y
    2. Այժմ մենք ստուգում ենք, թե արդյոք առաջին երկու կետերի լանջերը և այս և առաջին կետի թեքությունը նույնն են.
      • If dy * (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");
}

Java ծրագիր

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 լուծում է, բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ) որտեղ N = զանգվածում կետերի քանակը: Մենք կատարում ենք զանգվածի մեկ փոխանցում և դրանում կատարված բոլոր գործողությունները տևում են անընդհատ ժամանակ:

Տիեզերական բարդություն

Ո (1) քանի որ մենք օգտագործում ենք միայն մշտական ​​հիշողության տարածություն: