Сложность: 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⃣Вернуть максимальный счет.
😎 Решение:
function bagOfTokensScore($tokens, $power) {
sort($tokens);
$left = 0;
$right = count($tokens) - 1;
$score = 0;
$maxScore = 0;
while ($left <= $right) {
if ($power >= $tokens[$left]) {
$power -= $tokens[$left];
$score++;
$left++;
$maxScore = max($maxScore, $score);
} elseif ($score > 0) {
$power += $tokens[$right];
$score--;
$right--;
} else {
break;
}
}
return $maxScore;
}Ставь 👍 и забирай 📚 Базу знаний