Для сегодняшнего алгоритма мы собираемся написать функцию с именем maximumToys
, которая будет принимать один массив prices
и одно целое число k
в качестве входных данных.
Вы покупаете кучу игрушек в магазине игрушек, и у вас ограниченный бюджет. Вы хотите определить максимальное количество игрушек, которое вы можете купить, не выходя за рамки бюджета. Цель функции - вывести количество игрушек, которые вы можете купить, не выходя за рамки бюджета. Вот пример:
let prices = [2,3,4,6]; let k = 12;
В приведенном выше примере есть четыре игрушки, доступные по разным ценам. Если мы посмотрим на массив и посчитаем, сколько предметов мы можем купить, не превышая 12 долларов, мы увидим, что можем позволить себе купить не более 3 игрушек.
Мы складываем стоимость каждой игрушки, чтобы убедиться, что стоимость следующей игрушки не вынуждает нас превышать бюджет.
prices = 0 + 2 // 2 prices = 2 + 3 // 5 prices = 5 + 4 // 9 prices = 9 + 6 // 15 STOP. We will go $3 overbudget.
Функция вернет 3
.
Теперь переходим к написанию той же задачи в коде.
let spent = 0; let count = 0;
Переменная spent
показывает, сколько денег мы потратили на игрушки. Мы будем использовать эту переменную и сравнивать ее с нашим вводом k
, чтобы убедиться, что мы в рамках бюджета.
Переменная count
содержит количество игрушек, которые мы можем купить.
Затем мы сортируем наш входной массив prices
, потому что будет легче узнать максимальное количество игрушек, которое мы можем получить, если отсортировать массив в порядке возрастания.
prices.sort(function(a,b){ return a - b; });
Затем мы перебираем наш массив prices
с помощью цикла for..of. Цикл for… of аналогичен циклу for, но разница в том, что вы объявляете имя переменной для итерируемых элементов. Это позволяет получать элементы в массиве по назначенному имени переменной вместо использования индексной нотации, как в цикле for.
for(let toy of prices){ spent += toy; if(spent >= k){ return count; } count++; }
Внутри цикла for… of мы добавляем цены toy
к нашей переменной spent
. Мы также проверяем, не превышает ли потраченная нами сумма нашего бюджета k
. Если да, то завершаем цикл и возвращаем количество купленных игрушек. Если это не так, мы продолжаем и увеличиваем счетную переменную.
Мы проверяем нашу spent
переменную после добавления цены каждой игрушки, чтобы убедиться, что мы все еще в рамках бюджета, прежде чем включать эту игрушку в нашу count
переменную.
На этом наша работа завершена. Вот остальной код:
function maximumToys(prices, k) { let spent = 0; let count = 0; prices.sort(function(a,b){ return a - b; }); for(let toy of prices){ spent += toy; if(spent >= k){ return count; } count++; } }
Если вы нашли этот алгоритм полезным, ознакомьтесь с другими моими недавними решениями для алгоритмов JavaScript: