ນັບ subarrays ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 1 ແລະ 0 ຂອງ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Cisco ຄູປອງ Dunia Coursera ຖານຂໍ້ມູນ ລັດ ຫ້ອງທົດລອງ SAP Tesla
Array Hash

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

ບັນຫາ "Countarrays ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 1 ແລະ 0's" ລະບຸວ່າທ່ານຖືກຈັດໃຫ້ເປັນແຖວທີ່ປະກອບດ້ວຍ 0 ແລະ 1 ເທົ່ານັ້ນ. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຂໍໃຫ້ຊອກຫາການນັບ ຈຳ ນວນອະນຸກົມທີ່ປະກອບດ້ວຍບໍ່ເທົ່າກັບ 0 ຂອງໂຄສະນາ 1.

ຍົກຕົວຢ່າງ

arr[] = {0, 0, 1, 1, 0}
4

ຄຳ ອະທິບາຍ: ອານຸພາກຍ່ອຍທັງ ໝົດ ແມ່ນ (1,2), (3,4), (0,3), (1,4)

ນັບ subarrays ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 1 ແລະ 0 ຂອງ

 

arr[] = {1,0,0,1,1,0}
7

ຄຳ ອະທິບາຍ: ອານຸພາກຍ່ອຍທັງ ໝົດ ແມ່ນ (0, 1), (2,3), (0,3), (1,4), (0,5), (4,5), (2,5).

ລະບົບວິເຄາະ

1. Declare the map.
2. Set the output and sum to 0.
3. Traverse the array, while i<n.
  1. Set arr[i] = -1, if arr[i] is equal to 0.
  2. Add the value of arr[i] to the sum.
  3. If the sum is equal to 0, then increase the value of output by 1.
  4. If the map contains the sum, then add the output to the frequency of the current sum’s value in the map.
  5. If the map contains the value sum, then just increase the frequency of the previous sum’s frequency in the map by 1.
  6. Else put that new sum and marks its frequency as 1.
4. Return output.

ຄໍາອະທິບາຍ

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

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

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

ລະຫັດ

ລະຫັດ C ++ ກັບ Count subarrays ທີ່ມີ ຈຳ ນວນ 1's ແລະ 0's ເທົ່າທຽມກັນ

#include <iostream>
#include<map>

using namespace std;

int getSubArrayWithEqual01(int arr[], int n)
{
    map<int,int> MAP;
    int sum=0;
    int output=0;
    for (int i = 0; i < n; i++)
    {
        if (arr[i] == 0)
            arr[i] = -1;

        sum += arr[i];

        if (sum == 0)
            output++;

        if (MAP[sum])
            output += MAP[sum];

        if(MAP[sum]==0)
            MAP[sum]=1;
        else
            MAP[sum]++;
    }
    return output;
}
int main()
{
    int arr[] = { 0, 0, 1, 1, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"Sub-Arrays with equal 0's and 1's count is: " <<getSubArrayWithEqual01(arr, n);
}
Sub-Arrays with equal 0's and 1's count is: 4

ລະຫັດ Java ເພື່ອ Count subarrays ທີ່ມີ ຈຳ ນວນເທົ່າກັບ 1 ແລະ 0 ຂອງ

import java.util.HashMap;
class SubArrayCount01
{
    public static int getSubArrayWithEqual01(int[] arr, int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<>();
        int sum = 0;
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if (arr[i] == 0)
            {
                arr[i] = -1;
            }
            sum += arr[i];

            if (sum == 0)
            {
                output++;
            }
            if (MAP.containsKey(sum))
                output += MAP.get(sum);

            if (!MAP.containsKey(sum))
            {
                MAP.put(sum, 1);
            }
            else
            {
                MAP.put(sum, MAP.get(sum) + 1);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0 };
        int n = arr.length;
        System.out.println("Sub-Arrays with equal 0's and 1's count is:" +getSubArrayWithEqual01(arr, n));
    }
}
Sub-Arrays with equal 0's and 1's count is:4

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

ເວລາ C0mplexity

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

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

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