Subarray ທີ່ຍາວທີ່ສຸດມີ ຈຳ ນວນ 1s ໜຶ່ງ ຫຼາຍກວ່າ ຈຳ ນວນ 0s  


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

ພວກເຮົາໄດ້ມອບ array ຂອງເລກເຕັມ. ອາເລປະກອບດ້ວຍ 1 ແລະ 0 ຂອງເທົ່ານັ້ນ. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາຂໍໃຫ້ຄົ້ນຫາຄວາມຍາວຂອງອະນຸພາກຍາວທີ່ສຸດເຊິ່ງມີປະລິມານ 1 ຕົວເລກແມ່ນພຽງແຕ່ ໜຶ່ງ ເທົ່າກັບ ຈຳ ນວນ 0 ຂອງໃນ sub-array.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ:

ຮອດ [] = {1,0,1,1,0,0,0}

ຜົນໄດ້ຮັບ:

5

ຄໍາອະທິບາຍ:

ຈາກ 0 ຫາ 4 ດັດຊະນີ, {1, 0, 1, 1, 0}, ມີສາມ 1 ແລະສອງ 0 ຂອງ. ພຽງແຕ່ ໜຶ່ງ ນັບຂອງ 1 ເທົ່າກັບ 0 ຂອງ.

ການປ້ອນຂໍ້ມູນ:

ຮອດ [] = {1,0,1,0,0}

ຜົນໄດ້ຮັບ:

3

ຄໍາອະທິບາຍ:

ຈາກ 0 ຫາ 2 ດັດຊະນີ, {1, 0, 1}, ມີສອງ 1 ອັນແລະ 0 ແມ່ນ. ພຽງແຕ່ ໜຶ່ງ ນັບຂອງ 1 ເທົ່າກັບ 0 ຂອງ.

ລະບົບວິເຄາະ  

  1. ປະກາດແຜນທີ່.
  2. ຕັ້ງຄ່າຜົນບວກແລະຜົນຜະລິດຍາວໃຫ້ 0.
  3. ລອກລວງອາເລ, ໃນຂະນະທີ່ i = 0 ເຖິງ i <n.
    1. ກວດເບິ່ງວ່າ arr [i] ເທົ່າກັບ 0 ຖ້າຖືກຕ້ອງແລ້ວຕື່ມ -1 ໃສ່ຜົນບວກ.
    2. ອື່ນເພີ່ມ +1 ໃຫ້ເປັນຜົນລວມ.
    3. ໃຫ້ກວດເບິ່ງວ່າ ຜົນບວກແມ່ນເທົ່າກັນ ເຖິງ 1, ຫຼັງຈາກນັ້ນເພີ່ມມູນຄ່າຂອງຄວາມຍາວຂອງຜົນຜະລິດໂດຍ 1.
    4. ອີກຢ່າງ ໜຶ່ງ, ກວດເບິ່ງວ່າແຜນທີ່ບໍ່ມີຜົນລວມຖ້າວ່າຖືກຕ້ອງແລ້ວໃຫ້ເອົາຍອດລວມແລະມູນຄ່າປັດຈຸບັນຂອງຂ້ອຍເຂົ້າໃສ່ແຜນທີ່ພ້ອມກັບຜົນລວມ.
    5. ກວດເບິ່ງວ່າແຜນທີ່ປະກອບມີ (ຜົນລວມ 1).
    6. ຖ້າຜົນຜະລິດມີຄວາມຍາວ ໜ້ອຍ ກວ່າດັດຊະນີ i-index (ມູນຄ່າລວມຂອງແຜນທີ່).
      1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນປັບປຸງ outputLength ໃຫ້ເປັນ i-index.
  4. ສົ່ງຄືນຄວາມຍາວຂອງຜົນຜະລິດ.
ເບິ່ງ
ອາໄຫຼ່ຄູ່ຫຼັງຈາກລະດັບ M ປິດການໃຊ້ງານ

ຄໍາອະທິບາຍ  

