令牌放置

难度: Medium

你的初始能量为 power，初始分数为 0，只有一包令牌以整数数组 tokens 给出。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。

你的目标是通过有策略地使用这些令牌以 最大化 总分数。在一次行动中，你可以用两种方式中的一种来使用一个 未被使用的 令牌（但不是对同一个令牌使用两种方式）：

朝上：如果你当前至少有 tokens[i] 点能量，可以使用令牌 i ，失去 tokens[i] 点能量，并得到 1 分。
朝下：如果你当前至少有 1 分，可以使用令牌 i ，获得 tokens[i] 点能量，并失去 1 分。

在使用任意数量的令牌后，返回我们可以得到的最大分数。

示例 1：

输入：tokens = [100], power = 50
输出：0
解释：因为你的初始分数为 0，无法使令牌朝下。你也不能使令牌朝上因为你的能量（50）比 tokens[0] 少（100）。

示例 2：

输入：tokens = [200,100], power = 150
输出：1
解释：使令牌 1 正面朝上，能量变为 50，分数变为 1 。
不必使用令牌 0，因为你无法使用它来提高分数。可得到的最大分数是 1。

示例 3：

输入：tokens = [100,200,300,400], power = 200
输出：2
解释：按下面顺序使用令牌可以得到 2 分：
1. 令牌 0 (100)正面朝上，能量变为 100 ，分数变为 1
2. 令牌 3 (400)正面朝下，能量变为 500 ，分数变为 0
3. 令牌 1 (200)正面朝上，能量变为 300 ，分数变为 1
4. 令牌 2 (300)正面朝上，能量变为 0 ，分数变为 2

可得的最大分数是 2。

提示：

0 <= tokens.length <= 1000
0 <= tokens[i], power < 10⁴

Submission

运行时间: 26 ms

内存: 16.1 MB

from typing import List

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()  # Sort the tokens in ascending order
        score = 0  # Initialize the score to 0
        max_score = 0  # Variable to keep track of the maximum score
        left = 0  # Pointer to the leftmost token
        right = len(tokens) - 1  # Pointer to the rightmost token

        while left <= right:
            # If we have enough power to use the leftmost token, use it and increase the score
            if power >= tokens[left]:
                power -= tokens[left]
                score += 1
                left += 1
                max_score = max(max_score, score)
            # If we have a positive score and want to gain more power, use the rightmost token
            elif score > 0:
                power += tokens[right]
                score -= 1
                right -= 1
            # If none of the above conditions are met, we can't make any more moves
            else:
                break

        return max_score

solution = Solution()

print(solution.bagOfTokensScore([100], 50))  # Output: 0
print(solution.bagOfTokensScore([100, 200], 150))  # Output: 1
print(solution.bagOfTokensScore([100, 200, 300, 400], 200))  # Output: 2

Explain

本题解采用了贪心算法的思想，首先对令牌数组进行排序。然后使用两个指针left和right，分别指向数组的最小值和最大值，代表可以使用的令牌范围。在每一次循环中，首先判断是否有足够的能量使用left指向的令牌增加分数，如果可以，则使用该令牌并向右移动left指针。如果能量不足以使用left指向的令牌，但有足够的分数来兑换right指向的令牌获取能量，则使用right指向的令牌并向左移动right指针。循环直到没有足够的资源使用任何令牌。整个过程中跟踪并更新最大分数。

时间复杂度: O(n log n)

空间复杂度: O(1)

from typing import List

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        tokens.sort()  # 将令牌按能量值升序排序
        score = 0  # 初始化分数为0
        max_score = 0  # 记录最大分数
        left = 0  # 左指针，指向最小令牌
        right = len(tokens) - 1  # 右指针，指向最大令牌

        while left <= right:
            if power >= tokens[left]:  # 如果能量足够，使用左侧令牌，增加分数
                power -= tokens[left]
                score += 1
                left += 1
                max_score = max(max_score, score)  # 更新最大分数
            elif score > 0:  # 如果分数足够，使用右侧令牌，增加能量
                power += tokens[right]
                score -= 1
                right -= 1
            else:  # 否则，终止循环
                break

        return max_score

solution = Solution()

print(solution.bagOfTokensScore([100], 50))  # 输出: 0
print(solution.bagOfTokensScore([100, 200], 150))  # 输出: 1
print(solution.bagOfTokensScore([100, 200, 300, 400], 200))  # 输出: 2

Explore

问题的关键在于贪心策略的应用。通过将令牌按能量值升序排序，我们可以最大化使用令牌的可能性。使用'朝上'策略，即首先使用较小的令牌以增加分数，是为了尽可能地在能量允许的情况下增加分数。当能量不足以继续使用最小的令牌时，若还有分数可用，则考虑'朝下'策略，即使用最大的令牌以换取更多能量，从而可能继续使用中间的小令牌。这种策略是动态的，基于当前的能量和分数来决定下一步的最佳行动，因此通常能够保证达到最大分数。

当左右指针相遇时，说明只剩下一个令牌未被使用。在这种情况下，如果当前的能量足够使用这个令牌，则应该使用它以增加分数；如果能量不足，而且没有足够的分数来兑换这个令牌的能量，则不再可能使用任何令牌。因此，在指针相遇时，是否继续使用令牌完全取决于当前的能量和分数。

这种策略基于贪心算法的思想，尽量保持游戏的持续性和分数的最大化。在能量不足以使用左侧令牌（低成本令牌）时，使用右侧令牌（高成本令牌）来获取能量，是为了尽可能地维持或增加能够继续使用更多令牌的可能性。这种策略在大多数情况下是有效的，因为它延长了游戏的进行，并可能在后续步骤中使用更多的低成本令牌来增加分数。然而，这不一定总是最优策略，因为特定的令牌和能量组合可能存在特殊情况，使得这种策略不是最优解。但在没有额外信息的情况下，按照这种策略行动通常能达到较好的结果。