517. Super Washing Machines

leetcode hard

#array#csharp#hard#leetcode#math#search

Task

У вас есть n супер стиральных машин, расположенных в одну линию. Изначально каждая стиральная машина содержит некоторое количество платьев или пуста.

За один ход вы можете выбрать любые m (1 <= m <= n) стиральные машины и одновременно передать одно платье из каждой выбранной машины в одну из её соседних стиральных машин.

Дан целочисленный массив machines, представляющий количество платьев в каждой стиральной машине слева направо по линии. Верните минимальное количество ходов, необходимых для того, чтобы во всех стиральных машинах стало одинаковое количество платьев. Если это невозможно, верните -1.

Пример:

Input: machines = [1,0,5]

Output: 3

Explanation:

1st move: 1 0 <-- 5 => 1 1 4

2nd move: 1 <-- 1 <-- 4 => 2 1 3

3rd move: 2 1 <-- 3 => 2 2 2

C# solution

matched/original

public class Solution {
    public int FindMinMoves(int[] machines) {
        int n = machines.Length;
        int dressTotal = 0;
        foreach (int m in machines) dressTotal += m;
        if (dressTotal % n != 0) return -1;
        int dressPerMachine = dressTotal / n;
        for (int i = 0; i < n; i++) machines[i] -= dressPerMachine;
        int currSum = 0, maxSum = 0, res = 0;
        foreach (int m in machines) {
            currSum += m;
            maxSum = Math.Max(maxSum, Math.Abs(currSum));
            res = Math.Max(res, Math.Max(maxSum, m));
        }
        return res;
    }
}

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 FindMinMoves(vector<int>& machines) {
        int n = machines.size();
        int dressTotal = 0;
        foreach (int m in machines) dressTotal += m;
        if (dressTotal % n != 0) return -1;
        int dressPerMachine = dressTotal / n;
        for (int i = 0; i < n; i++) machines[i] -= dressPerMachine;
        int currSum = 0, maxSum = 0, res = 0;
        foreach (int m in machines) {
            currSum += m;
            maxSum = max(maxSum, abs(currSum));
            res = max(res, max(maxSum, m));
        }
        return res;
    }
}

Java solution

matched/original

class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length, dressTotal = 0;
        for (int m : machines) dressTotal += m;
        if (dressTotal % n != 0) return -1;

        int dressPerMachine = dressTotal / n;
        for (int i = 0; i < n; i++) machines[i] -= dressPerMachine;

        int currSum = 0, maxSum = 0, res = 0;
        for (int m : machines) {
            currSum += m;
            maxSum = Math.max(maxSum, Math.abs(currSum));
            res = Math.max(res, Math.max(maxSum, m));
        }
        return res;
    }
}

JavaScript solution

matched/original

var findMinMoves = function(machines) {
    const n = machines.length
    const dressTotal = machines.reduce((a, b) => a + b, 0)
    if (dressTotal % n !== 0) return -1

    const dressPerMachine = Math.floor(dressTotal / n)
    for (let i = 0; i < n; i++) {
        machines[i] -= dressPerMachine
    }

    let currSum = 0, maxSum = 0, res = 0
    for (const m of machines) {
        currSum += m
        maxSum = Math.max(maxSum, Math.abs(currSum))
        res = Math.max(res, Math.max(maxSum, m))
    }
    return res
}

Python solution

matched/original

class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        n = len(machines)
        dressTotal = sum(machines)
        if dressTotal % n != 0:
            return -1
        
        dressPerMachine = dressTotal // n
        machines = [m - dressPerMachine for m in machines]

        currSum = maxSum = res = 0
        for m in machines:
            currSum += m
            maxSum = max(maxSum, abs(currSum))
            res = max(res, maxSum, m)
        
        return res

Go solution

matched/original

func findMinMoves(machines []int) int {
    n := len(machines)
    dressTotal := 0
    for _, m := range machines {
        dressTotal += m
    }
    if dressTotal % n != 0 {
        return -1
    }

    dressPerMachine := dressTotal / n
    for i := range machines {
        machines[i] -= dressPerMachine
    }

    currSum, maxSum, res := 0, 0, 0
    for _, m := range machines {
        currSum += m
        maxSum = max(maxSum, abs(currSum))
        res = max(res, max(maxSum, m))
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Explanation

Algorithm

Проверьте, можно ли решить задачу: длина массива machines должна быть делителем суммы элементов массива machines. Если нет, верните -1. Вычислите количество платьев, которое должно быть в каждой машине: dresses_per_machine = sum(machines) / len(machines). Нормализуйте задачу, заменив количество платьев в каждой машине на количество платьев, которые нужно удалить из этой машины (может быть отрицательное значение).

Инициализируйте переменные curr_sum, max_sum и res нулем. Итеративно пройдитесь по всем машинам m в массиве machines, обновляя curr_sum и max_sum на каждом шагу: curr_sum += m, max_sum = max(max_sum, abs(curr_sum)).

Обновляйте результат res на каждом шагу: res = max(res, max_sum, m). Верните res.

😎