פתרון Leetcode בומרנג תקף


רמת קושי קַל
נשאל לעתים קרובות Google
מתמטיקה

הצהרת בעיה

בבעיה זו, אנו מקבלים סט של שלוש נקודות במישור XY 2-D. עלינו לחזור בין אם הם יוצרים בומרנג ובין אם לאו, כלומר אם מדובר בשלושה מובהק נקודות ולעשות לֹא יוצרים קו ישר.

דוגמה

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

לקלט הראשון יש שתי נקודות זהות מתוך 3, כך שזה לא בומרנג תקף ואנחנו מדפיסים שקר. במבחן השני יש 3 נקודות מובחנות שאינן יוצרות קו ישר ואנחנו מדפיסים נכון.

פתרון 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 = ההבדל של קואורדינטות x של שתי הנקודות הראשונות ו- dy1 = ההפרש של קואורדינטות y של שתי הנקודות הראשונות
  2. באופן דומה, חנות dx2 = ההבדל של קואורדינטות y משתי הנקודות האחרונות ו- dy2 = ההפרש של קואורדינטות y של שתי הנקודות האחרונות
  3. החזר אם ((dx1 * dy2)! = (Dx2 * dy1)) (מבחן השיפוע מַצָב)
  4. הדפיס את התוצאה

יישום פתרון חוקי של בומרנג בומרנג

תוכנית 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;
}

תוכנית Java

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) כאשר אנו משתמשים במרחב זיכרון קבוע.