糖果Leetcode解决方案数量最多的孩子


难度级别 易得奖学金
经常问 亚马逊 彭博
排列

在“糖果数量最多的孩子”问题中,我们得到了一个整数数组,这些整数代表一些孩子得到的巧克力数量以及可以任何方式分配的一些额外糖果。 现在,我们需要找到:

  • 每个孩子都可以吃最多数量的巧克力吗? 分配后(以多数或共同)?

我们需要以布尔向量的形式来打印这种可能性。

使用案列

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

说明

第一个孩子:即使我们付出了全部 多给第一个孩子的糖果,它将有6个<7(第5个孩子)的糖果。 所以,我们打印 false 为了它。

第二个孩子:我们全力以赴 给这个孩子额外的糖果,使它变得重要 9 > 7(第5个孩子)。 所以,我们打印 true 为了它。

同样,对于第三,第四和第五个孩子,很容易看出他们在优化分配之后可以拥有最多的糖果。

进场(贪婪)

在这个问题上,我们独立于分配额外糖果的选择。 这 最佳 决定任何孩子的方法是给孩子所有额外的糖果,然后检查所需的条件。 考虑,我们需要找到任何结果 第i个 孩子。 现在,可以分配给它的最大糖果数量等于总的额外糖果数量。

因此,糖果可以拥有的糖果总数 第i个 child = a [i] +额外的糖果。 如果此值大于 排列 在分配之前,我们可以得出结论,这个孩子在分配之后可以拥有最多的糖果。 由于我们选择将所有多余的糖果给 第i个 只是孩子,这种方法是 贪婪.

糖果Leetcode解决方案数量最多的孩子

算法

  1. 查找数组的最大值并将其存储为 最大糖果
  2. 初始化一个布尔值 导致 排列
  3. 从数组的开头到结尾运行一个循环:
    1. 如果当前的糖果数量 第i个 儿童+额外的糖果是 大于或等于 maxCandies:
      1. 将此孩子的结果设置为 true, false 除此以外
  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程序

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 =数组的大小。 当我们遍历整个数组一次时。

空间复杂度

上),因为我们将每个孩子的结果保存在单独的数组中。