leetcode
leetcode 3001 ~ 3050
宝石补给

宝石补给

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 35 ms, 内存: 17.6 MB


/*
 * 思路:
 * 1. 使用Java Stream来简化数组遍历和最大最小值计算。
 * 2. 对每次操作更新宝石数组。
 * 3. 最后通过Stream找到最大值和最小值并计算差值。
 */
import java.util.Arrays;

public class GemDifferenceStream {
    public int getMaxMinGemDifference(int[] gem, int[][] operations) {
        for (int[] operation : operations) {
            int x = operation[0];
            int y = operation[1];
            int halfGem = gem[x] / 2;
            gem[x] -= halfGem;
            gem[y] += halfGem;
        }
        int maxGem = Arrays.stream(gem).max().orElse(0);
        int minGem = Arrays.stream(gem).min().orElse(0);
        return maxGem - minGem;
    }
}

解释

方法:

本题解首先遍历所有的宝石赠送操作,对每次操作,将赠送者的宝石数减半(向下取整),并将这一半的宝石数加给接收者。操作完成后,通过遍历一次宝石数组来找出拥有最多宝石和最少宝石的勇者,计算二者的宝石数量之差,这就是最终的结果。

时间复杂度:

O(m + n)

空间复杂度:

O(n)

代码细节讲解

🦆
在`赠送者将自己一半的宝石(需向下取整)赠送给接收者`的操作中,如果赠送者的宝石数为奇数,赠送后的剩余宝石计算是否正确考虑了所有情况?
是的,计算正确。使用整数除法(//)自动向下取整。例如,如果赠送者有5颗宝石,赠送的宝石数为5 // 2 = 2颗,赠送后剩余3颗。这种操作正确处理了奇数和偶数宝石数的情况,确保了赠送者总是保留至少一半的宝石(向下取整)。
🦆
操作数组`operations`是否可以为空?如果是空数组,程序是否能够正确处理并返回初始宝石数组中的最大和最小宝石数之差?
是的,操作数组`operations`可以为空。如果是空数组,循环体内的代码不会执行,宝石数组保持不变。随后的最大值和最小值计算会在未修改的宝石数组上进行,正确返回初始宝石数组中的最大和最小宝石数之差。
🦆
在遍历宝石数组以找出最大值和最小值时,初始化的`down`变量设置为100000,这种硬编码的方式是否有潜在的问题?例如数组中宝石数超过了100000怎么办?
是的,这种硬编码的方式存在潜在问题。如果数组中的宝石数超过100000,那么`down`变量初始化为100000就无法正确反映数组中真实的最小宝石数。更合理的初始化应该是设置`down`为宝石数组中的第一个元素,或使用Python的`float('inf')`来确保任何宝石数都小于初始值。

相关问题