സാധുവായ ബൂമറാങ് ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഗൂഗിൾ
മഠം

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ, ഒരു എക്‌സ്‌വൈ 2-ഡി വിമാനത്തിൽ ഞങ്ങൾക്ക് മൂന്ന് പോയിന്റുകളുടെ ഒരു കൂട്ടം നൽകിയിരിക്കുന്നു. അവ ഒരു ബൂമറാംഗ് ഉണ്ടാക്കുന്നുണ്ടോ ഇല്ലയോ എന്ന് ഞങ്ങൾ മടങ്ങേണ്ടതുണ്ട്, അതായത് അവ ഏതെങ്കിലും മൂന്ന് ആണോ എന്ന് വ്യത്യസ്തരായ പോയിന്റുകൾ ചെയ്യുക അല്ല ഒരു നേർരേഖ സൃഷ്ടിക്കുക.

ഉദാഹരണം

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) ഞങ്ങൾ സ്ഥിരമായ മെമ്മറി ഇടം ഉപയോഗിക്കുന്നതിനാൽ.