leetcode
leetcode 1551 ~ 1600
移除石子的最大得分

移除石子的最大得分

难度:

标签:

题目描述

代码结果

运行时间: 30 ms, 内存: 15.9 MB


/*
 * Problem Description: 
 * You are playing a single-player game with three piles of stones, labeled a, b, and c.
 * In each turn, you can remove one stone from any two different non-empty piles and gain 1 point.
 * The game ends when two or more piles are empty. 
 * The task is to find the maximum score you can achieve.
 * 
 * Approach: 
 * - Use Java Streams to handle the sorting and operations on the piles.
 * - The optimal strategy remains the same as in the previous solution.
 */

import java.util.Arrays;

public class MaxScoreStream {
    public int maximumScore(int a, int b, int c) {
        int[] stones = {a, b, c};
        // Sort the array using Streams
        stones = Arrays.stream(stones).sorted().toArray();
        int maxScore = 0;
        while (stones[1] > 0) {
            // Reduce the two largest piles
            stones[2]--;
            stones[1]--;
            maxScore++;
            // Sort again using Streams
            stones = Arrays.stream(stones).sorted().toArray();
        }
        return maxScore;
    }
}

解释

方法:

首先对三堆石子的数量进行排序,确保我们可以方便地进行比较和操作。如果最小的两堆石子数量之和小于第三堆的数量,那么我们只能进行的最大回合数是这两堆石子的总和,因为一旦这两堆石子被取完,游戏就会结束。如果不是这种极端情况,游戏可以持续到每堆石子都接近被取完,此时最大回合数就是所有石子数量的一半,因为每次操作都会从两堆中各取一个石子。

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在解决这个问题时首先选择对石子的数量进行排序?
排序石子的数量可以简化比较和决策过程。通过保证石子数量从小到大排序,可以更容易地识别并处理不同的操作策略。例如,当最小的两堆石子总和小于第三堆时,直接计算得分变得简单。此外,排序后的逻辑更清晰,代码也更易于理解和维护。
🦆
在排序后的数组中,检查`stones[0] + stones[1] < stones[2]`的逻辑是基于什么考虑?
这个检查是基于游戏规则,每次操作必须从两个不同的堆中各取出一个石子。当最小的两堆石子总和小于第三堆时,意味着这两堆石子会先被取完,之后无法继续操作。因此,这种情况下的最大回合数受到最小两堆的总量限制,检查这个条件可以直接得出最大回合数。
🦆
为何在`stones[0] + stones[1] < stones[2]`的情况下,最大分数是`stones[0] + stones[1]`,而不考虑从最大堆中取石子的可能性?
由于每次操作需要从两个不同的堆中取出石子,一旦任何一堆石子被取完,游戏就无法继续进行。在`stones[0] + stones[1] < stones[2]`的情况下,最小的两堆石子总和小于第三堆,这意味着在第三堆还有剩余石子时,最小的两堆就已经为空,无法继续操作。因此,最大回合数仅由这两堆的总和决定,无论第三堆中有多少石子剩余。
🦆
在返回`sum(stones) // 2`时,是否有考虑到所有堆最终可能无法完全平分的情况,如何确保每次操作都合法?
返回`sum(stones) // 2`是基于每次操作减少两颗石子的规则。这个策略假设在游戏过程中可以持续从两个不同的堆中取石子,直至石子总数减半。这种计算方式考虑到了总石子数是奇数的情况,最终可能会剩下一颗石子。在实际操作中,这意味着最后一次可能只能从两堆中取出一颗石子,如果总数为奇数。因此,使用`sum(stones) // 2`确保了所有操作在石子数为偶数的情况下合法,并且考虑到了石子数为奇数时的实际情况。

相关问题