โซลูชัน Boomerang Leetcode ที่ถูกต้อง  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน Google
อัลกอริทึม การเข้ารหัส สัมภาษณ์ สัมภาษณ์เตรียม LeetCode LeetCodeSolutions คณิตศาสตร์

คำชี้แจงปัญหา  

ในปัญหานี้เราได้รับชุดของจุดสามจุดในระนาบ XY 2-D เราจำเป็นต้องกลับมาไม่ว่าจะเป็นบูมเมอแรงหรือไม่นั่นคือไม่ว่าจะเป็นสามอันก็ตาม แตกต่าง จุดและทำ ไม่ สร้างเส้นตรง

ตัวอย่าง

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

อินพุตแรกมีจุดสองจุดที่เหมือนกันจาก 3 ดังนั้นจึงไม่ใช่บูมเมอแรงที่ถูกต้องและเราพิมพ์เท็จ การทดสอบครั้งที่สองมีจุดที่แตกต่างกัน 3 จุดที่ไม่เป็นเส้นตรงและเราพิมพ์จริง

โซลูชัน Boomerang Leetcode ที่ถูกต้อง

แนวทาง (การทดสอบความลาดชัน)  

ในปัญหา ตรวจสอบว่าเป็นเส้นตรงหรือไม่เราได้เรียนรู้ว่าจุดที่แตกต่างกันสามจุดนั้นเป็นเพียงแค่คอลลิเนียร์เท่านั้นหากความชันของเส้นที่เกิดจากจุดทุกคู่เท่ากัน ที่นี่เราต้องตรวจสอบ:

  • หากจุดแตกต่างกัน
  • จุดไม่อยู่บนเส้นตรง

หากคู่ของจุดใด ๆ เหมือนกันอินพุตที่ระบุจะผ่านการทดสอบ collinearity เนื่องจาก 2 จุดใด ๆ (หรือจุดเดียว) เสมอกัน ดังนั้นเราต้องตรวจสอบความเท่าเทียมกันของความลาดชัน โปรดทราบว่าถ้าสามจุดใด ๆ P1, P2 และ P3 เป็น collinear แสดงว่าเรามี

(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. พิมพ์ผลลัพธ์

การใช้งานโซลูชัน 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;
}

โปรแกรม 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

การวิเคราะห์ความซับซ้อนของโซลูชัน Boomerang Leetcode ที่ถูกต้อง

ความซับซ้อนของเวลา

O (1) ในขณะที่เราดำเนินการเป็นจำนวนคงที่

ความซับซ้อนของพื้นที่

O (1) เมื่อเราใช้พื้นที่หน่วยความจำคงที่