ເດັກນ້ອຍທີ່ມີ ຈຳ ນວນຕົວເລກທີ່ຍິ່ງໃຫຍ່ທີ່ສຸດຂອງ Leetcode Solution


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

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

  • ເດັກນ້ອຍທຸກໆຄົນສາມາດມີເລດໄດ້ຫຼາຍທີ່ສຸດ ຫຼັງຈາກການແຈກຢາຍ(ບໍ່ວ່າຈະມີສ່ວນໃຫຍ່ຫລືຮ່ວມກັນ)?

ພວກເຮົາ ຈຳ ເປັນຕ້ອງໄດ້ພິມຄວາມເປັນໄປໄດ້ນີ້ໃນຮູບແບບຂອງແວວບູຕິກ.

ຍົກຕົວຢ່າງ

Array = {1 , 4 , 5 , 6 , 7}
Extra = 5
false true true true true

ຄໍາອະທິບາຍ

ລູກຜູ້ທີ 1: ເຖິງແມ່ນວ່າພວກເຮົາຈະໃຫ້ທຸກຢ່າງ ເຂົ້າ ໜົມ ພິເສດໃຫ້ເດັກຜູ້ ທຳ ອິດ, ມັນຈະມີເຂົ້າ ໜົມ 6 <7 (ເດັກນ້ອຍທີ 5). ດັ່ງນັ້ນ, ພວກເຮົາພິມ ທີ່ບໍ່ຖືກຕ້ອງ ສໍາລັບມັນ.

ລູກຜູ້ທີ 2: ພວກເຮົາໃຫ້ທັງ ໝົດ ເຂົ້າ ໜົມ ພິເສດ ສຳ ລັບເດັກນ້ອຍຄົນນີ້, ເຮັດໃຫ້ມີການນັບ 9 > 7 (ລູກຜູ້ທີ 5). ດັ່ງນັ້ນ, ພວກເຮົາພິມ ທີ່ແທ້ຈິງ ສໍາລັບມັນ.

ເຊັ່ນດຽວກັນ, ສຳ ລັບເດັກທີສາມ, ສີ່ແລະຫ້າ, ມັນງ່າຍທີ່ຈະເຫັນວ່າພວກເຂົາສາມາດມີເຂົ້າ ໜົມ ທີ່ມີ ຈຳ ນວນຫຼາຍທີ່ສຸດຫຼັງຈາກແຈກຢາຍທີ່ດີທີ່ສຸດ.

ວິທີການ (Greedy)

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

ເພາະສະນັ້ນ, ຈຳ ນວນເຂົ້າ ໜົມ ທີ່ສາມາດຄອບຄອງໄດ້ໂດຍ ith ເດັກ = a [i] + ເຂົ້າ ໜົມ ພິເສດ. ຖ້າຄ່ານີ້ສູງກວ່າອົງປະກອບສູງສຸດໃນ array ກ່ອນການແຈກຢາຍ, ພວກເຮົາສາມາດສະຫຼຸບໄດ້ວ່າເດັກນ້ອຍຄົນນີ້ສາມາດມີເຂົ້າ ໜົມ ທີ່ມີເຂົ້າ ໜົມ ຫຼາຍທີ່ສຸດຫຼັງຈາກແຈກຢາຍ. ເນື່ອງຈາກພວກເຮົາເລືອກທີ່ຈະໃຫ້ເຂົ້າ ໜົມ ພິເສດທັງ ໝົດ ແກ່ອາຫານ ith ເດັກເທົ່ານັ້ນ, ວິທີການນີ້ແມ່ນ ໂລບ.

ເດັກນ້ອຍທີ່ມີ ຈຳ ນວນຕົວເລກທີ່ຍິ່ງໃຫຍ່ທີ່ສຸດຂອງ Leetcode Solution

ລະບົບວິເຄາະ

  1. ຊອກຫາຂອບເຂດສູງສຸດແລະເກັບມ້ຽນມັນເປັນ maxCandies
  2. ເລີ່ມຕົ້ນການໃສ່ເຫຼົ້າ ຜົນ array
  3. ດໍາເນີນການ loop ຈາກຈຸດເລີ່ມຕົ້ນຂອງຂບວນຈົນເຖິງທ້າຍຂອງມັນ:
    1. ຖ້າ ຈຳ ນວນເຂົ້າ ໜົມ ຊະນິດໃນປະຈຸບັນຂອງ ith ເດັກນ້ອຍແລະເຂົ້າ ໜົມ ພິເສດແມ່ນ ຫຼາຍກວ່າຫຼືເທົ່າກັບ maxCandies:
      1. ກຳ ນົດຜົນຂອງເດັກຄົນນີ້ເປັນ ທີ່ແທ້ຈິງ, ທີ່ບໍ່ຖືກຕ້ອງ ຖ້າບໍ່ດັ່ງນັ້ນ
  4. ພິມຜົນໄດ້ຮັບ

ການຈັດຕັ້ງປະຕິບັດວິທີການຄົ້ນຫາເດັກນ້ອຍດ້ວຍ ຈຳ ນວນເຂົ້າ ໜົມ ທີ່ໃຫຍ່ທີ່ສຸດ

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

vector <bool> kidsWithCandies(vector <int> &candies , int extraCandies)
{
    int n = candies.size() , maxCandies = 0;
    for(int i = 0 ; i < n ; i++)
        if(candies[i] > maxCandies)
            maxCandies = candies[i];


    vector <bool> result(n);
    for(int i = 0 ; i < n ; i++)
        result[i] = (candies[i] + extraCandies >= maxCandies);

    return result;
}


int main()
{
    vector <int> candies = {1 , 4 , 5 , 6 , 7};
    int extraCandies = 5;
    for(bool x : kidsWithCandies(candies , extraCandies))
        cout << (x ? "true" : "false") << " ";
    cout << '\n';
    return 0;
}

Java Program

class kids_with_candies
{
    public static void main(String args[])
    {
        int[] candies = {1 , 4 , 5 , 6 , 7};
        int extraCandies = 5;
        for(boolean x : kidsWithCandies(candies , extraCandies))
            System.out.print(x + " ");
    }


    static boolean[] kidsWithCandies(int[] candies , int extraCandies)
    {
        int n = candies.length , maxCandies = 0;
        for(int i = 0 ; i < n ; i++)
            if(candies[i] > maxCandies)
                maxCandies = candies[i];

        boolean[] result = new boolean[n];

        for(int i = 0 ; i < n ; i++)
            result[i] = (candies[i] + extraCandies >= maxCandies);

        return result;
    }
}
false true true true true

ການວິເຄາະທີ່ສັບສົນໃນການຊອກຫາເດັກນ້ອຍທີ່ມີ ຈຳ ນວນເຂົ້າ ໜົມ ຫລາຍທີ່ສຸດ

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

ໂອ (N), N = ຂະ ໜາດ ຂອງຂບວນ. ດັ່ງທີ່ພວກເຮົາຂ້າມອາເລທັງ ໝົດ ຄັ້ງດຽວ.

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

ໂອ (N), ໃນຂະນະທີ່ພວກເຮົາບັນທຶກຜົນໄດ້ຮັບຂອງເດັກທຸກຄົນໃນແຖວຕ່າງຫາກ.