Жарактуу Бумеранг Leetcode чечими  


Кыйынчылык деңгээли жеңил
Көп суралган Гугл
Алгоритмы коддоо интервью интервью даярдоо LeetCode LeetCodeSolutions Math

Маселени билдирүү  

Бул маселеде бизге 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 координаттары.

Algorithm

  1. Dx1 инициализациясы = айырмасы х-координаттары алгачкы эки чекиттин жана dy1 = айырмасы у координаттары биринчи эки пункт
  2. Ошо сыяктуу эле, dx2 дүкөнү = айырмасы у координаттары акыркы эки чекиттин жана dy2 = айырмасы у координаттары акыркы эки пункттун
  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 чечиминин татаалдыгын талдоо

Убакыт татаалдыгы

O (1) биз тынымсыз бир катар операцияларды жасайбыз.

Космостун татаалдыгы

O (1) биз туруктуу эс мейкиндигин колдонуп жатканда.