ວິທີແກ້ໄຂບັນຫາ Leetcode ທີ່ສູງສຸດ


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

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

ໃນບັນຫາ Max Consecutive Ones ມີບັນຫາຖານສອງ. ພວກເຮົາຕ້ອງຊອກຫາ ຈຳ ນວນທີ່ຕິດຕໍ່ກັນສູງສຸດທີ່ມີຢູ່ໃນອາເລທີ່ ກຳ ນົດໄວ້.
ຂບວນການປ້ອນຂໍ້ມູນຈະມີພຽງແຕ່ 0 ແລະ 1 ເທົ່ານັ້ນ.

ຍົກຕົວຢ່າງ

[1,1,0,1,1,1]
3

ຄໍາອະທິບາຍ:
ສອງຕົວເລກ ທຳ ອິດຫລືສາມໂຕສຸດທ້າຍແມ່ນ 1 ອັນຕິດຕໍ່ກັນ.
ຈຳ ນວນສູງສຸດຂອງ 1s ຕິດຕໍ່ກັນແມ່ນ 3.

[0,1,0]
1

ຄໍາອະທິບາຍ:
ຈຳ ນວນສູງສຸດຂອງ 1s ຕິດຕໍ່ກັນແມ່ນ 1.

ວິທີການ

ເພື່ອແກ້ໄຂບັນຫານີ້ພວກເຮົາສາມາດແກ້ໄຂໄດ້ໂດຍຜ່ານການດັດສະນີໃນແຖວໃນສອງ ຮັງໃນຂະນະທີ່ loop ໂດຍປະຕິບັດຕາມສູດການຄິດໄລ່:

1. ສ້າງຕົວປ່ຽນແປງສູງສຸດຂອງຕົວປ່ຽນແປງເຊິ່ງຈະເກັບຮັກສາ 1s ຕິດຕໍ່ກັນທີ່ສູງສຸດຕິດຕໍ່ກັນໃນລະຫວ່າງການຍ່າງ.
2. ສ້າງແລະເລີ່ມຕົ້ນຕົວແປ i ໂດຍມີດັດຊະນີ ທຳ ອິດ.
3. ດຽວນີ້ ດຳ ເນີນການ loop ໃນຂະນະທີ່ i <array ຂະ ໜາດ.
4. ພາຍໃນວົງຈອນພວກເຮົາຈະກວດເບິ່ງວ່າຕົວເລກຢູ່ທີ່ດັດຊະນີປະຈຸບັນ i ແມ່ນ 1 ຫຼືບໍ່. ຖ້າມັນບໍ່ເທົ່າກັບ 1 ຫຼັງຈາກນັ້ນເພີ່ມດັດຊະນີ i. ອື່ນຖ້າມັນເທົ່າກັບ 1, ຫຼັງຈາກນັ້ນດໍາເນີນການຮັງໃນຂະນະທີ່ loop ໂດຍການສ້າງຕົວແປນັບແລະເລີ່ມຕົ້ນດ້ວຍ 0. ຫຼັງຈາກນັ້ນຂ້າມແຖວສໍາລັບ 1s ຕິດຕໍ່ກັນໃນທີ່ຮັງໃນຂະນະທີ່ loop. ຕົວຢ່າງເຊັ່ນ: ແຖວລ້ຽວຂ້າມໃນຂະນະທີ່ເລກ [i] ເທົ່າກັບ 1, ຄຽງຄູ່ກັບການນັບ ຈຳ ນວນ 1s ຕິດຕໍ່ກັນໃນປະຈຸບັນດັ່ງທີ່ສະແດງໃນຮູບຂ້າງລຸ່ມນີ້:

ຄົນສູງສຸດທີ່ຕໍ່ເນື່ອງ
5. ຫລັງຈາກພົບພໍ້ກັບ 0 ຫລືສິ້ນສຸດຂອງຂບວນ, ປັບປຸງຕົວແປສູງສຸດໂດຍການປຽບທຽບຄ່າເກົ່າຂອງມັນກັບຄ່າ 1s ຕິດຕໍ່ກັນໃນປະຈຸບັນທີ່ເກັບໄວ້ໃນຕົວປ່ຽນນັບ.
6. ຫຼັງຈາກທີ່ໃນຂະນະທີ່ loop ສຳ ເລັດໃຫ້ກັບມູນຄ່າສູງສຸດ.

ການປະຕິບັດ

ໂປຣແກຣມ C ++ ສຳ ລັບວິທີແກ້ໄຂບັນຫາ Leetcode ສູງສຸດທີ່ບໍ່ມີຕົວຕົນ

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

int findMaxConsecutiveOnes(vector<int>& nums) {

    int maximum=0;
    int i=0;

    while(i<nums.size())
    {
        int conOnes=0;
        while(i< nums.size() && nums[i]==1)
        {
            conOnes++;
            i++;
        }

        maximum=max(maximum,conOnes);
        i++;
    }

    return maximum; 
}

int main() 
{
    vector<int> nums={1,1,0,1,1,1};
    cout<<findMaxConsecutiveOnes(nums)<<endl;

  return 0; 
}
3

Java Program ສຳ ລັບການແກ້ໄຂບັນຫາ Leetcode ສູງສຸດແບບຕໍ່ເນື່ອງ

import java.lang.*;

class MaxOnes
{  
    public static int findMaxConsecutiveOnes(int[] nums) 
    {
        int maximum=0;
        int i=0;

        while(i<nums.length)
        {
        int conOnes=0;
        while(i< nums.length && nums[i]==1)
        {
        conOnes++;
        i++;
        }

        maximum=Math.max(maximum,conOnes);

        i++;
        }

        return maximum; 

    }
    
    public static void main(String args[])
    {
        int nums[]={1,1,0,1,1,1};

        System.out.println(findMaxConsecutiveOnes(nums));
        
    }
}
3

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

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

O (N): ພວກເຮົາ ກຳ ລັງຜ່ານຕາລາງຈາກການເລີ່ມຕົ້ນດັດສະນີຈົນເຖິງດັດຊະນີສຸດທ້າຍແລະເຂົ້າເບິ່ງແຕ່ລະດັດນີດຽວເທົ່ານັ້ນ. ສະນັ້ນຄວາມສັບສົນເວລາຈຶ່ງຈະເປັນເສັ້ນ O (N).

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

O (1): ພວກເຮົາບໍ່ໄດ້ໃຊ້ພື້ນທີ່ພິເສດ, ເພາະສະນັ້ນພື້ນທີ່ທີ່ ນຳ ໃຊ້ແມ່ນມີຢູ່ຕະຫຼອດເວລາ.