בדוק אם מדובר בפתרון Leetcode בקו ישר


רמת קושי קַל
נשאל לעתים קרובות פלנטיר טכנולוגיות
מערך מתמטיקה

בבעיה זו ניתן לנו מערך של נקודות. זה מייצג רשימה של קואורדינטות x ו- y של כמה נקודות הנמצאות במישור XY 2-D. עלינו לבדוק אם נקודות אלו מהוות קו ישר. שימו לב שיהיו לפחות 2 נקודות בקלט והערכים המוחלטים שלהם לא יעלו על 10 ^ 4.

דוגמה

Co-ordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}}
true

הסבר התרשים הבא מאשר כי כל הנקודות הן קולינריות.

בדוק אם מדובר בפתרון Leetcode בקו ישר

Co-ordinates = {{1 , 2} , {3 , 4}}
true

הסבר: שתי נקודות מחוברות יוצרות תמיד קו ישר.

גישה

קל להתבונן שאם יש רק שתי נקודות ברשימה הנתונה אז הן תמיד יהוו קו ישר והתוצאה תהיה נכונה. עם זאת, אם יש שלוש נקודות, כולן עשויות להיות קולינריות או לא. אז נוכל לתקן כל שתי נקודות, ליצור קו העובר דרכן ולבדוק אם כל שאר הנקודות מונחות על אותה קו. מתמטית, ניתן לעשות זאת על ידי סימון ה מדרון של הקו שנוצר בין שתי נקודות כלשהן. לדוגמה, הבה נבחן שיש לנו שלוש נקודות: P1 = (x1, y1) , P2 = (x2, y2) ו- P3 = (x3, y3).

עכשיו, בואו נוצר קו שעובר דרך P1 ו- P2. שיפוע קו זה יהיה:

מדרון = (y2 - y1) / (x2 - x1)

על מנת להבטיח ש- P3 יהיה קוליניארי עם P1 ו- P2, בואו נמצא קודם את שיפוע הקו שנוצר על ידי הנקודות P2 ו- P3. זה,

מדרון(P2 ו- P3) = (y3 - y2) / (x3 - x2)

כעת, הנקודות הן קולינריות בלבד ורק אם: שיפוע קו שנוצר על ידי P1 ו- P2 = שיפוע קו שנוצר על ידי P2 ו- P3.

לכן, אם P1, P2 ו- P3 הם קולינריים, יש לנו

(y2 - y1): (x2 - x1) :: (y3 - y2): (x3 - x2), או

(y2 - y1) * (x3 - x2) = (x2 - x1) * (y3 - y2)

לכן, אנו יכולים לתקן שתי נקודות, למשל P1 ו- P2, ולכל אחת מהן i > 2 ברשימת הקלטים, אנחנו יכולים לבדוק אם שיפוע (1, 2) שווה ל שיפוע (1, i) על ידי בדיקת מוצלבים כפי שראינו לעיל.

אַלגוֹרִיתְם

  1. אנו משתמשים בפונקציה בוליאנית checkStraightLine () כדי להחזיר אם מערך נקודות המועבר אליו יוצר קו ישר
  2. אם למערך יש רק 2 נקודות:
    • לחזור אמית
  3. אתחל x0 כקואורדינטת x של הנקודה הראשונה ו- y0 כקואורדינטת y של הנקודה השנייה. בדומה לכך, (x1, y1) לקואורדינטות של נקודה שנייה
  4. מכיוון שאנו זקוקים להבדל שלהם לבדיקה בין מוצרים, שמור את ההבדלים ביניהם כ:
    • dx = x1 - x0
    • dy = y1 - y0
  5. עכשיו לכל נקודה במערך אחרי הנקודה השנייה:
    1. אחסן קואורדינטות x ו- y של נקודה זו במשתנים x ו y
    2. כעת, אנו בודקים האם שיפוע שתי הנקודות הראשונות ושיפוע נקודה זו ונקודה ראשונה זהים:
      • If dy * (x - x0) is לֹא שווה ל dx * (y - y0)
        • להחזיר כוזב
  6. תחזיר נכון
  7. הדפיס את התוצאה

יישום בדיקה אם מדובר בפתרון קוד ישר של קוד קוד

תוכנית C ++

#include <bits/stdc++.h>
using namespace std;

bool checkStraightLine(vector <vector <int> > &coordinates)
{
    if(coordinates.size() == 2)
        return true;

    int x0 = coordinates[0][0] , x1 = coordinates[1][0];
    int y0 = coordinates[0][1] , y1 = coordinates[1][1];

    int dx = x1 - x0 , dy = y1 - y0;
    for(int i = 2 ; i < coordinates.size() ; i++)
    {
        int x = coordinates[i][0] , y = coordinates[i][1];
        if(dy * (x - x0) != dx * (y - y0))
            return false;
    }
    return true;
}

int main()
{
    vector <vector <int> > coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
    cout << (checkStraightLine(coordinates) ? "true\n" : "false\n");
}

תוכנית Java

class check_straight_line
{
    public static void main(String args[])
    {
        int[][] coordinates = {{1 , 2} , {2 , 3} , {3 , 4} , {4 , 5} , {5 , 6}};
        System.out.println(checkStraightLine(coordinates) ? "true" : "false");
    }

    static boolean checkStraightLine(int[][] coordinates)
    {
        if(coordinates.length == 2)
            return true;

        int x0 = coordinates[0][0] , x1 = coordinates[1][0];
        int y0 = coordinates[0][1] , y1 = coordinates[1][1];

        int dx = x1 - x0 , dy = y1 - y0;
        for(int i = 2 ; i < coordinates.length ; i++)
        {
            int x = coordinates[i][0] , y = coordinates[i][1];
            if(dy * (x - x0) != dx * (y - y0))
                return false;
        }
        return true;
    }
}
true

ניתוח המורכבות של בדיקה האם מדובר בפתרון קוד קוד ישר

מורכבות זמן

עַל) כאשר N = מספר הנקודות במערך. אנו מבצעים מעבר יחיד של המערך וכל הפעולות המבוצעות בו לוקחות זמן קבוע.

מורכבות בחלל

O (1) כיוון שאנחנו משתמשים רק במרחב זיכרון קבוע.