ຈໍານວນຂອງຊັອກໂກແລັດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນໃນບັນດານັກຮຽນ k  


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Accenture Adobe Amazon ເຟສບຸກ ສີ່ພັນ
Array Hash

"ຈຳ ນວນຊັອກໂກແລດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນໃນບັນດານັກຮຽນ k" ກ່າວວ່າທ່ານໄດ້ຮັບກ່ອງ n ທີ່ມີຊັອກໂກແລັດໃນມັນ. ສົມມຸດວ່າມີນັກຮຽນ k. ໜ້າ ວຽກແມ່ນແຈກແຈກ ຈຳ ນວນຊັອກໂກແລດສູງສຸດໃນບັນດານັກຮຽນ k ເທົ່າທຽມກັນ, ໂດຍການເລືອກກ່ອງຕິດຕໍ່ກັນ. ພວກເຮົາສາມາດສົມມຸດວ່າກ່ອງແມ່ນຢູ່ໃນແຖວທີ່ປະກອບດ້ວຍຕົວເລກຈາກ 1 ເຖິງ n. ໜ້າ ວຽກແມ່ນເລືອກກຸ່ມກ່ອງທີ່ສາມາດແຈກຊັອກໂກແລັດໄດ້ຫຼາຍທີ່ສຸດໃຫ້ນັກຮຽນ k ເທົ່າທຽມກັນ. ກ່ອງທີ່ມອບໃຫ້ສາມາດພິຈາລະນາເປັນແຖວແລະມາຮອດ [i] ສາມາດເປັນຕົວແທນ ຈຳ ນວນຊັອກໂກແລດໃນມັນຢູ່ໃນ ຕຳ ແໜ່ງ ຂອງດັດຊະນີ i.

ຍົກຕົວຢ່າງ  

arr[] = {1, 5, 3, 6, 10, 1}

k = 3
8

ຄໍາອະທິບາຍ: ຕົວເລກຈາກອະນຸພາກ 5, 3, 6, 10 ປະກອບມີ 24 ຊັອກໂກແລດເຊິ່ງສາມາດແຈກຢາຍໄດ້ໃນບັນດານັກຮຽນ k. ນັ້ນ ໝາຍ ຄວາມວ່າຊັອກໂກແລັດ 8 ໜ່ວຍ ຕໍ່ນັກຮຽນເຊິ່ງເປັນ ຈຳ ນວນສູງສຸດຂອງຄຸນຄ່າທີ່ໄດ້ມອບໃຫ້.

ລະບົບວິເຄາະ  

1. Declare a map.
2. Declare an array ‘sum’ of size n (length of the given array).
3. Set resultant to 0 and copy the value of arr[0] to sum[0].
4. Add all the values of arr[i] and sum[i-1] and store each value at sum[i].
5. Traverse the array, while i < n (length of the array).
  1. Set temp to sum[i]%k and check if the temp is equal to 0.
    1. If true then check for if resultant is less than sum[i], if true, then update resultant = sum[i].
  2. Check if the temp is present in a map, if present, then, push this value and the current index into the map.
  3. Else get the number which is related with the temp in a map, let x= map[temp], check if resultant is less than the sum[i] –sum[x].
    1. If true then update the value of resultant=sum[i]-sum[x], where x is map[temp].
6. Return the (resultant / k ).

ຄໍາອະທິບາຍ  

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

ເບິ່ງ
ການອອກແບບໂຄງສ້າງຂໍ້ມູນ

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

ໃຫ້ພວກເຮົາຍົກຕົວຢ່າງຂອງມັນ:

ຍົກຕົວຢ່າງ

arr [] = {1, 5, 3, 6, 10, 1}, k = 3

ຜົນບວກ [0] = ມາຮອດ [0] = 1.

ຜົນລວມ [1] = ມາຮອດ [i] + ຜົນບວກ [i-1] = 6,

ຜົນບວກ [2] = ມາຮອດ [i] + ຜົນບວກ [i-1] = 9, ສືບຕໍ່ມັນ, ພວກເຮົາຈະມີຄຸນຄ່າຕໍ່ໄປນີ້ໃນຜົນລວມ.

ຜົນບວກ [] = {1, 6, 9, 15, 25, 26}.

ພວກເຮົາຈະລວບລວມອາເລອີກເທື່ອ ໜຶ່ງ, ຈັບເອົາ temp ເປັນຜົນລວມ [i]% k. ພວກເຮົາຈະກວດເບິ່ງວ່າ temp ແມ່ນເທົ່າກັບ 0, ແຕ່ມັນບໍ່ແມ່ນ, ດັ່ງນັ້ນພວກເຮົາຈະກວດເບິ່ງວ່າແຜນທີ່ບໍ່ມີຄຸນຄ່ານີ້, ພວກເຮົາຈະເອົາດັດສະນີປະຈຸບັນໃສ່ໃນແຜນທີ່. ດັ່ງນັ້ນໃນແຜນທີ່, ພວກເຮົາມີ (1,0) ດຽວນີ້.

