948. Bag of Tokens

leetcode medium

#array#csharp#leetcode#math#medium#sort#two-pointers

Task

Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.

Пример:

Input: tokens = [100], power = 50

Output: 0

C# solution

matched/original

public class Solution {
    public int BagOfTokensScore(int[] tokens, int power) {
        Array.Sort(tokens);
        int left = 0, right = tokens.Length - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.Max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int BagOfTokensScore(vector<int>& tokens, int power) {
        sort(tokens.begin(), tokens.end());
        int left = 0, right = tokens.size() - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

Java solution

matched/original

import java.util.Arrays;

class Solution {
    public int bagOfTokensScore(int[] tokens, int power) {
        Arrays.sort(tokens);
        int left = 0, right = tokens.length - 1;
        int score = 0, maxScore = 0;
        
        while (left <= right) {
            if (power >= tokens[left]) {
                power -= tokens[left];
                score++;
                left++;
                maxScore = Math.max(maxScore, score);
            } else if (score > 0) {
                power += tokens[right];
                score--;
                right--;
            } else {
                break;
            }
        }
        
        return maxScore;
    }
}

JavaScript solution

matched/original

var bagOfTokensScore = function(tokens, power) {
    tokens.sort((a, b) => a - b);
    let left = 0, right = tokens.length - 1;
    let score = 0, maxScore = 0;
    
    while (left <= right) {
        if (power >= tokens[left]) {
            power -= tokens[left];
            score++;
            left++;
            maxScore = Math.max(maxScore, score);
        } else if (score > 0) {
            power += tokens[right];
            score--;
            right--;
        } else {
            break;
        }
    }
    
    return maxScore;
};

Python solution

matched/original

def bagOfTokensScore(tokens, power):
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score, maxScore = 0, 0
    
    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            left += 1
            maxScore = max(maxScore, score)
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break
    
    return maxScore

Go solution

matched/original

package main

import "sort"

func bagOfTokensScore(tokens []int, power int) int {
    sort.Ints(tokens)
    left, right := 0, len(tokens) - 1
    score, maxScore := 0, 0
    
    for left <= right {
        if power >= tokens[left] {
            power -= tokens[left]
            score++
            left++
            if score > maxScore {
                maxScore = score
            }
        } else if score > 0 {
            power += tokens[right]
            score--
            right--
        } else {
            break
        }
    }
    
    return maxScore
}

Explanation

Algorithm

Отсортировать массив tokens.

Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.

Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore

Повторять следующие шаги, пока left не превысит right:

Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.

Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.

Обновить максимальный счет, если текущий счет больше максимального.

Вернуть максимальный счет.

😎