subarray ທີ່ໃຫຍ່ທີ່ສຸດທີ່ມີຈໍານວນເທົ່າກັບ 0s ແລະ 1s  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon Coursera ສີເທົາສີສົ້ມ MakeMyTrip Morgan Stanley Paytm Synopsys ອິນເຕີເນັດ Times Times
Array Hash

ເຈົ້າຍັງບໍ່ໄດ້ໃຫ້ຈໍານວນຂອງຕົວເລກໄດ້. ເລກເຕັມແມ່ນພຽງແຕ່ 0 ແລະ 1 ເທົ່ານັ້ນໃນແຖວເຂົ້າ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຄົ້ນຫາອະນຸ ກຳ ມະການທີ່ໃຫຍ່ທີ່ສຸດທີ່ສາມາດມີ ຈຳ ນວນເທົ່າກັບ 0s ແລະ 1s.

ຍົກຕົວຢ່າງ  

arr[]={0,1,0,1,0,1,1,1}
0 to 5 (total 6 elements)

ຄໍາອະທິບາຍ

ຈາກ ຕຳ ແໜ່ງ ອາເລ 0 ຫາ 5 ມັນບໍ່ມີເທົ່າກັບ 0s ແລະ 1s

ນັບ 0s 3

ນັບ 1s ⇒ 3

ແລະນີ້ແມ່ນຂອດຍ່ອຍທີ່ໃຫຍ່ທີ່ສຸດທີ່ເກັບບໍ່ເທົ່າ 0s ແລະ 1s.

ສູດການຄິດໄລ່ເພື່ອຊອກຫາອະວະກາດໃຕ້ດິນທີ່ໃຫຍ່ທີ່ສຸດເຊິ່ງມີ ຈຳ ນວນເທົ່າກັບ 0s ແລະ 1s  

  1. ປະກາດກ HashMap.
  2. ທີ່ກໍານົດໄວ້ sum, ຄວາມຍາວສູງສຸດ, startingIndex ເຖິງ 0 ແລະ endIndex ເຖິງ -1.
  3. ລອກລວງອາເລແລະປັບປຸງແຕ່ລະສ່ວນຂອງອາເລເປັນ -1 ຖ້າມັນເທົ່າກັບ 0.
  4. ເລີ່ມຕົ້ນ loop ຈາກ 0 ເຖິງ n-1 (n ແມ່ນຄວາມຍາວຂອງຂບວນ).
    1. ເພີ່ມແຕ່ລະຄ່າຂອງ arr [i] ໃສ່.
    2. ກວດເບິ່ງວ່າຜົນລວມເທົ່າກັບ 0, ຖ້າວ່າແມ່ນ,
      1. ຈາກນັ້ນອັບເດດ ຄວາມຍາວສູງສຸດ ຄືກັບ i + 1, ແລະ endIndex ຄືກັບຂ້ອຍ.
    3. ກວດເບິ່ງວ່າແຜນທີ່ມີຍອດ + n ຢູ່ໃນ,
      1. ຫຼັງຈາກນັ້ນອັບເດດຄວາມຍາວຂອງ maxLength ເປັນມູນຄ່າ i - map (sum + n) ຈາກແຜນທີ່ແລະສິ້ນສຸດ Index ເປັນ i.
    4. ອື່ນເອົາການລວມເຂົ້າ + n ເຂົ້າໃນແຜນທີ່.
  5. ພິມສິ້ນສຸດລົງIndex - maxLength + 1 ແລະ endingIndex.
ເບິ່ງ
Traversal Tree (ການສັ່ງຊື້ລ່ວງ ໜ້າ, ເຄື່ອງສັ່ງຊື້ແລະເຄື່ອງພີມ)

ຄໍາອະທິບາຍ  

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

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

ພວກເຮົາ ກຳ ລັງຈະໄປ, ເພື່ອສະຫຼຸບ, ທຸກໆມູນຄ່າໃນອາເລ, ແລະຊອກຫາວ່າມັນເທົ່າກັບ 0, ຖ້າເທົ່າກັບພຽງແຕ່ອັບເດດຄວາມຍາວສູງສຸດຂອງອາເລແລະສິ້ນສຸດຂອງອິນເຕີ. ພວກເຮົາ ກຳ ລັງຈະເອົາ sum + n ເຂົ້າໄປໃນແຜນທີ່ຖ້າມັນບໍ່ມີຢູ່ແລ້ວ, ແລະຖ້າມັນມີຢູ່ແລ້ວກວດເບິ່ງບາງເງື່ອນໄຂແລ້ວປັບປຸງມູນຄ່າຂອງຄວາມຍາວແລະຄວາມຍາວສຸດທ້າຍຂອງ EndIndex. ພິມ endIndex - maxLength + 1 ເປັນຈຸດເລີ່ມຕົ້ນຂອງຂອບເຂດແລະ endIndex ເປັນຈຸດສິ້ນສຸດຂອງຂອບເຂດ.

