Leetcode задача #168. Excel Sheet column title.
Задача помечена как простая, тем не менее, не сразу понял как её решать.
Дано число, это номер столбца для Excel таблицы, требуется сгенерировать его буквенное имя. Иными словами сопоставить 1 -> A, … 26 -> Z, 27 -> AA …
Вроде бы тривиальная задача о переводе из одной позиционной системы счисления (СС) в другую. Мы хотим перевести из СС с основанием 10 (0…9) в СС с основанием 26 (A…Z).
Нюанс задачи заключается в том, что индексация столбцов в Excel виртуально отбрасывает нас во времена, когда в математике не изобрели числа 0, т.е. примерно на 1,5 тыс. лет назад.
«А» не является в данном случае подобием нуля, т.к. обозначает столбец под номером 1. Потому запись вроде «AA» — трактуется не как ноль-ноль, а как 1 — 1.
Если взять столбец 27, и поделить его на разрядность, то мы получим 1, и еще 1 в остатке, или коротко можно записать вот так:
|
1 |
27 / 26 = 1 R 1 |
Что легко читается как A — A. Но если мы берем столбец 26 и проделываем с ним тоже самое:
|
1 |
26 / 26 = 1 R 0 |
То здесь вы уже не сможете сопоставить что либо внятное, т.к. нуля у вас нет в данной системе счисления. А должен получится результат «Z».
Что же делать?
Можно попробовать сместить нумерацию на единицу влево. И сказать, что А — это не единица, а ноль, B — это 1, и так далее Z — 25.
|
1 |
(26 - 1) / 26 = 0 R 25 |
Вроде бы выправили ситуацию для этого случая, получилось «Z», который при смещении стал равен 25. Но вернемся снова к столбцу № 27:
|
1 |
(27 - 1) / 26 = 1 R 0 |
Учитывая смещение, это нам даст «BA», вместо «AA». Опять не хорошо.
Этот пример лишь показывает, что «0» это не самая простая концепция в математике. Но подход со смещением, в принципе, верный, только требуется смещать каждый разряд, а не всё число. Произведя смещение однократно, мы делаем правильный шаг только для младшего из разрядов.
Давайте посмотрим на код (TS):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
function convertToTitle(columnNumber: number): string { let res = ''; while (columnNumber > 0) { // смещение для текущего разряда... // всего лишь одна операция в коде, // но огромный прыжок вперед в истории всей математики :) columnNumber --; // остаток от деления на основание СС const extra = columnNumber % 26; // здесь мы получаем ASCII код символа и добавляем его к результату res = String.fromCharCode(65 + extra) + res; // переходим к следующему разряду columnNumber = (columnNumber - extra) / 26; } return res; }; |