ដំណោះស្រាយមានសុពលភាព Boomerang Leetcode


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន google
គណិតវិទ្យា

សេចក្តីថ្លែងការណ៍បញ្ហា។

នៅក្នុងបញ្ហានេះយើងត្រូវបានគេផ្តល់ឱ្យនូវសំណុំបីចំណុចនៅក្នុងយន្តហោះ XY 2-D ។ យើងត្រូវត្រឡប់ថាតើពួកវាបង្កើតជា boomerang រឺអត់នោះគឺថាតើពួកគេទាំងបីរឺអត់ ផ្សេងគ្នា ចំណុចនិងធ្វើ មិនមាន បង្កើតជាបន្ទាត់ត្រង់។

ឧទាហរណ៍

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

ការបញ្ចូលដំបូងមានពីរចំណុចដូចគ្នាក្នុងចំណោម ៣ ដូច្នេះវាមិនមែនជា boomerang ត្រឹមត្រូវទេហើយយើងបោះពុម្ពមិនពិត។ ការប្រលងលើកទី ២ មាន ៣ ចំនុចផ្សេងគ្នាដែលមិនបង្កើតជាបន្ទាត់ត្រង់ហើយយើងបោះពុម្ភពិត។

ដំណោះស្រាយមានសុពលភាព Boomerang Leetcode

វិធីសាស្រ្ត (ការធ្វើតេស្តជម្រាល)

នៅក្នុងបញ្ហា ពិនិត្យមើលថាតើវាជាបន្ទាត់ត្រង់យើងបានដឹងថាចំនុច ៣ ផ្សេងគ្នាគឺមានតែបន្ទាត់កាត់ទេប្រសិនបើជម្រាលនៃខ្សែដែលបង្កើតឡើងដោយរាល់ចំនុចនីមួយៗគឺដូចគ្នា។ នៅទីនេះយើងត្រូវពិនិត្យ:

  • ប្រសិនបើពិន្ទុខុសគ្នា
  • ចំនុចទាំងនោះមិនស្ថិតនៅលើបន្ទាត់ត្រង់ទេ

ប្រសិនបើគូនៃពិន្ទុគឺដូចគ្នាបន្ទាប់មកធាតុបញ្ចូលដែលបានផ្តល់ឱ្យនឹងឆ្លងកាត់ការធ្វើតេស្តពណ៌ដែលជាចំណុចណាមួយ (ឬចំណុចតែមួយ) តែងតែជាជួរ។ ដូច្នេះយើងគ្រាន់តែត្រូវការពិនិត្យមើលភាពស្មើគ្នានៃជម្រាល។ ចំណាំថាប្រសិនបើមានបីចំណុច P2, P1 និង P2 គឺជាបន្ទាត់កាត់នោះយើងមាន

(y2 - y1): (x2 - x1) :: (y3 - y2): (x៣ - x២) ឬ

(y2 - y1) * (x៣ - x២) = (x២ - x១) * (y៣ - y២)

កន្លែង x1, x2, x3, y1, y2, y3 គឺជាកូអរដោនេ x និង t ដែលត្រូវគ្នានៃ P1, P2 និង P3 ។

ក្បួនដោះស្រាយ

  1. ចាប់ផ្តើម dx1 = ភាពខុសគ្នានៃ កូអរដោនេ x នៃពីរចំនុចដំបូងនិងឌី ១ = ភាពខុសគ្នានៃ កូអរដោនេ y នៃពីរចំណុចដំបូង
  2. ស្រដៀងគ្នានេះដែរទុក dx2 = ភាពខុសគ្នានៃ កូអរដោនេ y នៃពីរចំនុចចុងក្រោយនិងឌី ២ = ភាពខុសគ្នានៃ កូអរដោនេ y ពីរចំណុចចុងក្រោយ
  3. ត្រឡប់ប្រសិនបើ ((dx1 * dy2)! = (dx2 * dy1)) (ការធ្វើតេស្តជម្រាល លក្ខខណ្ឌ)
  4. បោះពុម្ពលទ្ធផល

ការអនុវត្តដំណោះស្រាយដែលមានសុពលភាព Boomerang 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;
}

កម្មវិធីចាវ៉ា

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

ការវិភាគស្មុគស្មាញនៃដំណោះស្រាយសុលបូររុមឡឺរ

ស្មុគស្មាញពេលវេលា

ឱ (១) ដូចដែលយើងអនុវត្តចំនួនថេរនៃប្រតិបត្តិការ។

ភាពស្មុគស្មាញនៃលំហ

ឱ (១) ដូចដែលយើងប្រើទំហំចងចាំថេរ។