Integer to Roman

Средняя№12сначала самое крупное

Запишите целое число от 1 до 3999 римскими цифрами. I, V, X, L, C, D и M — это 1, 5, 10, 50, 100, 500 и 1000, они пишутся от больших к меньшим и складываются. Один символ подряд — не больше трёх раз; для 4, 9, 40, 90, 400 и 900 меньший символ ставится перед большим и вычитается: IV, IX, XL, XC, CD, CM. Наш пример: 2894 — ответ «MMDCCCXCIV».

12 Integer to RomanРазбор · 1×

Пример: 2894. Сверху — таблица от большего к меньшему, пары с вычитанием стоят среди обычных символов; ниже — остаток num и уже записанные символы.

1000M900CM500D400CD100C90XC50L40XL10X9IX5V4IV1Inum2894out—
ещё не пробовалипробуем это значениеиспользованоне поместилось

Пока ничего не записано; num = 2894

01/52
сначала · назад · пуск · шаг
Скорость
1function intToRoman(num):
2 out = ""
3 for each (value, symbol) in table: // 1000 M, 900 CM, 500 D, 400 CD, …, 4 IV, 1 I
4 while num >= value:
5 out = out + symbol
6 num = num - value
7 return out
состояние
num
2894
out
""
value
–
symbol
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Одними символами меньше какого-то значения правильная запись до него не дотягивает: меньше CM = 900 самое большое — DCCCXCIX = 899. Поэтому если значение помещается, запись обязана взять его сейчас: меньшие его не наберут.
  2. Пары CM, CD, XC, XL, IX и IV стоят в таблице как отдельные значения. Благодаря им жадности не нужны четыре одинаковых символа: 94 — это XC + IV, а не LXXXX + IIII.
  3. num только уменьшается, а таблица проходится один раз сверху вниз, поэтому символы выходят от больших к меньшим, как и требует римская запись.

Сложность

Время O(1): в таблице 13 значений, и ни один символ не пишется больше трёх раз подряд, поэтому символов выходит не больше 15. Память O(1), не считая ответа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.