Проблема
Задача была проста. Дана строка, представляющая римскую цифру, преобразовать ее в целое число.
У меня было предварительное представление о римских цифрах и их форматировании, поэтому я был готов сразу приступить к этому, но, как я вскоре узнал, даже такие упрощенные задачи, как эта, нельзя недооценивать.
Ограничения
Первоначально я игнорировал ограничения проблемы и пытался подойти к ней как можно шире. Этот инстинкт возник из моего опыта создания игр на Unity и C#, где нулевые ссылки и исключения за пределами границ могут привести к тому, что важный игровой объект перестанет работать. Однако позже эти ограничения окажутся неотъемлемой частью решения проблемы чистым и оптимизированным способом.
Попытка №1 — Неуклюжее начало
class Solution {
public int romanToInt(String s) {
int result = 0;
// ???
return result;
}
}
Мне нужно было бы вытащить каждую букву строки и найти соответствующее целочисленное значение. Очевидным первым шагом было создание цикла for, но при размышлении о том, что именно нужно делать в этом цикле, вдруг оказалось, что лучшее решение найти не так просто.
for(int i = 0; i < s.length(); i++)
{
switch(s.charAt(i))
{
case 'I':
result += 1;
break;
case 'V':
result += 5;
break;
case 'X':
result += 10;
break;
case 'L':
result += 50;
break;
case 'C':
result += 100;
break;
case 'D':
result += 500;
break;
case 'M':
result += 1000;
break;
}
}
Такой оператор switch потенциально мог бы работать, но сам по себе этот блок уже больше головной боли, чем пользы, а чтение каждой возможной буквы на каждом этапе цикла for — не самый оптимизированный план.
Я знал, что есть лучший способ приблизиться к этому. Мне нужна была структура данных, в которой я мог бы хранить символы в паре с соответствующими целыми числами. Массивы, списки и другие одномерные структуры не подойдут. Даже если бы я использовал их для разработки решения, оптимизация программы сильно пострадала бы.
Попытка № 2 — введите HashMap
С помощью HashMap я мог хранить эти пары букв и цифр и извлекать их во время центрального цикла for. Поскольку сделать это было так же просто, как вызвать метод get(), я мог сделать это без существенного увеличения сложности всей программы. Во-первых, мне нужно объявить карту и заполнить ее соответствующими парами.
class Solution {
static Map<Character, Integer> RomanNumerals = new HashMap<Character, Integer>();
public int romanToInt(String s) {
// BUILD ROMAN NUMERAL HASHMAP
RomanNumerals.put('I', 1);
RomanNumerals.put('V', 5);
RomanNumerals.put('X', 10);
RomanNumerals.put('L', 50);
RomanNumerals.put('C', 100);
RomanNumerals.put('D', 500);
RomanNumerals.put('M', 1000);
// INITIALIZE RESULT TO ZERO
int result = 0;
// LOOP THROUGH THE STRING
for(int i = 0; i < s.length(); i++)
{
// ADD INT EQUIVALENT TO CHARACTER FROM HASHMAP
// ONLY IF CHARACTER IS PRESENT IN MAP
if(RomanNumerals.containsKey(s.charAt(i)))
result += RomanNumerals.get(s.charAt(i));
}
return result;
}
}
Тело цикла for пришло после этого легко.
Легко-легко, верно? Код чистый, читаемый и безошибочный. Однако после запуска тестовых случаев я понял, что еще не закончил.
Мой код не прошел третий тест. Сначала это меня удивило. Я поинтересовался; если функция работала правильно для первых двух тестовых случаев, в чем проблема с третьим? Затем я внимательно посмотрел на входную строку: "MCMXCIV".
В первых двух тестовых строках, «III» и «LVIII», символы были организованы таким образом, что каждый из них соответствовал большему целому числу, чем следующий. Таким образом, каждое целое число может быть добавлено к результату без головной боли. Однако эта третья струна была другой.
Если римская цифра стоит перед другой, имеющей большее значение, она вычитает из следующего значения. С нашим текущим методом последовательность вроде «CM», которая должна соответствовать 900, становится 1100, что отбрасывает наш результат. То же самое верно и для «XC» позже в строке, которая была преобразована в 110 как часть этого решения, когда она должна была быть преобразована в 90.
Мне пришлось учесть это в моем следующем решении, чтобы пройти третий тест, но как мне это сделать? На первый взгляд изменения, которые необходимо было внести, были очевидны. При прохождении цикла, если следующая буква строки, следующая за текущей, соответствует большему целому числу из HashMap, число, соответствующее текущей букве, будет вычитаться из общего числа, а не добавляться.
Я подумал о беспорядке, который возник бы, если бы я взял несколько строк, чтобы проверить, является ли текущий символ последним в строке, проверить, существует ли следующий в HashMap, и проверить, было ли соответствующее целое число больше, чем текущее в строке. цикл, все для обслуживания того, что должно быть относительно простым оператором if-else.
for(int i = 0; i < s.length(); i++)
{
if(i < s.length() - 1
&& RomanNumerals.containsKey(s.charAt(i))
&& RomanNumerals.get(s.charAt(i + 1)) > RomanNumerals.get(s.charAt(i)))
result -= RomanNumerals.get(s.charAt(i));
else result += RomanNumerals.get(s.charAt(i));
}
Излишне говорить, что мне не понравилось, как это выглядело. Я хотел решение, которое было бы чище и лаконичнее, хотя и ненамного.
Это был момент, когда я вспомнил об ограничениях проблемы. В соответствии с этими ограничениями входная строка гарантировалась как допустимая римская цифра и содержала только буквы алфавита. Мне не нужно было проверять, существует ли символ или присутствует ли он в HashMap; по границам задачи они бы там были, лишь бы сама карта была объявлена корректно.
Попытка № 3 — Чистое вычитание
class Solution {
static Map<Character, Integer> RomanNumerals = new HashMap<Character, Integer>();
public int romanToInt(String s) {
// BUILD ROMAN NUMERAL HASHMAP
RomanNumerals.put('I', 1);
RomanNumerals.put('V', 5);
RomanNumerals.put('X', 10);
RomanNumerals.put('L', 50);
RomanNumerals.put('C', 100);
RomanNumerals.put('D', 500);
RomanNumerals.put('M', 1000);
// INITIALIZE RESULT TO ZERO
int result = 0;
for(int i = 0; i < s.length(); i++)
{
// SUBTRACT INT EQUIVALENT TO CHARACTER FROM HASHMAP IF THE NEXT
// CHARACTER HAS A HIGHER VALUE
if(i < s.length() - 1 &&
RomanNumerals.get(s.charAt(i + 1)) > RomanNumerals.get(s.charAt(i)))
result -= RomanNumerals.get(s.charAt(i));
else result += RomanNumerals.get(s.charAt(i));
// OTHERWISE ADD INT EQUIVALENT TO CHARACTER FROM HASHMAP
}
return result;
}
}
После удаления оператора containsKey() остались только основные инструкции. Целочисленное значение будет добавлено к результирующей переменной если только это целое число не будет меньше следующего, и поскольку эта проверка не может быть выполнена для последнего символа строки, мы все равно должны убедиться, что проверяемый символ не последний.
С последним пройденным тестом задача завершена!
