1196. How Many Apples Can You Put into the Basket

leetcode easy

#array#csharp#easy#hash-table#heap#leetcode#sort

Task

У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.

Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину.

Пример:

Input: weight = [100,200,150,1000]

Output: 4

Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.

C# solution

matched/original

public class Solution {
    public int MaxNumberOfApples(int[] weight) {
        var heap = new SortedSet<int>(weight);
        int apples = 0, units = 0;
        foreach (var w in heap) {
            if (units + w <= 5000) {
                units += w;
                apples++;
            } else {
                break;
            }
        }
        return apples;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MaxNumberOfApples(vector<int>& weight) {
        var heap = new SortedSet<int>(weight);
        int apples = 0, units = 0;
        foreach (var w in heap) {
            if (units + w <= 5000) {
                units += w;
                apples++;
            } else {
                break;
            }
        }
        return apples;
    }
}

Java solution

matched/original

class Solution {
    public int maxNumberOfApples(int[] arr) {
        List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());
        Queue<Integer> heap = new PriorityQueue<>(list);

        int apples = 0, units = 0;

        while (!heap.isEmpty() && units + heap.peek() <= 5000) {
            units += heap.remove();
            apples += 1;
        }
        return apples;
    }
}

JavaScript solution

matched/original

class Solution {
    maxNumberOfApples(weight) {
        weight.sort((a, b) => a - b);
        let apples = 0, units = 0;

        for (const w of weight) {
            if (units + w <= 5000) {
                units += w;
                apples++;
            } else {
                break;
            }
        }
        return apples;
    }
}

Explanation

Algorithm

Преобразование массива в мин-кучу:

Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.

Инициализация переменных:

Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.

Добавление яблок в корзину:

Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:

Увеличивайте apples на 1.

Увеличивайте units на значение, извлеченное из кучи.

😎