ເບິ່ງ
ດຶງອອກຈາກບັນຊີລາຍຊື່ທີ່ເຊື່ອມໂຍງອອກຈາກ Leetcode Solution

subarray ທີ່ໃຫຍ່ທີ່ສຸດທີ່ມີຈໍານວນເທົ່າກັບ 0s ແລະ 1sPin

ລະຫັດ  

ລະຫັດ C ++ ເພື່ອຊອກຫາສາຍໃຕ້ດິນທີ່ໃຫຍ່ທີ່ສຸດເຊິ່ງມີ ຈຳ ນວນເທົ່າກັບ 0s ແລະ 1s

#include<iostream>
#include<unordered_map>

using namespace std;

int getLargestSubA(int arr[], int n)
{
    unordered_map<int, int> MAP;

    int sum = 0;
    int maxLength = 0;
    int endingIndex = -1;

    for (int i = 0; i < n; i++)
        arr[i] = (arr[i] == 0) ? -1 : 1;

    for (int i = 0; i < n; i++)
    {
        sum += arr[i];
        if (sum == 0)
        {
            maxLength = i + 1;
            endingIndex = i;
        }
        if (MAP.find(sum + n) != MAP.end())
        {
            if (maxLength < i - MAP[sum + n])
            {
                maxLength = i - MAP[sum + n];
                endingIndex = i;
            }
        }
        else
            MAP[sum + n] = i;
    }
    cout<<endingIndex - maxLength + 1 <<" to " <<endingIndex;

    return maxLength;
}

int main()
{
    int arr[] = { 0,1,0,1,0,1,1,1 };
    int n = sizeof(arr) / sizeof(arr[0]);

    getLargestSubA(arr, n);
    return 0;
}
0 to 5

ການຈັດຕັ້ງປະຕິບັດຢູ່ເກາະຈາວາເພື່ອຊອກຫາອະວະກາດໃຕ້ດິນທີ່ໃຫຍ່ທີ່ສຸດເຊິ່ງມີ ຈຳ ນວນ 0s ແລະ 1s ເທົ່າກັນ

import java.util.HashMap;

class LargestSubArrayWithEqual01
{
    public static int getLargestSubA(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer, Integer>();

        int sum = 0;

        int maxLength = 0;
        int endingIndex = -1;

        for (int i = 0; i < n; i++)
        {
            arr[i] = (arr[i] == 0) ? -1 : 1;
        }

        for (int i = 0; i < n; i++)
        {
            sum += arr[i];
            if (sum == 0)
            {
                maxLength = i + 1;
                endingIndex = i;
            }
            if (MAP.containsKey(sum + n))
            {
                if (maxLength < i - MAP.get(sum + n))
                {
                    maxLength = i - MAP.get(sum + n);
                    endingIndex = i;
                }
            }
            else
                MAP.put(sum + n, i);

        }
        int end = endingIndex - maxLength + 1;
        System.out.println(end + " to " + endingIndex);

        return maxLength;
    }
    
    public static void main(String[] args)
    {
        int arr[] = {0,1,0,1,0,1,1,1};
        int n = arr.length;

        getLargestSubA(arr, n);
    }
}
0 to 5

ການວິເຄາະຄວາມສັບສົນ  

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ນີ້ພວກເຮົາສາມາດແກ້ໄຂບັນຫານີ້ໃນ O (n) ເພາະວ່າພວກເຮົາໄດ້ໃຊ້ HashMap ແລ້ວ. ເນື່ອງຈາກວ່າ HashMap ສາມາດໃສ່, ລຶບຫຼືດັດແປງອົງປະກອບຕ່າງໆໃນ O (1) ເວລາສັບສົນ.

ເບິ່ງ
ຊອກຫາວ່າອາເລແມ່ນຊຸດຍ່ອຍຂອງຂບວນອື່ນ

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ເນື່ອງຈາກ ຈຳ ນວນຂອງສ່ວນປະກອບທີ່ຈະຖືກໃສ່ໃນກໍລະນີທີ່ບໍ່ດີທີ່ສຸດເຂົ້າໄປໃນ hashmap ຈະມີຫຼາຍທີ່ສຸດ. ຄວາມສັບສົນໃນອະວະກາດເສັ້ນນີ້ບັນລຸໄດ້.