ເກັບເອົາເລກທີ 6 ຕໍ່ໄປແລະກວດສອບຜົນລວມ [i]% k ເປັນວັດ, ພົບວ່າມັນເປັນ 0 ໃນຕອນນີ້, ສະນັ້ນພວກເຮົາຈະປັບປຸງຜົນທີ່ໄດ້ຮັບໃນຕອນນີ້. ຜົນໄດ້ຮັບຈະເປັນ 6.

ອົງປະກອບຕໍ່ໄປຈະແມ່ນ 9 ແລະ 15, ໃນຮູບແບບນີ້ທັງສອງມີໂມດູນເຖິງ 3 ແມ່ນ 0, ດັ່ງນັ້ນເຖິງ 15, ຜົນອອກມາຈະເປັນ 15. ຕົວເລກຕໍ່ໄປແມ່ນ 25, ພວກເຮົາມີເຂດເວລາດຽວນີ້ຄືກັບ 1. ກັບສະພາບການອື່ນ. ແຕ່ພວກເຮົາມີ 1 ຢູ່ໃນແຜນທີ່ແລ້ວ. ດັ່ງນັ້ນພວກເຮົາຈະໄດ້ຮັບຄ່າຂອງມັນແລະນັ້ນແມ່ນ 0, ດັ່ງທີ່ພວກເຮົາເກັບ 1 ແລະ 0 ເຂົ້າໃນແຜນທີ່. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຈະຊອກຫາຜົນລວມ [i] -sum [0], ແລະນັ້ນຈະແມ່ນ 24, ປັບປຸງໃຫ້ເປັນຜົນມາຈາກຕົວເລກນີ້.

ເບິ່ງ
ຊອກຫາສິ່ງທີ່ຕິດຄັດມາຂອງຂະ ໜາດ 3 ໃນເວລາເສັ້ນ

ຫລັງຈາກໄປຢ້ຽມຢາມເບີຕື່ມອີກ, ພວກເຮົາຍັງມີ ຄຳ ຕອບຄືກັນກັບ 24. ສຸດທ້າຍ, ພວກເຮົາຈະກັບຄືນ 24/3 ນັ້ນແມ່ນ 8. ນີ້ຈະແມ່ນ ຄຳ ຕອບສຸດທ້າຍຂອງພວກເຮົາ.

ຈໍານວນຂອງຊັອກໂກແລັດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນໃນບັນດານັກຮຽນ kPin

ການປະຕິບັດ  

ໂປຼແກຼມ C ++ ສຳ ລັບ ຈຳ ນວນຊັອກໂກແລັດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນລະຫວ່າງນັກຮຽນ k

#include<iostream>
#include<unordered_map>

using namespace std;

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

    int sum[n];

    int resultant = 0;

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

    for (int i = 0; i < n; i++)
    {
        int temp = sum[i] % k;

        if (temp == 0)
        {
            if (resultant < sum[i])
                resultant = sum[i];
        }
        else if (MAP.find(temp) == MAP.end())
            MAP[temp] = i;

        else if (resultant < (sum[i] - sum[MAP[temp]]))
            resultant = sum[i] - sum[MAP[temp]];
    }
    return (resultant / k);
}
int main()
{
    int arr[] = {1, 5, 3, 6, 10, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "Number of chocolates which can be equally distributed:  "<< getChocolateNumbers(arr, n, k);
    return 0;
}
Number of chocolates which can be equally distributed:  8

Java ໂປແກຼມ ສຳ ລັບ ຈຳ ນວນຊັອກໂກແລັດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນໃນບັນດານັກຮຽນ k

import java.util.HashMap;

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

        int sum[]=new int[n];

        int resultant = 0;

        sum[0] = arr[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] = sum[i - 1] + arr[i];
        }
        for (int i = 0; i < n; i++)
        {
            int temp = sum[i] % k;

            if (temp == 0)
            {
                if (resultant < sum[i])
                    resultant = sum[i];
            }

            else if (!MAP.containsKey(temp) )
                MAP.put(temp, i);

            else if (resultant < (sum[i] - sum[MAP.get(temp)]))
                resultant = sum[i] - sum[MAP.get(temp)];
        }

        return (resultant / k);
    }
    public static void main(String[] args)
    {
        int arr[] = { 1,5,3,6,10,1 };
        int n = arr.length;
        int k = 3;
        System.out.println("Number of chocolates which can be equally distributed: "+ getChocolateNumbers(arr, n, k));
    }
}
Number of chocolates which can be equally distributed: 8

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບ ຈຳ ນວນຊັອກໂກແລັດສູງສຸດທີ່ຈະແຈກຢາຍຢ່າງເທົ່າທຽມກັນໃນບັນດານັກຮຽນ k  

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

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

ເບິ່ງ
ຈໍານວນຂອງການແກ້ໄຂ Domino ທຽບເທົ່າ Leetcode

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

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

ກະສານອ້າງອີງ