বৈধ বুমেরাং লেটকোড সমাধান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় গুগল
ম্যাথ

সমস্যা বিবৃতি

এই সমস্যায়, আমাদের এক্সওয়াই 2-ডি বিমানের তিনটি পয়েন্টের একটি সেট দেওয়া হয়। সেগুলি বুমেরাং গঠন করুক বা না করুক আমাদের ফিরে আসতে হবে, তারা তিনজনই কিনা স্বতন্ত্র পয়েন্ট এবং কি না একটি সরল রেখা গঠন।

উদাহরণ

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

প্রথম ইনপুটটিতে 3 টির মধ্যে দুটি একই পয়েন্ট রয়েছে, সুতরাং এটি কোনও বৈধ বুমেরাং নয় এবং আমরা মিথ্যা মুদ্রণ করি। দ্বিতীয় পরীক্ষায় 3 টি স্বতন্ত্র পয়েন্ট রয়েছে যা একটি সরল রেখা তৈরি করে না এবং আমরা সত্য মুদ্রণ করি।

বৈধ বুমেরাং লেটকোড সমাধান

পদ্ধতির (opeাল পরীক্ষা)

সমস্যায় এটি সরলরেখা কিনা তা পরীক্ষা করে দেখুন, আমরা শিখেছি যে তিনটি স্বতন্ত্র বিন্দু কেবল কল্লিনিয়ার হয় যদি প্রতিটি জোড় পয়েন্ট দ্বারা গঠিত রেখার opeাল একই হয়। এখানে, আমাদের যাচাই করা দরকার:

  • পয়েন্ট পৃথক হলে
  • পয়েন্টগুলি একটি সরলরেখায় থাকে না

যে কোনও পয়েন্টের জুড়ি যদি একই হয় তবে প্রদত্ত ইনপুটটি কলিনারিটি পরীক্ষায় উত্তীর্ণ হবে, যেহেতু যে কোনও 2 পয়েন্ট (বা একক পয়েন্ট) সর্বদা কোলাইনারি থাকে। সুতরাং, আমাদের কেবল opালু সমতার জন্য পরীক্ষা করা দরকার। নোট করুন যে কোনও তিনটি পয়েন্ট, পি 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 = এর পার্থক্য শুরু করুন এক্স-স্থানাঙ্ক প্রথম দুটি পয়েন্ট এবং dy1 = এর পার্থক্য y- স্থানাঙ্ক প্রথম দুটি পয়েন্ট
  2. একইভাবে, ডিএক্স 2 = এর পার্থক্য সঞ্চয় করুন 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

বৈধ বুমেরাং লেটকোড সমাধানের জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (1) আমরা ক্রমাগত অপারেশন হিসাবে।

স্থান জটিলতা

ও (1) যেমন আমরা ধ্রুবক মেমরি স্পেস ব্যবহার করি।