ພວກເຮົາຈະປະກາດກ ແຜນທີ່. ໃນແຜນທີ່ນັ້ນ, ພວກເຮົາ ກຳ ລັງຈະເກັບຄ່າຂອງຜົນລວມແລະຄ່າຂອງດັດຊະນີປັດຈຸບັນ, ຖ້າສະພາບການພໍດີ. ເອົາຕົວແປສອງຕົວແລະ ກຳ ນົດຜົນບວກໃສ່ 0 ແລະ outputLength ຫາ 0. ໃນຂະນະທີ່ ກຳ ລັງຜ່ານແຖວ, ພວກເຮົາຈະເລືອກເອົາແຕ່ລະອົງປະກອບຂອງ array, ແລະກວດເບິ່ງວ່າ arr [i] ເທົ່າກັບ 0, ຖ້າພົບວ່າມັນເທົ່າກັນ, ພວກເຮົາຈະເພີ່ມ -1 ເພື່ອສະຫຼຸບແລະເກັບມ້ຽນມັນເພື່ອເປັນຜົນບວກ, ອີກຢ່າງ ໜຶ່ງ ຖ້າພວກເຮົາບໍ່ໄດ້ພົບວ່າ 0, ພວກເຮົາຈະເອົາເລກບວກ 1 ໄປໃສ່ແລະເກັບມັນເປັນຜົນລວມ.

ເຫດຜົນທີ່ຢູ່ເບື້ອງຫຼັງວ່າລົບ 1 ແລະບວກ 1 ແມ່ນພວກເຮົາ ກຳ ລັງ ທຳ ທ່າວ່າທັງ ໝົດ 0 ເປັນ -1 ແລະເພີ່ມພວກມັນຢູ່ກັບ 1, ດັ່ງນັ້ນພວກເຮົາຈະໄດ້ເລກ 0 ຢູ່ສະ ເໝີ. ແຕ່ພວກເຮົາຈະກວດເບິ່ງບວກ 1 ບວກເຊິ່ງສະແດງໃຫ້ເຫັນວ່າພວກເຮົາຈະມີ 1 ອັນພິເສດ 0 ແລ້ວນັບ ຈຳ ນວນ XNUMX ຂອງ.

ສົມມຸດວ່າ, ພວກເຮົາຈະເອົາ 1, 0, 1 ຖ້າພວກເຮົາ ກຳ ລັງ ທຳ ທ່າວ່າ 0 ເປັນ -1, ພວກເຮົາຈະໄດ້ຮັບເລກ 0 ນັ້ນດ້ວຍ 2 ຕົວ ທຳ ອິດ, ແລະດ້ວຍເລກທີສາມ, ພວກເຮົາສາມາດພົບວ່າສະພາບການຂອງພວກເຮົາໄດ້ ສຳ ເລັດແລ້ວ. ພວກເຮົາໄດ້ຮັບແຖວຍ່ອຍຂອງ 1 ແລະ 0 ຂອງດ້ວຍການນັບ ໜຶ່ງ ພິເສດຂອງ 1 ກ່ວາ 0. ພວກເຮົາໄດ້ຮັບສະພາບການຂອງພວກເຮົາພໍໃຈ. ນັ້ນແມ່ນເຫດຜົນທີ່ພວກເຮົາຈະຊອກຫາຖ້າຜົນລວມເທົ່າກັບ 1 ໃນຂັ້ນຕອນຕໍ່ໄປຂອງສູດການຄິດໄລ່ແລະຈະ ກຳ ລັງປັບປຸງຄວາມຍາວຂອງຜົນໄດ້ຮັບ. ໃນທີ່ສຸດ, ຖ້າ ຄຳ ຖະແຫຼງການ, ຖ້າພວກເຮົາໄດ້ຮັບຄວາມຍາວຂອງຜົນຜະລິດ ໃໝ່, ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ປັບປຸງຂໍ້ມູນທີ່ຜ່ານມາກັບຄວາມຍາວຂອງຜົນຜະລິດໃນປະຈຸບັນແລະພວກເຮົາຈະສົ່ງຜົນຜະລິດກັບຄວາມຍາວອອກ.

ເບິ່ງ
ຊອກຫາອົງປະກອບທີ່ຊ້ ຳ ກັນ

ການປະຕິບັດ  

ໂປຣແກຣມ C ++ ສຳ ລັບ Subarray ທີ່ຍາວທີ່ສຸດມີ ຈຳ ນວນ 1s ໜຶ່ງ ຫຼາຍກວ່າ ຈຳ ນວນ 0s

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

ໂປຣແກຣມ Java ສຳ ລັບ Subarray ທີ່ຍາວທີ່ສຸດມີ ຈຳ ນວນ 1s ໜຶ່ງ ຫຼາຍກວ່າ ຈຳ ນວນ 0s

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Subarray ທີ່ຍາວທີ່ສຸດມີ ຈຳ ນວນ 1 ອັນ ໜຶ່ງ ຫຼາຍກວ່າ ຈຳ ນວນ 0s  

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

O (n) ບ່ອນທີ່ "n"  ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

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

O (n) ບ່ອນທີ່ "n"  ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.