Düz Xətti Leetcode Həlli olub olmadığını yoxlayın

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

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bu problemdə bizə bir array xal. Bu, XY 2-D müstəvisində yerləşən bəzi nöqtələrin x koordinatları və y koordinatlarının siyahısını əks etdirir. Bu nöqtələrin düz bir xətt təşkil etdiyini yoxlamaq lazımdır. Girişdə ən azı 2 nöqtə olacağını və mütləq dəyərlərinin 10 ^ 4-dən çox olmayacağını unutmayın.

misal

Co-ordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}}
true

Izahat Aşağıdakı diaqram bütün nöqtələrin kollinear olduğunu təsdiqləyir.

Düz Xətti Leetcode Həlli olub olmadığını yoxlayınPin

Co-ordinates = {{1 , 2} , {3 , 4}}
true

Izahat: İki bağlı nöqtə həmişə düz bir xətt təşkil edir.

Yanaşma

Verilən siyahıda yalnız iki nöqtə varsa, həmişə düz bir xətt meydana gətirəcəklərini və nəticənin doğru olacağını müşahidə etmək asandır. Bununla birlikdə, üç nöqtə varsa, hamısı kollinear ola bilər və ya olmaya bilər. Beləliklə, istənilən iki nöqtəni düzəldə bilərik, onların arasından keçən bir xətt düzəldə bilərik və digər nöqtələrin hamısının eyni xəttdə yerləşdiyini yoxlaya bilərik. Riyazi olaraq, bu yoxlanılaraq edilə bilər yamac hər hansı iki nöqtə arasında əmələ gələn xəttin. Məsələn, üç nöqtəmiz olduğunu düşünək: P1 = (x1, y1) , P2 = (x2, y2) və P3 = (x3, y3).

İndi P1 və P2-dən keçən bir xətt quraq. Bu xəttin yamacı belə olacaq:

Yamaç = (y2 - y1) / (x2 - x1)

P3-ün P1 və P2 ilə kollinear olmasını təmin etmək üçün əvvəlcə P2 və P3 nöqtələrinin əmələ gətirdiyi xəttin yamacını tapaq. Yəni,

Yamaç(P2 və P3) = (y3 - y2) / (x3 - x2)

İndi nöqtələr yalnız bir-birinə bərabərdir və yalnız: P1 və P2-nin əmələ gətirdiyi xəttin yamacı = P2 və P3-in əmələ gətirdiyi xəttin yamacı.

Buna görə, P1, P2 və P3 kollinearsa, bizdə var

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

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

Bu səbəbdən, P1 və P2 deyən və hər biri üçün iki nöqtəni düzəldə bilərik i Giriş siyahısında> 2, olub olmadığını yoxlaya bilərik yamac (1, 2) bərabərdir Yamac (1, i) by yuxarıda gördüyümüz kimi məhsullar arası yoxlama.

Alqoritm

  1. Bir boole funksiyasından istifadə edirik checkStraightLine () ona ötürülən nöqtələrin bir düz xətt təşkil edib etmədiyini qaytarmaq
  2. Dizidə yalnız varsa 2 bal:
    • doğru qayıt
  3. Initialize x0 birinci nöqtənin x koordinatı və y0 ikinci nöqtənin y koordinatı olaraq. Oxşar, (x1, y1) ikinci nöqtənin koordinatları üçün
  4. Məhsullar arası yoxlama üçün onların fərqinə ehtiyacımız olduğundan, fərqlərini aşağıdakı kimi saxlayın:
    • dx = x1 - x0
    • dy = y1 - y0
  5. İndi ikinci nöqtədən sonra massivdəki hər nöqtə üçün:
    1. Bu nöqtənin x və y koordinatlarını dəyişənlərdə saxlayın xy
    2. İndi ilk iki nöqtənin yamacları ilə bu və ilk nöqtənin meylinin eyni olub olmadığını yoxlayırıq:
      • If dy * (x - x0) is yox bərabərdir dx * (y - y0)
        • yalan qayıt
  6. Doğru qayıdın
  7. Nəticəni çap edin

Düz Xətti Leetcode Həlli Olduğunu Yoxlamanın Tətbiqi

C ++ Proqramı

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

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

Düz Xətt Leetcode Həlli Olduğunu Yoxlamanın Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N) burada N = massivdəki nöqtələrin sayı. Dizinin tək keçidini edirik və bu yerdə həyata keçirilən bütün əməliyyatlar daimi vaxt tələb edir.

Kosmik Mürəkkəblik

O (1) yalnız daimi yaddaş boşluğundan istifadə etdiyimiz üçün.

Crack Sistemi Dizayn Müsahibələri
Translate »
1