Java教程

LeetCode517 超级洗衣机 Java

本文主要是介绍LeetCode517 超级洗衣机 Java,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
  • 题目:

    假设有 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 <= 104
    • 0 <= machines[i] <= 105

思路 :

  1. 贪心算法。算出衣服平均值,平均值非整数直接返回**-1**,高于平均值记为正数,低于记为负数,再将其相加取绝对值中的最大值即为最小操作数。

示例一:

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

结果:

在这里插入图片描述

这篇关于LeetCode517 超级洗衣机 Java的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!