ສາມວິທີແກ້ໄຂບັນຫາ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ດີຈີ
Array

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

ໃນ” ສາມຄີກົ້ຕໍ່ກັນ” ບັນຫາພວກເຮົາໄດ້ຮັບ array ແລະພວກເຮົາຕ້ອງກວດເບິ່ງວ່າມີສາມຕົວເລກຕໍ່ເນື່ອງໃນແຖວທີ່ມີຢູ່ຫລືບໍ່. ຖ້າມັນມີຢູ່ໃນຕອນນັ້ນພວກເຮົາຕ້ອງກັບຄືນມາເປັນຄວາມຈິງຫຼືອື່ນໆພວກເຮົາຈະກັບຄືນມາບໍ່ຖືກຕ້ອງ.

ຍົກຕົວຢ່າງ

arr = [2,6,4,1]
false

ຄຳ ອະທິບາຍ:

ບໍ່ມີສາມຄີກກັນເລີຍ. ເພາະສະນັ້ນກັບຄືນມາບໍ່ຖືກຕ້ອງ.

arr = [1,2,34,3,4,5,7,23,12]
true

ຄໍາອະທິບາຍ:

ໃນອາເລທີ່ໃຫ້ຖ້າພວກເຮົາກວດເບິ່ງທັງສາມສ່ວນຂອງສ່ວນປະກອບຕິດຕໍ່ກັນ. ມັນອາດຈະເປັນດັ່ງຕໍ່ໄປນີ້:

ສາມວິທີແກ້ໄຂບັນຫາ Leetcode

[5, 7, 23] ແມ່ນສາມຄີກົ້ຕໍ່ກັນ. ເພາະສະນັ້ນກັບຄືນມາເປັນຄວາມຈິງ.

ວິທີການ

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

ສຳ ລັບສິ່ງນີ້ພວກເຮົາສາມາດ ນຳ ໃຊ້ for loop ແລະພວກເຮົາສາມາດປັບປຸງອົງປະກອບທີສາມຂອງແຕ່ລະກຸ່ມ (3 ອົງປະກອບຕິດຕໍ່ກັນ) ຈາກດັດຊະນີ = 2 ເຖິງດັດຊະນີ = n-1. ຫຼັງຈາກນັ້ນສ່ວນທີ່ຕິດຕໍ່ກັນໃນປະຈຸບັນຈະຖືກສະແດງໂດຍອົງປະກອບຕ່າງໆມາຮອດ [i-2], ມາຮອດ [i-1] ແລະມາຮອດ [i].
ພວກເຮົາຈະເລີ່ມ iterating ຈາກອົງປະກອບທີສາມຈາກທາງຫນ້າ. ຖ້າຂະ ໜາດ ຂອງຂບວນ ໜ້ອຍ ກວ່າສາມຫຼັງຈາກນັ້ນພວກເຮົາກໍ່ສົ່ງຄືນທີ່ບໍ່ຖືກຕ້ອງ.

ລະບົບວິເຄາະ

  1. ສ້າງຕົວແປ i ແລະການເລີ່ມຕົ້ນດ້ວຍດັດຊະນີ 2.
  2. Run a ສຳ ລັບ loop ສຳ ລັບຂ້ອຍຈົນກວ່າອົງປະກອບສຸດທ້າຍ, (n-1) ດັດຊະນີ.
  3. ກວດເບິ່ງວ່າອົງປະກອບທີ່ຢູ່ໃນຕົວຊີ້ບອກ i, (i-1) ແລະ (i-2) ແມ່ນຄີກຫຼືບໍ່.
  4. ຖ້າທັງສາມຄີກ, ກັບມາເປັນຄວາມຈິງ. ອື່ນສືບຕໍ່ traversal ໄດ້.
  5. ຫລັງຈາກຜ່ານການຊີ້ບອກທຸກຢ່າງ, ໃຫ້ກັບຄືນມາຕົວະ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບສາມວິທີແກ້ໄຂແບບ Leetcode

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

bool threeConsecutiveOdds(vector<int>& arr) 
{
    int n=arr.size();

    for(int i = 2; i < n; i++) 
    {
        if(arr[i] % 2 == 1 && arr[i-1] % 2 == 1 && arr[i-2] % 2 == 1 )
        return true;
    }

    return false;

}

int main() 
{
    vector<int> arr={1,2,34,3,4,5,7,23,12};
    
    if(threeConsecutiveOdds(arr) )
        cout<<"true"<<endl;
    else
        cout<<"no"<<endl;

  return 0; 
}
true

Java Program ສຳ ລັບສາມວິທີແກ້ໄຂ Leetcode

import java.lang.*;

class Rextester
{  
    public static boolean threeConsecutiveOdds(int[] arr) {

        int n=arr.length;

        for(int i = 2; i < n; i++) 
        {
            if(arr[i] % 2 == 1 && arr[i-1] % 2 == 1 && arr[i-2] % 2 == 1 )
            return true;
        }

        return false;

    }
    
    public static void main(String args[])
    {
       int[] arr={1,2,34,3,4,5,7,23,12};
    
       System.out.println(threeConsecutiveOdds(arr));
   
    }
}
true

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບສາມວິທີແກ້ໄຂບັນຫາ Leetcode

ຄວາມສັບສົນເວລາ

O (N): ບ່ອນທີ່ N ແມ່ນຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ໃນຂະນະທີ່ພວກເຮົາ ກຳ ລັງຜ່ານພຽງແຕ່ຄັ້ງດຽວ ສຳ ລັບດັດສະນີແຕ່ລະຄັ້ງ, ຄວາມສັບສົນຂອງເວລາຈະເປັນ O (N).

ຄວາມສັບສົນໃນອະວະກາດ 

O (1): ພວກເຮົາ ກຳ ລັງບໍ່ໃຊ້ຄວາມ ຈຳ ພິເສດໃດໆ. ເພາະສະນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ຈະຄົງທີ່.