Valid Bumeranq Leetcode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur google
alqoritmlər kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions RiyaziyyatBaxılıb 22

Problem bəyanat

Bu problemdə bizə XY 2-D müstəvisində üç nöqtə toplusu verilir. Bir bumeranq qurub-yaratmadıqlarına, yəni hər üçü olmasına baxmayaraq qayıtmalıyıq fərqli xal və et yox düz bir xətt təşkil edir.

misal

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

İlk giriş 3-dən iki eyni nöqtəyə malikdir, buna görə də etibarlı bir bumeranq deyil və yalan yazırıq. İkinci testdə düz bir xətt meydana gətirməyən 3 fərqli nöqtə var və biz doğru yazırıq.

Valid Bumeranq Leetcode HəlliPin

Yanaşma (Yamac Testi)

Problemdə Düz bir xətt olub olmadığını yoxlayın, üç fərqli nöqtənin yalnız hər cüt cütün əmələ gətirdiyi xəttin meylinin eyni olduğu təqdirdə kollinear olduğunu öyrəndik. Budur, yoxlamaq lazımdır:

  • Xallar fərqlidirsə
  • nöqtələr düz bir xətt üzərində yatmır

Hər hansı bir xal cütü eynidirsə, verilən giriş kollinearlıq sınağından keçəcəkdir, çünki hər hansı 2 nöqtə (və ya tək bir nöqtə) həmişə kollineardır. Beləliklə, yamacların bərabərliyini yoxlamaq lazımdır. Qeyd edək ki, P1, P2 və P3 hər hansı üç nöqtə kollineardırsa, bizdə var

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), və ya

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

burada x1, x2, x3, y1, y2, y3 P1, P2 və P3-ün müvafiq x və t koordinatlarıdır.

Alqoritm

  1. Başlanğıc dx1 = fərq x koordinatları ilk iki nöqtənin və dy1 = fərqi y koordinatları ilk iki xal
  2. Eynilə, mağaza dx2 = fərqi y koordinatları son iki nöqtənin və dy2 = fərqi y koordinatları son iki xal
  3. Geri qayıdın ((dx1 * dy2)! = (Dx2 * dy1)))yamac testi şərt)
  4. Nəticəni çap edin

Valid Bumeranq Leetcode həllinin tətbiqi

C ++ Proqramı

#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 Proqramı

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

Valid Bumeranq Leetcode həllinin mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (1) davamlı sayda əməliyyat həyata keçirdiyimiz üçün.

Kosmik mürəkkəblik

O (1) daimi yaddaş məkanından istifadə etdiyimiz üçün.

Şərh yaz

Translate »
2