Сложность: hard
Дан массив целых чисел target длины n. Начав с массива arr, состоящего из n единиц, вы можете выполнить следующую процедуру:
Пусть x будет суммой всех элементов, находящихся в вашем массиве.
Выберите индекс i так, чтобы 0 <= i < n, и установите значение arr в индексе i равным x.
Вы можете повторять эту процедуру столько раз, сколько потребуется.
Верните true, если возможно построить массив target из arr, в противном случае верните false.
Пример:
Input: target = [8,5]
Output: true
👨💻 Алгоритм:
1⃣Использование максимальной кучи (Max Heap) для отслеживания максимальных значений в target:
Сначала необходимо инициализировать кучу с максимальным приоритетом, чтобы всегда иметь доступ к наибольшему элементу в массиве target.
Вычислить сумму всех элементов в target и сохранить ее.
2⃣Повторение процесса переворота:
Извлечь наибольшее значение из кучи. Вычесть это значение из общей суммы.
Проверить несколько условий:
Если извлеченное значение равно 1 или общая сумма равна 1, вернуть true.
Если извлеченное значение меньше общей суммы, общая сумма равна 0, или извлеченное значение делится на общую сумму без остатка, вернуть false.
Остаток от деления наибольшего значения на общую сумму является новым значением, которое нужно вставить обратно в кучу. Обновить общую сумму.
3⃣Повторение цикла до достижения результата:
Повторять шаг 2 до тех пор, пока не будут выполнены условия выхода из цикла (возврат true или false).
😎 Решение:
using System;
using System.Collections.Generic;
public class Solution {
public bool IsPossible(int[] target) {
var pq = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b - a));
long total = 0;
foreach (var num in target) {
total += num;
pq.Enqueue(num, num);
}
while (pq.Peek() > 1) {
int maxVal = pq.Dequeue();
total -= maxVal;
if (maxVal < total || total == 0 || maxVal % total == 0) return false;
pq.Enqueue(maxVal % total, maxVal % total);
total += pq.Peek();
}
return true;
}
}
Ставь 👍 и забирай 📚 Базу знаний