LeetCode: 948-Bag of Tokens 解題紀錄

Last Updated on 2022-09-12 by Clay

題目

You have an initial power of power, an initial score of 0, and a bag of tokens where tokens[i] is the value of the ith token (0-indexed).

Your goal is to maximize your total score by potentially playing each token in one of two ways:

• If your current power is at least tokens[i], you may play the ith token face up, losing tokens[i] power and gaining 1 score.
• If your current score is at least 1, you may play the ith token face down, gaining tokens[i] power and losing 1 score.

Each token may be played at most once and in any order. You do not have to play all the tokens.

Return the largest possible score you can achieve after playing any number of tokens.

Example 1:

Input: tokens = [100], power = 50
Output: 0
Explanation: Playing the only token in the bag is impossible because you either have too little power or too little score.

Example 2:

Input: tokens = [100,200], power = 150
Output: 1
Explanation: Play the 0th token (100) face up, your power becomes 50 and score becomes 1.
There is no need to play the 1st token since you cannot play it face up to add to your score.

Example 3:

Input: tokens = [100,200,300,400], power = 200
Output: 2
Explanation: Play the tokens in this order to get a score of 2:
1. Play the 0th token (100) face up, your power becomes 100 and score becomes 1.
2. Play the 3rd token (400) face down, your power becomes 500 and score becomes 0.
3. Play the 1st token (200) face up, your power becomes 300 and score becomes 1.
4. Play the 2nd token (300) face up, your power becomes 0 and score becomes 2.

Constraints:

• 0 <= tokens.length <= 1000
• 0 <= tokens[i], power < 104

這個題目我愣是反覆看了好幾次，這才終於明白題目的意思：我們的初始分數 score 是 0，然後有一個初始的 power 值以及一系列的 tokens（卡牌？令牌？）。

• 打出 token 時會按照 token 的數值消耗 power 值，但是會得一分
• 如果 power 值不足以打出 token，則可以減一分（如果你的 score 不為 0）並把一張 token 的數值轉換成 power

最後我們則要計算，最高到底可以得到幾分呢？有一個提示是，你不需要用光手上所有的 tokens。

---

解題思路

這個題目的解法我並不清楚該說是 two pointer 還是 greedy，但大致上就是將所有的 tokens 按照由小到大的順序排序，接著從最小的 token 開始消耗 power 賺取分數就是了；如果手上的 power 值不夠，則拿當前 tokens 中最大的 token 來充當 power，按照這個思路就可以得到最高分了。

C++ 範例程式碼

class Solution {
public:
    int bagOfTokensScore(vector<int>& tokens, int power) {
        // Sort
        sort(tokens.begin(), tokens.end());
        
        // Init
        int left = 0;
        int right = tokens.size() - 1;
        int score = 0;
        int max_score = 0;
        
        // Count
        while (left <= right) {
            if (tokens[left] <= power) {
                power -= tokens[left];
                ++score;
                ++left;
                
                max_score = (max_score, score);
            }
            else if (score >= 1) {
                power += tokens[right];
                --score;
                --right;
            }
            else {
                break;
            }
        }
        
        return max_score;
    }
};

Python 範例程式碼

class Solution:
    def bagOfTokensScore(self, tokens: List[int], power: int) -> int:
        # Sort
        tokens.sort()
        
        # Init
        left = 0
        right = len(tokens) - 1
        score = 0
        max_score = 0
        
        # Count
        while left <= right:
            if tokens[left] <= power:
                power -= tokens[left]
                score += 1
                left += 1
                max_score = max(max_score, score)
            elif score >= 1:
                power += tokens[right]
                score -= 1
                right -= 1
            else:
                break
        
        return max_score

---

References

• LeetCode 948. Bag of Tokens

---

Read More

• LeetCode 解題目錄