宝石补给

标签: 数组 模拟

难度: Easy

欢迎各位勇者来到力扣新手村，在开始试炼之前，请各位勇者先进行「宝石补给」。 每位勇者初始都拥有一些能量宝石， `gem[i]` 表示第 `i` 位勇者的宝石数量。现在这些勇者们进行了一系列的赠送，`operations[j] = [x, y]` 表示在第 `j` 次的赠送中 第 `x` 位勇者将自己一半的宝石（需向下取整）赠送给第 `y` 位勇者。 在完成所有的赠送后，请找到拥有**最多**宝石的勇者和拥有**最少**宝石的勇者，并返回他们二者的宝石数量**之差**。 **注意：** - 赠送将按顺序逐步进行。 **示例 1：** >输入：`gem = [3,1,2], operations = [[0,2],[2,1],[2,0]]` > >输出：`2` > >解释： >第 1 次操作，勇者 `0` 将一半的宝石赠送给勇者 `2`， `gem = [2,1,3]` >第 2 次操作，勇者 `2` 将一半的宝石赠送给勇者 `1`， `gem = [2,2,2]` >第 3 次操作，勇者 `2` 将一半的宝石赠送给勇者 `0`， `gem = [3,2,1]` >返回 3 - 1 = 2 **示例 2：** >输入：`gem = [100,0,50,100], operations = [[0,2],[0,1],[3,0],[3,0]]` > >输出：`75` > >解释： >第 1 次操作，勇者 `0` 将一半的宝石赠送给勇者 `2`， `gem = [50,0,100,100]` >第 2 次操作，勇者 `0` 将一半的宝石赠送给勇者 `1`， `gem = [25,25,100,100]` >第 3 次操作，勇者 `3` 将一半的宝石赠送给勇者 `0`， `gem = [75,25,100,50]` >第 4 次操作，勇者 `3` 将一半的宝石赠送给勇者 `0`， `gem = [100,25,100,25]` >返回 100 - 25 = 75 **示例 3：** >输入：`gem = [0,0,0,0], operations = [[1,2],[3,1],[1,2]]` > >输出：`0` **提示：** - `2 <= gem.length <= 10^3` - `0 <= gem[i] <= 10^3` - `0 <= operations.length <= 10^4` - `operations[i].length == 2` - `0 <= operations[i][0], operations[i][1] < gem.length`

Submission

运行时间: 35 ms

内存: 17.6 MB

class Solution:
    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:
        for ope in operations:
            d = gem[ope[0]] // 2
            gem[ope[0]] -= d
            gem[ope[1]] += d

        up, down = 0, 100000
        for g in gem:
            up = max(g, up)
            down = min(g, down)
        return up - down

Explain

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

时间复杂度: O(m + n)

空间复杂度: O(n)

class Solution:
    def giveGem(self, gem: List[int], operations: List[List[int]]) -> int:
        # 遍历所有操作
        for ope in operations:
            d = gem[ope[0]] // 2  # 计算赠送者要赠送的宝石数（取半并向下取整）
            gem[ope[0]] -= d  # 减少赠送者的宝石数
            gem[ope[1]] += d  # 增加接收者的宝石数

        # 初始化最大宝石数和最小宝石数
        up, down = 0, 100000
        # 找出拥有最多和最少宝石的勇者
        for g in gem:
            up = max(g, up)  # 更新最大宝石数
            down = min(g, down)  # 更新最小宝石数
        return up - down  # 返回最大和最小宝石数的差

Explore

是的，计算正确。使用整数除法（//）自动向下取整。例如，如果赠送者有5颗宝石，赠送的宝石数为5 // 2 = 2颗，赠送后剩余3颗。这种操作正确处理了奇数和偶数宝石数的情况，确保了赠送者总是保留至少一半的宝石（向下取整）。

是的，操作数组`operations`可以为空。如果是空数组，循环体内的代码不会执行，宝石数组保持不变。随后的最大值和最小值计算会在未修改的宝石数组上进行，正确返回初始宝石数组中的最大和最小宝石数之差。

是的，这种硬编码的方式存在潜在问题。如果数组中的宝石数超过100000，那么`down`变量初始化为100000就无法正确反映数组中真实的最小宝石数。更合理的初始化应该是设置`down`为宝石数组中的第一个元素，或使用Python的`float('inf')`来确保任何宝石数都小于初始值。