超级洗衣机

517. 超级洗衣机

假设有 n 台超级洗衣机放在同一排上。开始的时候，每台洗衣机内可能有一定量的衣服，也可能是空的。

在每一步操作中，你可以选择任意 m (1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。

给定一个整数数组 machines 代表从左至右每台洗衣机中的衣物数量，请给出能让所有洗衣机中剩下的衣物的数量相等的 最少的操作步数 。如果不能使每台洗衣机中衣物的数量相等，则返回 -1 。

示例 1：

输入：machines = [1,0,5]
输出：3
解释：
第一步:    1     0 <-- 5    =>    1     1     4
第二步:    1 <-- 1 <-- 4    =>    2     1     3    
第三步:    2     1 <-- 3    =>    2     2     2

示例 2：

输入：machines = [0,3,0]
输出：2
解释：
第一步:    0 <-- 3     0    =>    1     2     0    
第二步:    1     2 --> 0    =>    1     1     1

示例 3：

输入：machines = [0,2,0]
输出：-1
解释：
不可能让所有三个洗衣机同时剩下相同数量的衣物。

提示：

n == machines.length
1 <= n <= 10⁴
0 <= machines[i] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int findMinMoves(vector<int>& machines) { } };

javascript 解法, 执行用时: 68 ms, 内存消耗: 43.9 MB, 提交时间: 2023-09-21 15:08:22

/**
 * @param {number[]} machines
 * @return {number}
 */
var findMinMoves = function(machines) {
    const tot = eval(machines.join('+'));
    const n = machines.length;
    if (tot % n !== 0) {
        return -1;
    }
    let avg = Math.floor(tot / n);
    let ans = 0, sum = 0;
    for (let num of machines) {
        num -= avg;
        sum += num;
        ans = Math.max(ans, Math.max(Math.abs(sum), num));
    }
    return ans;
};

golang 解法, 执行用时: 4 ms, 内存消耗: 4 MB, 提交时间: 2023-09-21 15:08:05

func findMinMoves(machines []int) (ans int) {
    tot := 0
    for _, v := range machines {
        tot += v
    }
    n := len(machines)
    if tot%n > 0 {
        return -1
    }
    avg := tot / n
    sum := 0
    for _, num := range machines {
        num -= avg
        sum += num
        ans = max(ans, max(abs(sum), num))
    }
    return
}

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

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

java 解法, 执行用时: 2 ms, 内存消耗: 42.3 MB, 提交时间: 2023-09-21 15:07:51

class Solution {
    public int findMinMoves(int[] machines) {
        int tot = Arrays.stream(machines).sum();
        int n = machines.length;
        if (tot % n != 0) {
            return -1;
        }
        int avg = tot / n;
        int ans = 0, sum = 0;
        for (int num : machines) {
            num -= avg;
            sum += num;
            ans = Math.max(ans, Math.max(Math.abs(sum), num));
        }
        return ans;
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 13.1 MB, 提交时间: 2023-09-21 15:07:23

class Solution {
public:
    int findMinMoves(vector<int> &machines) {
        int tot = accumulate(machines.begin(), machines.end(), 0);
        int n = machines.size();
        if (tot % n) {
            return -1;
        }
        int avg = tot / n;
        int ans = 0, sum = 0;
        for (int num: machines) {
            num -= avg;
            sum += num;
            ans = max(ans, max(abs(sum), num));
        }
        return ans;
    }
};

python3 解法, 执行用时: 64 ms, 内存消耗: 16.8 MB, 提交时间: 2023-09-21 15:07:16

'''
贪心
'''
class Solution:
    def findMinMoves(self, machines: List[int]) -> int:
        tot = sum(machines)
        n = len(machines)
        if tot % n:
            return -1
        avg = tot // n
        ans, s = 0, 0
        for num in machines:
            num -= avg
            s += num
            ans = max(ans, abs(s), num)
        return ans

上一题

下一题

详情