当前位置：首页 > article >正文

LeetCode题练习与总结：超级洗衣机--517

article 2025/1/6 7:12:08

一、题目描述

假设有 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^4
0 <= machines[i] <= 10^5

二、解题思路

首先计算所有洗衣机中衣物的总数，如果总数不能被洗衣机数量整除，则返回 -1，因为无法使每台洗衣机中衣物的数量相等。
如果可以整除，计算出每台洗衣机应有的衣物数量，记为 avg。
遍历洗衣机数组，对于每台洗衣机，计算其与 avg 的差值，如果差值为正，说明需要将衣物移出；如果差值为负，说明需要将衣物移入。
遍历过程中，维护两个变量：sum 表示当前遍历到的洗衣机与 avg 的累积差值，maxMove 表示使所有洗衣机中衣物数量相等所需的最大操作步数。
对于每台洗衣机，如果 sum 的绝对值大于 maxMove，则更新 maxMove。
最后返回 maxMove。

三、具体代码

class Solution {
    public int findMinMoves(int[] machines) {
        int total = 0;
        for (int machine : machines) {
            total += machine;
        }
        
        int n = machines.length;
        if (total % n != 0) {
            return -1;
        }
        
        int avg = total / n;
        int sum = 0, maxMove = 0;
        for (int machine : machines) {
            int diff = machine - avg;
            sum += diff;
            maxMove = Math.max(maxMove, Math.max(Math.abs(sum), diff));
        }
        
        return maxMove;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

计算所有洗衣机中衣物的总数：我们遍历了整个 machines 数组一次，所以这部分的时间复杂度是 O(n)，其中 n 是数组的长度。
判断是否可以整除：这是一个常数时间操作，所以时间复杂度是 O(1)。
遍历洗衣机数组，计算差值并更新最大操作步数：我们再次遍历了整个 machines 数组，因此这部分的时间复杂度也是 O(n)。

将上述步骤合并，总的时间复杂度是 O(n) + O(1) + O(n)，简化后为 O(n)。

2. 空间复杂度

total 变量用于存储衣物的总数，这是一个固定大小的整数，所以空间复杂度是 O(1)。
n 变量用于存储洗衣机数量，这也是一个固定大小的整数，空间复杂度是 O(1)。
avg 变量用于存储每台洗衣机应有的衣物数量，同样是一个固定大小的整数，空间复杂度是 O(1)。
sum 变量用于存储当前累积的差值，空间复杂度是 O(1)。
maxMove 变量用于存储最大操作步数，空间复杂度是 O(1)。

在整个算法过程中，我们没有使用额外的数据结构来存储大量数据，所有的变量都是固定大小的，因此总的空间复杂度是 O(1)。

五、总结知识点

数组的遍历：
- 使用增强型 for 循环（for-each 循环）来遍历数组 machines，这是 Java 中遍历数组元素的一种简洁方式。
基本算术运算：
- 使用加法运算符 += 来累加数组中所有洗衣机的衣物总数。
- 使用取模运算符 % 来检查衣物总数是否能被洗衣机数量整除。
条件判断：
- 使用 if 语句来检查衣物总数是否能被洗衣机数量整除，如果不能，则返回 -1。
整数除法：
- 使用整数除法 / 来计算每台洗衣机应有的平均衣物数量。
变量声明和初始化：
- 声明并初始化了几个整型变量 total、n、avg、sum 和 maxMove，用于在算法过程中存储中间结果。
数学函数的使用：
- 调用 Math.max() 方法来找出累积差值 sum 和当前差值 diff 中的最大值，并更新 maxMove。
绝对值：
- 使用 Math.abs() 方法来计算累积差值 sum 的绝对值，以便正确地更新 maxMove。
返回值：
- 方法 findMinMoves 返回一个整数值，表示使所有洗衣机中衣物数量相等所需的最大操作步数。