हे स्ट्रेट लाइन लीटकोड सोल्यूशन आहे का ते तपासा


अडचण पातळी सोपे
वारंवार विचारले पलांटिर टेक्नॉलॉजीज
अरे गणित

या समस्येमध्ये, आम्हाला एक दिले जाते अॅरे गुण. हे XY 2-D विमानात असलेल्या काही बिंदूंच्या एक्स-निर्देशांक आणि y- समन्वयांची यादी दर्शविते. हे बिंदू सरळ रेष आहेत की नाही हे तपासण्याची गरज आहे. लक्षात घ्या की इनपुटमध्ये कमीतकमी 2 गुण असतील आणि त्यांचे परिपूर्ण मूल्ये 10 ^ 4 पेक्षा जास्त होणार नाहीत.

उदाहरण

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

स्पष्टीकरण खालील रेखाचित्र पुष्टी करते की सर्व बिंदू एकसमान आहेत.

हे स्ट्रेट लाइन लीटकोड सोल्यूशन आहे का ते तपासा

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

स्पष्टीकरण: दोन जोडलेले बिंदू नेहमी एक सरळ रेषा तयार करतात.

दृष्टीकोन

हे लक्षात ठेवणे सोपे आहे की दिलेल्या यादीमध्ये केवळ दोन गुण असतील तर ते नेहमी एक सरळ रेषा तयार करतात आणि त्याचा परिणाम सत्य असेल. तथापि, तीन गुण असल्यास ते सर्व कॉलिनार असू शकतात किंवा नसू शकतात. तर, आम्ही कोणतेही दोन बिंदू निश्चित करू शकतो, त्यामधून जात असलेली एक ओळ बनवू शकतो आणि इतर सर्व बिंदू एकाच ओळीवर आहेत काय ते तपासू शकतो. गणिताने हे तपासून करता येते ढाल कोणत्याही दोन बिंदू दरम्यान तयार केलेली रेषा. उदाहरणार्थ, आपल्याकडे तीन मुद्द्यांचा विचार करूयाः पी 1 = (x1, y1) , पी 2 = (x2, y2) आणि पी 3 = (x3, y3).

आता, आपण पी 1 आणि पी 2 मधून जात असलेली एक ओळ बनवू. या ओळीचा उतार खालीलप्रमाणे असेल:

उतार = (y2 - y1) / (x2 - x1)

पी 3 पी 1 आणि पी 2 सह लाइनर आहे याची खात्री करण्यासाठी, प्रथम बिंदू पी 2 आणि पी 3 ने बनलेल्या रेषेचा उतार शोधू. ते आहे,

उतार(पी 2 आणि पी 3) = (y3 - y2) / (x3 - x2)

आता, बिंदू केवळ आणि केवळ कोलिनेर आहेतः पी 1 आणि पी 2 ने बनलेल्या रेषाचा उतार = पी 2 आणि पी 3 ने बनलेल्या रेषाचा उतार.

म्हणून, जर पी 1, पी 2 आणि पी 3 कॉलिनर असतील तर आपल्याकडे आहे

(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. आम्ही बुलियन फंक्शन वापरतो चेकस्ट्राइटलाईन () बिंदूंचा अ‍ॅरे सरळ रेषेत तयार झाला की परत मिळवण्यासाठी
  2. जर अ‍ॅरे फक्त असेल 2 गुण:
    • सत्य परत करा
  3. आरंभ करा x0 पहिल्या बिंदूचे एक्स-समन्वय म्हणून आणि y0 दुसर्‍या बिंदूचे वाय समन्वय म्हणून. त्याचप्रमाणे (x1, y1) दुसर्‍या बिंदूच्या समन्वयासाठी
  4. आम्हाला क्रॉस-प्रॉडक्ट तपासणीसाठी त्यांचा फरक आवश्यक असल्याने, त्यांचे फरक या रुपात संग्रहित करा:
    • dx = x1 - x0
    • dy = y1 - y0
  5. आता दुसर्‍या बिंदूनंतर अ‍ॅरेमधील प्रत्येक बिंदूसाठी:
    1. या बिंदूचे x आणि y निर्देशांक व्हेरिएबल्समध्ये ठेवा x आणि y
    2. आता आपण तपासू की पहिल्या दोन बिंदूंचे उतार आणि याचा उतार आणि पहिला बिंदू समान आहे:
      • If dy * (x - x0) is नाही च्या बरोबरीने dx * (y - y0)
        • खोटे परत
  6. खरे परत
  7. निकाल प्रिंट करा

हे स्ट्रेट लाइन लीटकोड सोल्यूशन असल्यास तपासणीची अंमलबजावणी

सी ++ प्रोग्राम

#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");
}

जावा कार्यक्रम

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

हे स्ट्रेट लाइन लीटकोड सोल्यूशन असल्यास तपासणीचे जटिल विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन) जेथे N = अ‍ॅरे मधील बिंदूंची संख्या. आम्ही अ‍ॅरेचा एकच पास करतो आणि त्यामध्ये केल्या गेलेल्या सर्व ऑपरेशन्समध्ये निरंतर वेळ लागतो.

स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण आपण फक्त मेमरी स्पेस वापरतो.