చెల్లుబాటు అయ్యే బూమరాంగ్ లీట్‌కోడ్ పరిష్కారం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది గూగుల్
మఠం

సమస్యల నివేదిక

ఈ సమస్యలో, మాకు XY 2-D విమానంలో మూడు పాయింట్ల సమితి ఇవ్వబడుతుంది. అవి బూమేరాంగ్‌ను ఏర్పరుస్తాయో లేదో మనం తిరిగి రావాలి, అంటే అవి ఏమైనా ఉన్నాయా విభిన్న పాయింట్లు మరియు చేయండి కాదు సరళ రేఖను ఏర్పరుస్తుంది.

ఉదాహరణ

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

మొదటి ఇన్పుట్ 3 లో రెండు ఒకే పాయింట్లను కలిగి ఉంది, కాబట్టి ఇది చెల్లుబాటు అయ్యే బూమేరాంగ్ కాదు మరియు మేము తప్పుడు ముద్రించాము. రెండవ పరీక్షలో 3 విభిన్న పాయింట్లు ఉన్నాయి, అవి సరళ రేఖను ఏర్పరచవు మరియు మేము ఒప్పును ముద్రించాము.

చెల్లుబాటు అయ్యే బూమరాంగ్ లీట్‌కోడ్ పరిష్కారం

అప్రోచ్ (వాలు పరీక్ష)

సమస్యలో ఇది స్ట్రెయిట్ లైన్ కాదా అని తనిఖీ చేయండి, ప్రతి జత బిందువులచే ఏర్పడిన రేఖ యొక్క వాలు ఒకేలా ఉంటే మూడు విభిన్న బిందువులు మాత్రమే కోలినియర్ అని మేము తెలుసుకున్నాము. ఇక్కడ, మేము తనిఖీ చేయాలి:

  • పాయింట్లు భిన్నంగా ఉంటే
  • పాయింట్లు సరళ రేఖలో ఉండవు

ఏదైనా జత పాయింట్లు ఒకేలా ఉంటే, ఇచ్చిన ఇన్పుట్ కోలినియారిటీ పరీక్షలో ఉత్తీర్ణత సాధిస్తుంది, ఎందుకంటే ఏదైనా 2 పాయింట్లు (లేదా ఒకే పాయింట్) ఎల్లప్పుడూ కొల్లినియర్. కాబట్టి, మేము వాలుల సమానత్వం కోసం తనిఖీ చేయాలి. ఏదైనా మూడు పాయింట్లు, పి 1, పి 2 మరియు పి 3 కొల్లినియర్ అయితే, మన దగ్గర ఉన్నాయని గమనించండి

(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. ఫలితాన్ని ముద్రించండి

చెల్లుబాటు అయ్యే బూమేరాంగ్ లీట్‌కోడ్ పరిష్కారం అమలు

సి ++ ప్రోగ్రామ్

#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 (1) మేము స్థిరమైన సంఖ్యలో కార్యకలాపాలను నిర్వహిస్తున్నప్పుడు.

స్థల సంక్లిష్టత

O (1) మేము స్థిరమైన మెమరీ స్థలాన్ని ఉపయోగిస్తున్నప్పుడు.