Formatted question description: https://leetcode.ca/all/948.html
948. Bag of Tokens (Medium)
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 gaining1
point. - If we have at least
1
point, we may play the token face down, gainingtoken[i]
power, and losing1
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:
tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000
Related Topics:
Greedy
Solution 1. Greedy + Two Pointers
Intuition: We would want to buy high value tokens using score and sell low value tokens to get scores.
So we should:
- sort the tokens in asending order.
- Try to use
P
to cover as much low value tokens as possible to get scores. - We buy the highest value token using one score, and add the value to
P
. If we can’t buy any token, break. - Repeat step 2 and 3 until we’ve visited all tokens.
- The final score we get is the answer.
// OJ: https://leetcode.com/problems/bag-of-tokens/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int bagOfTokensScore(vector<int>& tokens, int P) {
sort(tokens.begin(), tokens.end());
int i = 0, j = tokens.size() - 1, S = 0; // i points to the next low value token we can sell, j points to the next high value token we can buy, S is the score.
while (i <= j) {
while (i <= j && tokens[i] <= P) { // tokens[i] can be covered by `P`, sell it for score.
P -= tokens[i++];
S++;
}
if (i < j && S) { // if i == j, we can't sell any token after buying this token. So we only buy this tokens[j] if i < j and we have some score left.
S--;
P += tokens[j--];
} else break;
}
return S;
}
};
Java
class Solution {
public int bagOfTokensScore(int[] tokens, int P) {
Arrays.sort(tokens);
int low = 0, high = tokens.length - 1;
int points = 0, power = P;
int maxPoints = 0;
while (low <= high) {
if (tokens[low] > power && points == 0)
break;
if (tokens[low] <= power) {
power -= tokens[low];
low++;
points++;
} else {
power += tokens[high];
high--;
points--;
}
maxPoints = Math.max(maxPoints, points);
}
return maxPoints;
}
}