حل Boomerang Leetcode صالح


مستوى الصعوبة سهل
كثيرا ما يطلب في جوجل
الرياضيات

المشكلة بيان

في هذه المسألة ، لدينا مجموعة من ثلاث نقاط في المستوى XY 2-D. نحتاج إلى العودة سواء كانوا يشكلون ارتدادًا أم لا ، أي ما إذا كانوا ثلاثة خامد نقاط وتفعل ليس تشكيل خط مستقيم.

مثال

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

يحتوي الإدخال الأول على نقطتين متشابهتين من أصل 3 ، لذا فهو ليس بوميرانج صالحًا ونطبع خطأ. الاختبار الثاني له 3 نقاط مميزة لا تشكل خطاً مستقيماً ونطبع صحيحاً.

حل Boomerang Leetcode صالح

النهج (اختبار المنحدر)

في المشكلة تحقق مما إذا كان خطًا مستقيمًا، لقد تعلمنا أن ثلاث نقاط مميزة تكون على خط واحد فقط إذا كان ميل الخط الذي يتكون من كل زوج من النقاط هو نفسه. هنا ، نحتاج إلى التحقق من:

  • إذا كانت النقاط متميزة
  • النقاط لا تقع على خط مستقيم

إذا كان أي زوج من النقاط هو نفسه ، فسيمتاز الإدخال المحدد باختبار العلاقة الخطية المتداخلة ، لأن أي نقطتين (أو نقطة واحدة) تكون دائمًا على علاقة خطية. لذلك ، نحتاج فقط إلى التحقق من تساوي المنحدرات. لاحظ أنه إذا كانت هناك ثلاث نقاط ، P2 و P1 و P2 على خط واحد ، فلدينا

(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 = فرق إحداثيات ص من أول نقطتين
  2. وبالمثل ، قم بتخزين dx2 = فرق إحداثيات ص من النقطتين الأخيرتين و dy2 = فرق إحداثيات ص من النقطتين الأخيرتين
  3. ارجع إذا ((dx1 * dy2)! = (dx2 * dy1)) (اختبار المنحدر حالة)
  4. اطبع النتيجة

تنفيذ حل Boomerang 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

تحليل التعقيد لحل Boomerang Leetcode الصالح

تعقيد الوقت

يا (1) لأننا نجري عددًا ثابتًا من العمليات.

تعقيد الفضاء

يا (1) حيث نستخدم مساحة ذاكرة ثابتة.