ນັບ Subarrays ກັບອົງປະກອບແບບດຽວກັນແລະຄີກ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Accenture ປັດໃຈ ສະ ເໜ່
Array Hash

ສົມມຸດວ່າທ່ານໄດ້ເອົາເລກເຕັມ array ຂອງຂະ ໜາດ N. ຍ້ອນວ່າມີຕົວເລກ, ຕົວເລກແມ່ນຄີກຫຼືແມ່ນແຕ່. ຄຳ ຖະແຫຼງທີ່ມີບັນຫາແມ່ນ count subarray ທີ່ມີສ່ວນປະກອບຍ່ອຍແລະຄີກດຽວກັນຫຼືຄົ້ນພົບ ຈຳ ນວນຂອງ sub-arrays ທີ່ມີ ຈຳ ນວນເທົ່າກັນຂອງເລກບວກເຖິງແມ່ນວ່າແລະຄີກ.

ຍົກຕົວຢ່າງ  

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

arr [] = {2, 5, 1, 6};

ຜົນຜະລິດ

3

ຄໍາອະທິບາຍ

ຍ້ອນວ່າມັນມີ 2 {5, 1}, {6, 2}, {5, 1, 6, XNUMX}

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

ຮອດ [] = {2,3,4,5,1,6}

ຜົນຜະລິດ

7

ລະບົບວິເຄາະ  

  1. ປະກາດສອງອາຄານ, positiveNum ແລະ negativeNum ຂອງຂະ ໜາດ n + 1.
  2. ກໍານົດການນັບແລະຜົນໄດ້ຮັບເປັນ 0, ແລະກໍານົດ positiveNum [0] ເປັນ 1.
  3. ຂ້າມອາເລ ຈາກ i = 0, ເຖິງ i
    1. ກວດເບິ່ງວ່າການເຮັດວຽກແບບບິດເບືອນແລະການເຂົ້າເຖິງ [i] & 1 ເທົ່າກັບ 1,
      1. ຖ້າຖືກຕ້ອງ, ຫຼັງຈາກນັ້ນເພີ່ມ ຈຳ ນວນນັບ 1.
    2. ອີກຢ່າງ ໜຶ່ງ, ຫຼຸດ ຈຳ ນວນນັບ 1.
    3. ຖ້າການນັບ ໜ້ອຍ ກວ່າ 0, ຫຼັງຈາກນັ້ນຕື່ມຜົນຜະລິດເຂົ້າໃນ negativeNum [-count] ແລະເກັບມັນໄວ້ໃນຜົນຜະລິດ.
    4. ອີກອັນ ໜຶ່ງ, ເພີ່ມຜົນຜະລິດເຂົ້າໃນ positiveNum [ນັບ] ແລະເກັບມັນໄວ້ເພື່ອຜົນຜະລິດ.
  4. ກັບຄືນຜົນຜະລິດ.

ຄໍາອະທິບາຍ  

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

ເບິ່ງ
ຫຼຸດຜ່ອນຄວາມແຕກຕ່າງສູງສຸດລະຫວ່າງຄວາມສູງ

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

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

ການປະຕິບັດ  

ໂປຣແກຣມ C ++ ສຳ ລັບ Count Subarrays ກັບ Same Even ແລະ Odd Elementes

#include<iostream>
#include<unordered_map>

using namespace std;

int getOESubarrays(int arr[], int n)
{
    int count = 0;
    int output = 0;

    int positiveNum[n+1];
    int negativeNum[n+1];

    positiveNum[0] = 1;

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

        if (count < 0)
        {
            output += negativeNum[-count];
            negativeNum[-count]++;
        }
        else
        {
            output += positiveNum[count];
            positiveNum[count]++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {2,3,4,5,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Even Odd Sub-Arrays are: " << getOESubarrays(arr,n);
    return 0;
}
Even Odd Sub-Arrays are: 7

ໂປແກຼມ Java ສຳ ລັບ Count Subarrays ກັບ Same Even ແລະ Odd Elementes

class oddEvenSubArrays
{
    public static int getOESubarrays(int[] arr, int n)
    {
        int count = 0;
        int output = 0;

        int positiveNum[] = new int[n + 1];
        int negativeNum[] = new int[n + 1];

        positiveNum[0] = 1;

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

            if (count < 0)
            {
                output += negativeNum[-count];
                negativeNum[-count]++;
            }
            else
            {
                output += positiveNum[count];
                positiveNum[count]++;
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,3,4,5,1,6};
        int n = arr.length;
        System.out.println("Even Odd Sub-Arrays are: "+getOESubarrays(arr, n));
    }
}
Even Odd Sub-Arrays are: 7

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ Subarrays Count ທີ່ມີອົງປະກອບແບບດຽວກັນແລະຄີກ  

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

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

ເບິ່ງ
ການແບ່ງ Array ອອກເປັນຄູ່ດ້ວຍ Sum ແບ່ງອອກໂດຍ K

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

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