Бумерангтың жарамды кодының шешімі  


Күрделілік дәрежесі оңай
Жиі кіреді Google
алгоритмдер кодтау сұхбат сұхбат дайындау LeetCode LeetCodeSolutions математика

Проблемалық мәлімдеме  

Бұл есепте бізге XY 2-D жазықтығында үш нүктенің жиынтығы берілген. Біз олар бумеранг құра ма, жоқ па, әйтпесе олардың үшеуі бола ма, қайтуымыз керек әр түрлі нүктелер және істеу емес түзу сызық құрайды.

мысал

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

Бірінші кірістің 3-тен екі бірдей нүктесі бар, сондықтан ол жарамды бумеранг емес және біз жалған басамыз. Екінші тестте түзу түзілмейтін 3 нақты нүкте бар және біз шындықты шығарамыз.

Бумерангтың жарамды кодының шешімітүйреуіш

Тәсіл (көлбеу сынау)  

Мәселеде Бұл түзу сызық екенін тексеріңіз, біз әр үш нүкте құрған түзудің көлбеуі бірдей болған жағдайда ғана үш нақты нүкте коллинеарлы болатынын білдік. Мұнда тексеру қажет:

  • Егер нүктелер бөлек болса
  • нүктелер түзудің бойында жатпайды

Егер кез-келген нүкте жұбы бірдей болса, онда берілген кіріс коллинеарлықты тексеруден өтеді, өйткені кез-келген 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 - P1, P2 және P3 сәйкес x және t координаттары.

Алгоритм

  1. Dx1 инициализациясы = айырмашылық х-координаталар алғашқы екі нүктенің және dy1 = айырмасы у-координаттары алғашқы екі ұпай
  2. Сол сияқты, dx2 = айырмашылықты сақтаңыз у-координаттары соңғы екі нүктенің және dy2 = айырмасы у-координаттары соңғы екі ұпай
  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

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

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

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

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

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

2