Бул түз сызык Leetcode чечими экендигин текшериңиз


Кыйынчылык деңгээли жеңил
Көп суралган Palantir Technologies
согуштук тизме Math

Бул маселеде, бизге берилет согуштук тизме упайлар. Бул XY 2-D тегиздигинде жаткан кээ бир чекиттердин х-координаттарынын жана у-координаттарынын тизмесин билдирет. Бул чекиттер түз сызыкты түзүп жаткандыгын текшеришибиз керек. Киргизүүдө кеминде 2 упай бар экендигин жана алардын абсолюттук мааниси 10 ^ 4төн ашпагандыгын эске алыңыз.

мисал

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

түшүндүрүү Төмөнкү диаграмма бардык чекиттердин коллинеар экендигин тастыктайт.

Бул түз сызык Leetcode чечими экендигин текшериңиз

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

түшүндүрүү: Эки туташкан чекит ар дайым түз сызыкты түзөт.

жакындоо

Эгерде берилген тизмеде эки гана чекит болсо, анда алар ар дайым түз сызыкты түзүп, натыйжасы чын болоорун байкоо оңой. Бирок, үч пункт бар болсо, алардын бардыгы коллинеардык мүнөздө болушу мүмкүн. Ошентип, биз каалаган эки чекитти оңдой алабыз, алардан өткөн сызыкты түзүп, калган чекиттердин бардыгы бир эле сызыкта жаткандыгын текшере алабыз. Математикалык жактан, муну текшерүү аркылуу жасоого болот эңкейиш каалаган эки чекиттин ортосунда түзүлгөн сызыктын. Мисалы, үч упай бар экендигин карап көрөлү: P1 = (x1, y1) , P2 = (x2, y2) жана P3 = (x3, y3).

Эми, P1 жана P2 аркылуу өтчү сызыкты түзөлү. Бул сызыктын жантайышы төмөнкүдөй болот:

эңкейиш = (y2 - y1) / (x2 - x1)

P3 P1 жана P2 менен коллинеар болушун камсыз кылуу үчүн, биринчи P2 жана P3 чекиттери түзгөн сызыктын жантаймагын табалы. Ушул,

эңкейиш(P2 жана P3) = (y3 - y2) / (x3 - x2)

Эми упайлар коллинеардык мүнөздө гана болот, эгерде: P1 жана P2 түзгөн сызыктын кыйышы = P2 жана P3 түзгөн сызыктын жантаюу.

Демек, P1, P2 жана P3 коллинеар болсо, бизде бар

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), же

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

Демек, биз P1 жана P2 деп эки чекитти оңдой алабыз жана ар бирине i Кирүү тизмесинде> 2 болсо, анда биз текшере алабыз эңкейиш (1, 2) болуп барабар Жантайыш (1, i) боюнча жогоруда биз көргөндөй кайчылаш продукт текшерүү.

Algorithm

  1. Буль функциясын колдонобуз checkStraightLine () ага берилген упайлар массивинин түз сызыкты түзгөндүгүн кайтаруу
  2. Эгерде массивде бар болсо 2 упайлар:
    • return true
  3. Initialize x0 биринчи чекиттин х-координаты жана y0 экинчи чекиттин у-координаты катары. Ошо сыяктуу эле, (x1, y1) экинчи чекиттин координаттары үчүн
  4. Продукцияны текшерүү үчүн алардын айырмачылыгы керек болгондуктан, алардын айырмачылыктарын төмөнкүдөй сактаңыз:
    • dx = x1 - x0
    • dy = y1 - y0
  5. Эми экинчи пункттан кийинки массивдеги ар бир чекит үчүн:
    1. Бул чекиттин x жана y координаттарын өзгөрмөлөрдө сактаңыз x жана y
    2. Эми, алгачкы эки чекиттин жантайышы менен ушул жана биринчи чекиттин жантайышы бирдей экендигин текшеребиз:
      • If dy * (x - x0) is жок барабар dx * (y - y0)
        • return false
  6. Чындыкты кайтаруу
  7. Жыйынтыгын басып чыгарыңыз

Эгерде бул Leetcode Түз Чечими болсо, Текшерүүнү Ишке ашыруу

C ++ программасы

#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 программасы

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

Текшерүүнүн татаалдыгын анализдөө, эгер бул түз сызык Leetcode чечими болсо

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

O (N) мында N = массивдеги упайлардын саны. Биз массивдин бир өтүүсүн жасайбыз жана андагы бардык операциялар туруктуу убакытты талап кылат.

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

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