Валидно решение на бумеранг с Leetcode


Ниво на трудност Лесно
Често задавани в Google
Математически

Декларация за проблема

В този проблем ни е даден набор от три точки в XY 2-D равнина. Трябва да се върнем независимо дали образуват бумеранг или не, т.е. дали са три отчетлив точки и направете не образуват права линия.

Пример

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

Първият вход има две същите точки от 3, така че не е валиден бумеранг и отпечатваме false. Вторият тест има 3 различни точки, които не образуват права линия и ние отпечатваме true.

Валидно решение на бумеранг с 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 са съответните координати x и t на P1, P2 и P3.

алгоритъм

  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

Сложност във времето

O (1) тъй като извършваме постоянен брой операции.

Космическа сложност

O (1) тъй като използваме постоянно пространство в паметта.