# 948. Bag of Tokens

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`

``````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;
}
};
``````

``````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;
}
};
``````

``````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://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation