Сообщения

Показаны сообщения с ярлыком "Жадный алгоритм"

Удалить и заработать

Источник: https://leetcode.com/problems/delete-and-earn/ Дан массив nums целых чисел. Из массива можно удалить эемент nums[i] и заработать nums[i] очков . После чего нужно удалить все элементы равные nums[i] - 1 или nums[i] + 1 . Перед проведением операци йдаления у вас 0 очков. Вернуть максимальное значение очков, которые можно заработать, применяя операцию "удалить и заработать", описанную выше. Пример 1: Дано: nums = [3,4,2] Результат: 6 Пояснение: Удялем и зарабатываем 4, затем 3 тоже удаляем, поскольку 3=4-1. Остается [2]. Удаляем 2 и зарабатываем +2. Итого 4+2=6. Пример 2: Дано : nums = [2,2,3,3,3,4] Результат : 9 Пояснение : Удаляем и зарабатываем 3. 2=3-1 и 4=3+1 - удаляем ВСЕ 2 и 4. Остается [3,3]. Удаляем и зарабатываем +3, но больше нет соседних значений (2 и 4). Остается [3]. Удалеям и зарабатываем ещё раз +3. Итого 3+3+3=9. Огранияения: 1 <= nums.length <= 2 * 10 4 1 <= nums[i] <= 10 4 Идея решения Заметим, что если в массиве есть дубл...

Фотокамеры в двоичном дереве

Изображение
Дано двоичное дерево, нам нужно установить в его узлах фотокамеры. Камера в каждом узле мониторит сам узел, его родителя и его непосредственных детей. Вычислить минимальное колчиество камер, которыми можно промониторить всё дерево. Пример 1: Дано: [0,0,null,0,0] Результат: 1 Пояснение: Одной камеры достаточно, чтобы промониторить все узлы дерева, если установить её так, как показано на рисунке. Пример 2: Дано: [0,0,null,0,null,0,null,null,0] Результат: 2 Пояснение: По крайней мере 2 камеры нужны, чтобы мониторить всё дерево. На рисунке показана однеа из конфигураций расположения камер. Примечания: Число узлов в дереве варбируется в интервале [1, 1000] . Все узлы дерева имеют значение 0 . Идея решения  Рассмотрим "внутренний" (не корневой и не листовой) узел в дереве. Он может мониториться камерой в родителе, в себе, в своих 2 детях. Итого: 4 узла задействованы. Рассмотрим корневой узел дерева.. Он монтирится двумя детьми и собой. Итого: 3 узла задействованы. Расммотрим...

Раздать печеньки детям

Допустим, вы - многодетный родитель и хотите угостить всех своих детей печеньками. Вы должны дать хотя бы одну печеньку каждому ребенку. Каждый ребенок обладает своим фактором жадности g i до печенек.  Фактор жадности - это минимальный размер печеньки, которой ребенок будет доволен. И у каждой печеньки есть свой размер s j . Если s j  >= g i , мы можем дать печеньку j ребенку i, и тот будет доволен. Ваша задача максимизировать число довольных детей и в качестве ответа выдать число довольных детей. Примечания: Фактор жадности всегда положителен. Каждый ребенок может взять только одну печеньку. Пример 1: Дано: [1,2,3], [1,1] Результат: 1 Пояснение: у вас 3 детей и 2 печеньки. Факторы эадности детей соответственно 1, 2, 3. Даже если у вас 2 печеньки, их размер равен 1, поэтому доволен останется только ребенок с фактором жадности 1. Пример 2: Дано: [1,2], [1,2,3] Результат: 2 Пояснение: У вас 2 детей (с фактором жадности 1 и 2) и 3 печеньки. У трёх печ...

Заправки

Источник : https://www.interviewbit.com/problems/gas-station/ Задача . Дано два массива A и B одинакового размера N. N - это число заправок расположенных на пути, который закольцовывается. Массив A показывает, сколько топлива хранится на каждой заправке i. У вас есть машина с беконечным баком. А в массиве B элемент i показывает, сколько топлива расходует ваша машина при переезде из точки i в i+1. Нужно вернуть индекс i заправки, начиная с которой вы можете объехать все заправки. Либо вернуть -1, если такого индекса не существует (с какой заправки не стратуй, всё равно останешься где-то без топлива). Пример. Input 1: A = [1, 2] B = [2, 1] Output 1: 1 Объяснение: Если вы стартуете с индекса 0, вы можете залить в бак A[0] = 1 единиц топлива. Но вам нужно B[0] = 2 единицы топлива, чтобы доехать до заправки с индексом 1. Если вы стартуете с заправки под индексом 1, вы можете залить в бак A[1] = 2 единицы топлива. И вам нужно B[1] = 1 топлива, ч...