Сложность: medium
Вы начинаете с начальной силой, равной power, начальным счетом 0 и мешком жетонов, представленным в виде целочисленного массива tokens, где каждый tokens[i] обозначает значение tokeni. Ваша цель - максимизировать общее количество очков, стратегически разыгрывая эти жетоны. За один ход вы можете разыграть неразыгранный жетон одним из двух способов (но не обоими для одного и того же жетона): лицом вверх: Если ваша текущая сила не меньше жетонов[i], вы можете сыграть токени, потеряв силу жетонов[i] и получив 1 очко. Лицом вниз: Если ваш текущий счет не меньше 1, вы можете сыграть токени, получив силу токенов[i] и потеряв 1 счет. Верните максимально возможный счет, который вы можете получить, сыграв любое количество токенов.
Пример:
Input: tokens = [100], power = 50
Output: 0
👨💻 Алгоритм:
1⃣Отсортировать массив tokens.
Использовать два указателя: left и right, чтобы отслеживать начало и конец массива токенов.
Инициализировать переменные для текущей силы power, текущего счета score и максимального счета maxScore
2⃣Повторять следующие шаги, пока left не превысит right:
Если текущая сила power достаточна для разыгрывания токена tokens[left] лицом вверх, разыграть его и увеличить счет.
Если текущая сила недостаточна, но счет больше 0, разыграть токен tokens[right] лицом вниз и уменьшить счет.
Обновить максимальный счет, если текущий счет больше максимального.
3⃣Вернуть максимальный счет.
😎 Решение:
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;
}
}
Ставь 👍 и забирай 📚 Базу знаний