Бұл түзу сызықтық шешім кодын тексеріңіз


Күрделілік дәрежесі оңай
Жиі кіреді Palantir Technologies
Array математика

Бұл мәселеде бізге ан массив ұпай Бұл XY 2-D жазықтығында жатқан кейбір нүктелердің х-координаттары мен у-координаттарының тізімін білдіреді. Бұл нүктелер түзу сызықты құрайтынын тексеру керек. Кірісте кем дегенде 2 нүкте болатындығын және олардың абсолюттік мәндері 10 ^ 4-тен аспайтынын ескеріңіз.

мысал

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

Түсіндіру Келесі диаграмма барлық нүктелердің коллинеар болғандығын растайды.

Бұл түзу сызықтық шешім кодын тексеріңіз

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) бойынша жоғарыда көрсетілгендей, кросс-өнімдерді тексеру.

Алгоритм

  1. Біз логикалық функцияны қолданамыз checkStraightLine () оған берілген нүктелер массиві түзу түзетіндігін қайтару
  2. Егер массивте тек бар болса 2 ұпайлар:
    • шындыққа оралу
  3. Бастамаңыз x0 бірінші нүктенің х-координаты және y0 екінші нүктенің у-координаты ретінде. Сол сияқты, (x1, y1) екінші нүктенің координаттары үшін
  4. Өнімдерді тексеру үшін олардың айырмашылығы қажет болғандықтан, олардың айырмашылықтарын келесідей сақтаңыз:
    • dx = x1 - x0
    • dy = y1 - y0
  5. Енді екінші нүктеден кейінгі массивтің әр нүктесі үшін:
    1. Осы нүктенің х және у координаттарын айнымалыларда сақтаңыз x және y
    2. Енді алғашқы екі нүктенің көлбеуі мен осы және бірінші нүктенің көлбеуі бірдей екендігін тексереміз:
      • If dy * (x - x0) is емес тең dx * (y - y0)
        • жалған қайтару
  6. Ақиқатқа оралу
  7. Нәтижені басып шығарыңыз

Тік сызықтық шешім кодын тексеруді жүзеге асыру

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

Тексерудің күрделілігін талдау, егер бұл тікелей сызықтық код шешімі болса

Уақыттың күрделілігі

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

Ғарыштың күрделілігі

O (1) өйткені біз тек тұрақты жад кеңістігін қолданамыз.