वैध बुमेरांग लेटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ गुगल
गणित

समस्या वक्तव्य

यस समस्यामा हामीलाई XY २-D प्लेनमा तीन पोइन्टको सेट दिइन्छ। हामीले फर्कनु पर्छ तिनीहरू बुूमरा form बनाउँछन् वा गर्दैनन्, त्यो हो कि तिनीहरू कुनै पनि तीन हुन् भिन्न पोइन्ट्स र गर्नुहोस् छैन एक सीधा रेखा बनाउनुहोस्।

उदाहरणका

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

पहिलो इनपुटमा of मध्ये दुई समान बिन्दुहरू छन्, त्यसैले यो मान्य बुमेरांग होइन र हामी गलत प्रिन्ट गर्दछौं। दोस्रो परिक्षणमा distin भिन्न बिन्दु छन् जुन एक सीधा रेखा हुँदैन र हामी सहि प्रिन्ट गर्दछौं।

वैध बुमेरांग लेटकोड समाधान

दृष्टिकोण (स्लोप टेस्ट)

समस्यामा यदि यो सीधा रेखा हो भने जाँच गर्नुहोस्, हामीले सिक्यौं कि तीन भिन्न पोइन्टहरू मात्र लाइनर हुन्छ यदि रेखाको ढलान प्रत्येक जोडी पोइन्टहरूको गठन समान हुन्छ। यहाँ, हामीले जाँच गर्नु पर्छ:

  • यदि बिन्दु फरक छन्
  • पोइन्टहरू सीधा रेखामा हुँदैन

यदि कुनै पनि पोइन्टको जोडी उस्तै हो, भने दिइएका इनपुटले collinearity टेस्ट उत्तीर्ण गर्दछ, किनकि कुनै पनि २ पोइन्ट (वा एकल बिन्दु) सँधै लाइनर हुन्छ। त्यसोभए, हामीले स्लोपहरूको समानता जाँच गर्न आवश्यक छ। नोट गर्नुहोस् कि यदि कुनै पनि तीन पोइन्टहरू, P2, P1 र P2 collinear छन्, हामीसँग छ

(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 = फरकको सुरूवात गर्नुहोस् x- निर्देशांक पहिलो दुई पोइन्ट र dy1 = को फरक y- निर्देशांक पहिलो दुई पोइन्टको
  2. समान रूपमा, dx2 = भिन्नता भण्डार गर्नुहोस् y- निर्देशांक अन्तिम दुई पोइन्ट र dy2 = को भिन्नता y- निर्देशांक अन्तिम दुई बिन्दुहरूको
  3. फिर्ती गर्नुहोस् ((dx1 * dy2)! = (Dx2 * dy1)) (स्लोप परीक्षण सर्त)
  4. परिणाम प्रिन्ट गर्नुहोस्

वैध बुमेरांग लेटकोड समाधानको कार्यान्वयन

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

वैध बुमरैंग लीटकोड समाधानको जटिलता विश्लेषण

समय जटिलता

O (१) जब हामी लगातार अपरेशनहरू प्रदर्शन गर्दछौं।

ठाउँ जटिलता

O (१) जस्तो कि हामी स्थिर मेमोरी स्पेस प्रयोग गर्छौं।