Решение: построить целевой массив с несколькими суммами

LeetCode Solutions (161 серия деталей)

Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет

Проблема LeetCode #1354 (жестко): построить целевой массив с несколькими суммами

Описание:

( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++

Учитывая множество целых чисел цель Анкет Из стартового массива, A состоящий из всех 1 Вы можете выполнить следующую процедуру:

• пусть x Будьте суммой всех элементов в настоящее время в вашем массиве.
• Выберите индекс я , так что 0 и установить значение A в индексе я к x Анкет
• Вы можете повторить эту процедуру столько раз, сколько необходимо.

Возврат Истинный Если возможно построить цель массив от A В противном случае вернуть Ложный Анкет

Примеры:

Ограничения:

• N.length
• 1.length * 10^4
• 1 [i]^9

Идея:

( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++

Одна вещь, которую мы можем сразу же заметить: сумма элементов в A всегда будет больше, чем любой элемент A , так как A начинается со всех положительных чисел. Следовательно, сумма будет только расти, когда мы переживаем процесс решения. Это означает, что у нас будет только одна попытка поместить заданное число в его правильном месте.

Это также означает, что Последний Шаг всегда будет заключаться в том, чтобы урегулировать наибольшее значение целевого массива, что означает, что мы можем реконструировать природу A Прямо перед последним шагом. Оттуда нам придется продолжать иметь дело с самой большой оставшейся стоимостью, а также работать назад, пока мы не получим успех или не потерпим неудачу.

Поскольку нам придется иметь дело с целевыми значениями в порядке нисходящей стоимости, мы считаем, что мы должны использовать максимальная очередь приоритета или Max-Heap Структура для отслеживания целевых значений, особенно потому, что мы не заботимся об индексах значений.

Как только у нас есть все цель Значения, вставленные в очередь приоритета ( pq/heap ) и сумма Подсчитано, мы можем продолжить дело со значениями по порядку. На каждом этапе мы должны удалить значение максимума, вычислить значение его замены, а затем повторно включить эту замену обратно в пта . Если, в начале итерации, мы видим, что максимальное значение в PQ это 1 , тогда это означает, что все значения в пта являются 1 S, и мы должны вернуть истинность Анкет

С другой стороны, если мы обнаружим, что собираемся вставить число меньше, чем 1 в пта , мы знаем, что потерпели неудачу и должны вернуть false , как мы будем пройти предписанную начальную позицию.

Но на данный момент мы все еще получим Tle результат и должен будет оптимизировать еще немного. Рассмотрим ситуацию, в которой мы обрабатываем максимальное значение только для того, чтобы обнаружить, что мы собираемся повторно ввести число, которое является все еще максимальное значение. В некоторых краевых случаях может потребоваться тысячи итераций, чтобы полностью обработать это значение, чтобы мы могли перейти к другому, когда вся эта обработка может быть сделана более просто за один шаг.

Взять, к примеру, цель = [3,5,33] . Обычно мы удаляем 33 и вычислить его замену как 25 , тогда из 25 к 17 , Тогда 17 к 9 , тогда, наконец, 9 к 1 Анкет Каждый раз мы удаляем сумму всех оставшихся значений ( 3 + ) из текущего числа. В любом действующем целевом массиве, как мы отмечали в самом начале, максимальное значение должен Будьте больше, чем сумма оставшихся элементов, так как она пришла от этой суммы плюс значение, которое было заменено.

Это означает, что мы должны быть в состоянии удалить оставшуюся сумму ( 8 ) из нашего текущего максимального значения ( 33 ) столько раз, сколько мы можем, поскольку только остальные принесут нам ниже эту сумму. Это мы можем довольно легко достичь с Мод оператор что приведет к нашему заменяющему значению ( 33 % ) без необходимости итерации на каждом шаге.

Как отмечалось недавно, если мы обнаружим, что максимальное значение на самом деле меньше, чем оставшаяся сумма, то массив не должен быть действительным, и мы можем вернуть false Анкет Также, если num Должен быть 0 После применения оператора мода, тогда мы должны вернуть false , за исключением случая края, где сумма Анкет Альтернативно, мы могли бы вместо этого подтолкнуть сумма на PQ Intead of численность , что сразу же вызвет сбой во всех случаях, кроме края.

Реализация:

JavaScript’s Maxpriorityqueue () NPM удобен, но не очень эффективен. Пользователь Max-Heap Реализация более эффективна. Оба варианта включены ниже.

Python по умолчанию на Мин-Хеп , поэтому мы можем имитировать Max-Heap Изменив знак на каждом элементе, когда он вставлен и удален из кучи.

Код JavaScript:

( Прыгните к : Описание задачи Идея решения

w/maxpriorityqueue ():

var isPossible = function(target) {
    let pq = new MaxPriorityQueue({priority: x => x}), sum = 0
    for (let num of target) sum += num, pq.enqueue(num)
    while (pq.front().element !== 1) {
        let num = pq.dequeue().element
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, pq.enqueue(num || sum)
    }
    return true
};

w/max-heap:

var isPossible = function(target) {
    let heap = [,], sum = 0

    const heapify = val => {
        let i = heap.length, par = i >> 1, temp
        heap.push(val)
        while (heap[par] < heap[i]) {
            temp = heap[par], heap[par] = heap[i], heap[i] = temp
            i = par, par = i >> 1
        }
    }
    const extract = () => {
        if (heap.length === 1) return null
        let top = heap[1], left, right, temp,
            i = 1, child = heap[3] > heap[2] ? 3 : 2
        if (heap.length > 2) heap[1] = heap.pop()
        else heap.pop()
        while (heap[i] < heap[child]) {
            temp = heap[child], heap[child] = heap[i], heap[i] = temp
            i = child, left = i << 1, right = left + 1
            child = heap[right] > heap[left] ? right : left
        }
        return top
    }

    for (let num of target) sum += num, heapify(num)
    while (heap[1] !== 1) {
        let num = extract()
        sum -= num
        if (num <= sum || sum < 1) return false
        num %= sum, sum += num, heapify(num || sum)
    }
    return true
};

Код Python:

( Прыгните к : Описание задачи Идея решения

class Solution:
    def isPossible(self, target: List[int]) -> bool:
        heap = [-num for num in target]
        total = sum(target)
        heapify(heap)
        while heap[0] != -1:
            num = -heappop(heap)
            total -= num
            if num <= total or total < 1: return False
            num %= total
            total += num
            heappush(heap, -num or -total)
        return True

Код Java:

( Прыгните к : Описание задачи Идея решения

class Solution {
    public boolean isPossible(int[] target) {
        Queue pq = new PriorityQueue<>((a,b) -> b - a);
        int sum = 0;
        for (int num : target) {
            sum += num;
            pq.add(num);
        }
        while (pq.peek() != 1) {
            int num = pq.poll();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum;
            sum += num;
            pq.add(num > 0 ? num : sum);
        }
        return true;
    }
}

C ++ Код:

( Прыгните к : Описание задачи Идея решения

class Solution {
public:
    bool isPossible(vector& target) {
        priority_queue pq;
        unsigned int sum = 0;
        for (int num : target)
            sum += num, pq.push(num);
        while (pq.top() != 1) {
            int num = pq.top();
            pq.pop();
            sum -= num;
            if (num <= sum || sum < 1) return false;
            num %= sum, sum += num, pq.push(num ? num : sum);
        }
        return true;
    }
};

LeetCode Solutions (161 серия деталей)

Оригинал: “https://dev.to/seanpgallivan/solution-construct-target-array-with-multiple-sums-24d4”