Leetcode 948 Bag of Tokens

发表于 |

你具有初始能量P，分数0，和一系列的tokens
每个token只能使用一次，并且token具有一个值token[i]
对于每个token，你有以下两种方式去使用：

  1. 如果此时的能量P>token[i]，我们可以消耗token[i]的能量来获得1分
  2. 如果此时你至少有1分，你可以失去1分并获得token[i]的能量

返回能得到的最大分数。

Example 1:
Input: tokens = [100], P = 50
Output: 0

Example 2:
Input: tokens = [100,200], P = 150
Output: 1

Example 3:
Input: tokens = [100,200,300,400], P = 200
Output: 2

Note:

  1. tokens.length <= 1000
  2. 0 <= tokens[i] < 10000
  3. 0 <= P < 10000

思路分析：
这道题使用贪心策略，即以下两条：

  1. 始终只从最小的token[i]获得分数
  2. 始终只从最大的token[i]获得能量

那什么时候终止呢，当我们目前无法获得更多分数时，也就是P < mim(tokens)
我们需要决策是否消耗1分去换取max(tokens)的能量

决策条件就是我们换取之后至少能多获得两分（这样最后总分才可能更大），我们才继续游戏
否则，直接放弃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def bagOfTokensScore(self, tokens, P):
        if not tokens: return 0
        if P < min(tokens): return 0
        tokens.sort()
        
        def solve(tokens, P, points):
            if not tokens: return points
            if len(tokens) == 1: return points+int(tokens[0] <= P)
            # tokens[-1]+P表示换能量之后具有的总能量
            # 判断其是否还能购买两个
            if len(tokens) >= 3 and tokens[-1]+P < tokens[0]+tokens[1]:
                return points
            i = 0
            while i < len(tokens) and tokens[i] <= P:
                P -= tokens[i]
                points += 1
                i += 1
            return max(points, solve(tokens[i:-1], P+tokens[-1], points-1))
        
        return solve(tokens[1:], P-tokens[0], 1)