LeetCode Ts-948. Bag of Tokens

    AllenLi
    CodingLeetCode Js-Two Pointers

    You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.
    Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):
    Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score.
    Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.
    Return the maximum possible score you can achieve after playing any number of tokens.

    你一開始擁有初始能量 power, 初始的分數 0, 和一袋代幣 tokens(整數陣列)，
其中 tokens[i] 表示第 i 個代幣的價值。
你的目標是透過策略地使用代幣來使總分數最大化。
在每一個回合中，你可對尚未使用的代幣採用以下其中一種操作方式(同一個代幣不能同時執行兩種)：
Face-up:
如果你目前的能量大於或等於 tokens[i]，
你可以使用該代幣，消耗 tokens[i] 能量並獲得 1 分。
Face-down:
如果你目前的分數至少爲 1 分，
你可以使用該代幣，獲得 tokens[i] 能量，並失去 1 分。
請回傳在使用任務數量的代幣後，你能達到的最大分數。

    Example 1:

    Input: tokens = [100], power = 50

Output: 0

Explanation: Since your score is 0 initially, you cannot play the token face-down. You also cannot play it face-up since your power (50) is less than tokens[0] (100).

    Example 2:

    Input: tokens = [200,100], power = 150

Output: 1

Explanation: Play token1 (100) face-up, reducing your power to 50 and increasing your score to 1.

There is no need to play token0, since you cannot play it face-up to add to your score. The maximum score achievable is 1.

    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:

Play token0 (100) face-up, reducing power to 100 and increasing score to 1.
Play token3 (400) face-down, increasing power to 500 and reducing score to 0.
Play token1 (200) face-up, reducing power to 300 and increasing score to 1.
Play token2 (300) face-up, reducing power to 0 and increasing score to 2.
The maximum score achievable is 2.

    Solution:
    我們可以對 tokens 做由小到大的排序，這樣可以方便我們做出適合的判斷。
    接著我們用雙指針的方式，透過 left, right 來操作，
    left 指向最便宜的代幣，right 指向最貴的代幣，
    如果能量能夠買最小代幣，則我們花能量並加分(left++)，
    否則如果還有分數，就用 1 分數將最大代幣反面使用換取能量(right–)，
    如兩者皆不能操作，則停止並跳出回圈，
    每次操作後都更新 maxScore，
    最後回傳 maxScore。

    Code 1: BigO(n log n)

    function bagOfTokensScore(tokens: number[], power: number): number {
    tokens.sort((a, b) => a - b);
    let left: number = 0;
    let right: number = tokens.length - 1;
    let score: number = 0;
    let maxScore: number = 0;

    while (left <= right) {
        if (power >= tokens[left]) {
            power -= tokens[left];
            score++;
            left++;
        } else if (score > 0) {
            power += tokens[right];
            score--;
            right--;
        } else {
            break;
        }
        maxScore = Math.max(maxScore, score);
    }
    return maxScore;
};

    FlowChart:
    Example 1

    Input: tokens = [100], power = 50

Break: left=0, right=0, power=50, score=0

    Example 2

    Input: tokens = [200,100], power = 150

Used token up: left=0, power=50, score=1
MaxScore updated: 1
Used token down: right=1, power=250, score=0
MaxScore updated: 1

    Example 3

    Input: tokens = [100,200,300,400], power = 200

Used token up: left=0, power=100, score=1
MaxScore updated: 1
Used token down: right=3, power=500, score=0
MaxScore updated: 1
Used token up: left=1, power=300, score=1
MaxScore updated: 1
Used token up: left=2, power=0, score=2
MaxScore updated: 2

    Related Posts