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


कठिनाई स्तर आसान
में अक्सर पूछा गूगल
मठ

समस्या का विवरण

इस समस्या में, हमें 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 इसी x और t निर्देशांक P1, P2 और P3 के हैं।

कलन विधि

  1. प्रारंभिक dx1 = का अंतर एक्स-निर्देशांक पहले दो बिंदुओं और dy1 = का अंतर y- निर्देशांकों पहले दो अंक के
  2. इसी तरह, dx2 = का अंतर स्टोर करें y- निर्देशांकों पिछले दो बिंदुओं और dy2 = का अंतर y- निर्देशांकों अंतिम दो अंक के
  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;
}

जावा प्रोग्राम

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

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

समय जटिलता

ओ (1) जैसा कि हम लगातार संचालन करते हैं।

अंतरिक्ष की जटिलता

ओ (1) जैसा कि हम निरंतर मेमोरी स्पेस का उपयोग करते हैं।