[算法练习及思路-leetcode每日一题(Java解法)]No517.超级洗衣机

题号:no517

题目:超级洗衣机

题目描述

假设有 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   

示例 2：

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

提示：

• n == machines.length

• 1 <= n <= 104

• 0 <= machines[i] <= 105

思路

1.这道题一定要弄清楚题意!在每一步操作中，你可以选择任意m(1 <= m <= n) 台洗衣机，与此同时将每台洗衣机的一件衣服送到相邻的一台洗衣机。 这句话的意思要弄明白,首先你的一次操作一定只能将一个洗衣机的一件衣服进行左移右移,但是可以想象 他是有传递性的,比如你想将三号洗衣机的衣服移动到一号,其实就是将3号->2号->1号

2.首先弄清楚题目后,这里我们不难理解,衣服总数必须均分给洗衣机,否则返回-1.均分的结果是target=sum/n;

3.所以我们可以使用贪心的策略,仔细想想,如果有一个洗衣机特别多衣服,导致其他的都比target要低,那么就由这一台洗衣机往两边发就行,假设这台洗衣机为i,这种时候就是machine[i]-target操作数就行,就直接将里面的多出来的衣服全部分给左右两边

4.还有种情况,就是每个洗衣机可能超过target也有可能低于target,那么假设当前位置为i,我们从左往右遍历,用一个diff做统计数,计算每一台洗衣机需要的衣服数的和,每一台洗衣机的需要的衣服是machine[i]-target,当前位置machine[i]-target>0说明能往两边分衣服,如果machine[i]-target<0表示需要从两边拿衣服,我们吧1到i这i个洗衣机看做一组,他们每个位置的machine[i]-target的和diff就是这i个洗衣机需要的右边i+1到n个洗衣机需要的操作数diff,如果diff小于0说明需要从i+1台机器到n台机器拿过来diff件衣服,如果diff大于0说明要往i+1台机器到n台机器送过去diff件衣服,操作数是Math.abs(diff).

5.也就是说res = Math.max(res,Math.max(Math.abs(diff),machines[i]-target));是用来维护操作数的,分为上个位置得到的最小操作数,当前位置1到i台机器作为分组一需要的diff(i+1到n台机器作为分组2,假设当前位置能直接往两边输送完毕的操作数

解题代码

class Solution {
    public int findMinMoves(int[] machines) {
        int n = machines.length;
        int sum = 0;
        for(int i = 0;i<machines.length;i++) {
            sum+=machines[i];
        }
        // 如果不能均分直接返回-1
        if(sum%n!=0) return -1;
        int target = sum/n;
        int diff = 0;
        int res = 0;
        for(int i = 0;i<n;i++) {
            // 获取当前位置需要的衣服
            diff += machines[i]-target;
            // 三个状态,1,res,上个状态的最小操作数,2,Math.max(Math.abs(diff))当前组需要的最小操作数,3,当前位置能够往两遍输送的最衣服数量
            res = Math.max(res,Math.max(Math.abs(diff),machines[i]-target));
        }
        return res;


    }
}

题外话求关注

欢迎大佬们关注小弟的博客https://blog.csdn.net/qq_41522089