[LeetCode] 948. Bag of Tokens

[grandyang]

You have an initial power P, an initial score of 0 points, and a bag of tokens.

Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

• If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
• If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.

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

这道题说是给了一个初始力量值P，然后有一个 tokens 数组，有两种操作可以选择，一种是减去 tokens[i] 的力量，得到一分，但是前提是减去后剩余的力量不能为负。另一种是减去一分，得到 tokens[i] 的力量，前提是减去后的分数不能为负，问一顿操作猛如虎后可以得到的最高分数是多少。这道题其实题意不是太容易理解，而且例子也没给解释，博主也是读了好几遍题目才明白的。比如例子3，开始有 200 的力量，可以先花 100，得到1个积分，此时还剩 100 的力量，但由于剩下的 token 值都太大，没法换积分了，只能用积分来换力量，既然都是花一个1个积分，肯定是要换最多的力量，于是换来 400 力量，此时总共有 500 的力量，积分还是0，但是一顿操作后，白嫖了 400 的力量，岂不美哉？！这 500 的力量刚好可以换两个积分，所以最后返回的就是2。通过上述分析，基本上可以知道策略了，从最小的 token 开始，用力量换积分，当力量不够时，就用基本换最大的力量，如果没有积分可以换力量，就结束，或者所有的 token 都使用过了，也结束，这就是典型的贪婪算法 Greedy Algorithm，也算对得起其 Medium 的身价。这里先给 tokens 数组排个序，然后使用双指针i和j，分别指向开头和末尾，当 i<=j 进行循环，从小的 token 开始查找，只要力量够，就换成积分，不能换的时候，假如 i>j 或者此时积分为0，则退出；否则用一个积分换最大的力量，参见代码如下：

解法一：

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        int res = 0, cur = 0, n = tokens.size(), i = 0, j = n - 1;
        sort(tokens.begin(), tokens.end());
        while (i <= j) {
            while (i <= j && tokens[i] <= P) {
                P -= tokens[i++];
                res = max(res, ++cur);
            }
            if (i > j || cur == 0) break;
            --cur;
            P += tokens[j--];
        }
        return res;
    }
};

我们也可以换一种写法，不用 while 套 while，而是换成赏心悦目的 if ... else 语句，其实也没差啦，参见代码如下：

解法二：

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        int res = 0, cur = 0, n = tokens.size(), i = 0, j = n - 1;
        sort(tokens.begin(), tokens.end());
        while (i <= j) {
            if (P >= tokens[i]) {
                P -= tokens[i++];
                res = max(res, ++cur);
            } else if (cur > 0) {
                --cur;
                P += tokens[j--];
            } else {
                break;
            }
        }
        return res;
    }
};

我们也可以使用递归来做，使用一个子函数 helper，将i和j当作参数输入，其实原理跟上的方法一摸一样，不难理解，参见代码如下：

解法三：

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int P) {
        sort(tokens.begin(), tokens.end());
        return helper(tokens, P, 0, (int)tokens.size() - 1, 0);
    }
    int helper(vector<int>& tokens, int P, int i, int j, int cur) {
        if (i > j) return cur;
        int res = cur;
        if (tokens[i] <= P) {
            res = max(res, helper(tokens, P - tokens[i], i + 1, j, cur + 1));
        } else if (cur > 0) {
            res = max(res, helper(tokens, P + tokens[j], i, j - 1, cur - 1));
        }
        return res;
    }
};

Github 同步地址:

#948

参考资料：

https://leetcode.com/problems/bag-of-tokens/

https://leetcode.com/problems/bag-of-tokens/discuss/383249/Java-Solution-With-Explanation

https://leetcode.com/problems/bag-of-tokens/discuss/197696/C%2B%2BJavaPython-Greedy-%2B-Two-Pointers

LeetCode All in One 题目讲解汇总(持续更新中...)