ໂຊລູຊັ່ນ Boomerang Leetcode ທີ່ຖືກຕ້ອງ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ກູໂກ
ຂັ້ນຕອນວິທີ ລະຫັດ ການສໍາພາດ ການສໍາພາດກ່ອນ LeetCode LeetCodeSolutions ຄະນິດສາດ

ຖະແຫຼງການບັນຫາ  

ໃນບັນຫານີ້, ພວກເຮົາໄດ້ຮັບການ ກຳ ນົດໄວ້ສາມຈຸດໃນຍົນ XY 2-D. ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ກັບຄືນມາບໍ່ວ່າພວກມັນຈະເປັນຮູບແບບບູລົມຫລືບໍ່ກໍ່ຕາມ, ນັ້ນແມ່ນວ່າພວກເຂົາແມ່ນສາມຄົນ ແຕກຕ່າງກັນ ຈຸດແລະເຮັດ ບໍ່ ປະກອບເປັນເສັ້ນຊື່.

ຍົກຕົວຢ່າງ

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

ການປ້ອນຂໍ້ມູນຄັ້ງ ທຳ ອິດມີສອງຈຸດດຽວກັນຈາກ 3, ດັ່ງນັ້ນມັນບໍ່ແມ່ນ boomerang ທີ່ຖືກຕ້ອງແລະພວກເຮົາພິມຜິດ. ການທົດສອບຄັ້ງທີສອງມີ 3 ຈຸດທີ່ແຕກຕ່າງກັນທີ່ບໍ່ເປັນເສັ້ນຊື່ແລະພວກເຮົາພິມເປັນຄວາມຈິງ.

ໂຊລູຊັ່ນ Boomerang Leetcode ທີ່ຖືກຕ້ອງPin

ວິທີການ (ການທົດສອບເປີ້ນພູ)  

ໃນບັນຫາ ກວດເບິ່ງວ່າມັນແມ່ນເສັ້ນຊື່, ພວກເຮົາໄດ້ຮຽນຮູ້ວ່າສາມຈຸດທີ່ແຕກຕ່າງກັນແມ່ນມີພຽງເສັ້ນສາຍເທົ່ານັ້ນຖ້າວ່າເປີ້ນພູຂອງເສັ້ນທີ່ຖືກສ້າງຕັ້ງຂື້ນໂດຍທຸກໆຈຸດຂອງຈຸດແມ່ນຄືກັນ. ນີ້, ພວກເຮົາຕ້ອງການກວດສອບ:

  • ຖ້າຈຸດແຕກຕ່າງ
  • ຈຸດຕ່າງໆບໍ່ໄດ້ນອນຢູ່ໃນເສັ້ນຊື່

ຖ້າຄູ່ຂອງຈຸດໃດ ໜຶ່ງ ຄືກັນ, ຫຼັງຈາກນັ້ນຈຸດປະກອບທີ່ເຂົ້າມາຈະຜ່ານການທົດສອບ collinearity, ເພາະວ່າ 2 ຈຸດໃດ ໜຶ່ງ (ຫຼືຈຸດດຽວ) ແມ່ນຢູ່ໃນເສັ້ນ colline ສະນັ້ນ, ພວກເຮົາພຽງແຕ່ຕ້ອງການກວດສອບຄວາມເທົ່າທຽມກັນຂອງເປີ້ນພູ. ໃຫ້ສັງເກດວ່າຖ້າມີສາມຈຸດ, 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) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່.

2