Welcome to Subscribe On Youtube
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;
}
};
-
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; } } ############ class Solution { public int bagOfTokensScore(int[] tokens, int power) { Arrays.sort(tokens); int i = 0, j = tokens.length - 1; int ans = 0, t = 0; while (i <= j) { if (power >= tokens[i]) { power -= tokens[i++]; ++t; ans = Math.max(ans, t); } else if (t > 0) { power += tokens[j--]; --t; } else { break; } } return ans; } }
-
class Solution: def bagOfTokensScore(self, tokens: List[int], power: int) -> int: tokens.sort() i, j = 0, len(tokens) - 1 ans = t = 0 while i <= j: if power >= tokens[i]: power -= tokens[i] i, t = i + 1, t + 1 ans = max(ans, t) elif t: power += tokens[j] j, t = j - 1, t - 1 else: break return ans ############ class Solution(object): def bagOfTokensScore(self, tokens, P): """ :type tokens: List[int] :type P: int :rtype: int """ print(tokens) tokens.sort() N = len(tokens) left, right = 0, N - 1 points = 0 remain = N while left < N and P >= tokens[left]: P -= tokens[left] points += 1 left += 1 remain -= 1 if left == 0 or left == N: return points while points > 0 and remain > 1: P += tokens[right] right -= 1 points -= 1 remain -= 1 while left <= right and P >= tokens[left]: P -= tokens[left] points += 1 left += 1 remain -= 1 return points
-
func bagOfTokensScore(tokens []int, power int) int { sort.Ints(tokens) i, j := 0, len(tokens)-1 ans, t := 0, 0 for i <= j { if power >= tokens[i] { power -= tokens[i] i, t = i+1, t+1 ans = max(ans, t) } else if t > 0 { power += tokens[j] j, t = j-1, t-1 } else { break } } return ans } func max(a, b int) int { if a > b { return a } return b }