Վավեր Բումերանգի Leetcode լուծում


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

Խնդիրի հայտարարություն

Այս խնդրում մեզ տրվում է XY 2-D ինքնաթիռի երեք կետերի հավաքածու: Մենք պետք է վերադառնանք ՝ նրանք բումերանգ են կազմում, թե ոչ, այսինքն ՝ դրանք երեքն են հստակ միավորներ և արա Նշում ուղիղ գիծ են կազմում:

Օրինակ

Points = {{1 , 2} , {2 , 6} , {1 , 2}}
false
Points = {{1 , 1} , {2 , 3} , {6 , 7}}
true

Առաջին մուտքագրումը ունի 3 նույնից երկու նույն կետ, ուստի այն վավեր բումերանգ չէ, և մենք կեղծ ենք տպում: Երկրորդ թեստը ունի 3 հստակ կետեր, որոնք ուղիղ գիծ չեն կազմում, և մենք տպում ենք ճիշտ:

Վավեր Բումերանգի Leetcode լուծում

Մոտեցում (թեքության թեստ)

Խնդրի մեջ Ստուգեք, արդյոք դա ուղիղ գիծ է, մենք իմացանք, որ երեք հստակ կետերը գծային են միայն այն դեպքում, եթե յուրաքանչյուր զույգ կետերի կողմից կազմված գծի թեքությունը նույնն է: Այստեղ մենք պետք է ստուգենք.

  • Եթե ​​կետերը հստակ են
  • կետերը ուղիղ գծի վրա չեն

Եթե ​​ցանկացած զույգ միավոր նույնն է, ապա տրված մուտքագրումը կանցնի կոլեկցիոնության թեստ, քանի որ ցանկացած 2 միավոր (կամ մեկ միավոր) միշտ գծային է: Այսպիսով, մենք պարզապես պետք է ստուգենք լանջերի հավասարությունը: Նշենք, որ եթե որևէ երեք կետ, P1, P2 և P3 գծային են, մենք ունենք

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), կամ

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

որտեղ x1, x2, x3, y1, y2, y3 - ը P1, P2 և P3- ի համապատասխան x և t կոորդինատներն են:

Ալգորիթմ

  1. Նախաձեռնեք dx1 = - ի տարբերությունը x- կոորդինատները առաջին երկու կետերի և dy1 = - ի տարբերությունը y- կոորդինատները առաջին երկու կետերի
  2. Նմանապես, պահեք dx2 = տարբերությունը y- կոորդինատները վերջին երկու կետերի և dy2 = - ի տարբերությունը y- կոորդինատները վերջին երկու կետերի
  3. Վերադարձեք, եթե ((dx1 * dy2)! = (Dx2 * dy1)) ()լանջի փորձարկում պայմանը)
  4. Տպեք արդյունքը

Բումերանգի վավեր Leetcode լուծման իրականացում

C ++ ծրագիր

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

bool isBoomerang(vector <vector <int> > &points)
{
    int dx1 = (points[1][0] - points[0][0]);
    int dy1 = (points[1][1] - points[0][1]);
    int dx2 = (points[2][0] - points[1][0]);
    int dy2 = (points[2][1] - points[1][1]);

    return (dx1 * dy2) != (dy1 * dx2);
}

int main()
{
    vector <vector <int> > points = {{1 , 1} , {2 , 3} , {6 , 7}};
    if(isBoomerang(points))
        cout << "true\n";
    else
        cout << "false\n";
    return 0;
}

Java ծրագիր

class valid_boomerang
{
    public static void main(String args[])
    {
        int[][] points = {{1 , 1} , {2 , 3} , {6 , 7}};
        if(isBoomerang(points))
            System.out.println("true");
        else
            System.out.println("false");
    }

    static boolean isBoomerang(int[][] points)
    {
        int dx1 = (points[1][0] - points[0][0]);
        int dy1 = (points[1][1] - points[0][1]);
        int dx2 = (points[2][0] - points[1][0]);
        int dy2 = (points[2][1] - points[1][1]);

        return (dx1 * dy2) != (dy1 * dx2);
    }
}
true

Բումերանգի վավեր Leetcode լուծույթի բարդության վերլուծություն

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

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

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

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