Сложность: medium
Числовое значение строчной буквы определяется ее позицией (начиная с 1) в алфавите, поэтому числовое значение a равно 1, числовое значение b равно 2, числовое значение c равно 3 и так далее.
Числовое значение строки, состоящей из строчных букв, определяется как сумма числовых значений ее символов. Например, числовое значение строки "abe" равно 1 + 2 + 5 = 8.
Вам даны два целых числа n и k. Верните лексикографически наименьшую строку длиной n с числовым значением, равным k.
Обратите внимание, что строка x лексикографически меньше строки y, если x идет перед y в словарном порядке, то есть либо x является префиксом y, либо, если i - первая позиция, где x[i] != y[i], то x[i] идет перед y[i] в алфавитном порядке.
Пример:
Input: n = 3, k = 27
Output: "aay"
Explanation: The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.
👨💻 Алгоритм:
1⃣Построить строку или массив символов result для хранения выбранных символов для каждой позиции.
2⃣Итерация от позиции 1 до n и заполнение символом каждой позиции:
Найти позиции, которые нужно заполнить, исключая текущую позицию, задаваемую переменной positionsLeft как n - position - 1.
Если значение k больше, чем positionsLeft * 26, зарезервировать числовое значение 26 (символ z) для всех оставшихся позиций positionsLeft. Вычислить значение текущей позиции, заданное переменной add, как k - (positionsLeft * 26). Вычесть рассчитанное значение add из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
Иначе, заполнить текущую позицию символом a, имеющим числовое значение 1. Вычесть 1 из k, чтобы найти оставшееся значение k после заполнения текущей позиции.
3⃣Повторять процесс, пока все позиции не будут заполнены.
😎 Решение:
class Solution {
function getSmallestString($n, $k) {
$result = array_fill(0, $n, 'a');
for ($position = 0; $position < $n; $position++) {
$positionsLeft = ($n - $position - 1);
if ($k > $positionsLeft * 26) {
$add = $k - ($positionsLeft * 26);
$result[$position] = chr(97 + $add - 1);
$k -= $add;
} else {
$k -= 1;
}
}
return implode('', $result);
}
}Ставь 👍 и забирай 📚 Базу знаний