Repository navigation
[LeetCode] 948. Bag of Tokens #948
Description
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, losingtoken[i]power, and gaining1point. - If we have at least
1point, we may play the token face down, gainingtoken[i]power, and losing1point.
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:
tokens.length <= 10000 <= tokens[i] < 100000 <= 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 同步地址:
参考资料：
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
Activity