время выполнения — функция оптимизации времени C ++ для определения количества возможностей декодирования
Это Практика собеседования от CodeFights. У меня есть решение, которое работает, за исключением того факта, что для очень больших входов требуется слишком много времени.
Совершенно секретно message содержащие заглавные буквы из 'A' в 'Z' был закодирован как числа с использованием следующего сопоставления:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Вы агент ФБР, и вам нужно определить общее количество способов, которыми сообщение может быть декодировано.
Поскольку ответ может быть очень большим, возьмите его по модулю 10 ^ 9 + 7.
пример
За message = "123"выход должен быть
mapDecoding(message) = 3,
"123" может быть расшифрован как "ABC" (1 2 3), "LC" (12 3) или же "AW" (1 23)Таким образом, общее количество способов 3,
Ввод, вывод
[ограничение по времени] 500 мс (cpp)
[вход] строковое сообщение
Строка, содержащая только цифры.
Гарантированные ограничения:
0 ≤ message.length ≤ 105,
[вывод] целое число
Общее количество способов декодирования данного сообщения.
Мы должны реализовать решение в функции int mapDecoding(std::string message)Итак, все мое решение заключается в следующем:
/*0*/ void countValidPaths(int stIx, int endIx, std::string message, long *numPaths)
/*1*/ {
/*2*/ //check out-of-bounds error
/*3*/ if (endIx >= message.length())
/*4*/ return;
/*5*/
/*6*/ int subNum = 0, curCharNum;
/*7*/ //convert substr to int
/*8*/ for (int i = stIx; i <= endIx; ++i)
/*9*/ {
/*10*/ curCharNum = message[i] - '0';
/*11*/ subNum = subNum * 10 + curCharNum;
/*12*/ }
/*13*/
/*14*/ //check for leading 0 in two-digit number, which would not be valid
/*15*/ if (endIx > stIx && subNum < 10)
/*16*/ return;
/*17*/
/*18*/ //if number is valid
/*19*/ if (subNum <= 26 && subNum >= 1)
/*20*/ {
/*21*/ //we've reached the end of the string with success, therefore return a 1
/*22*/ if (endIx == (message.length() - 1) )
/*23*/ ++(*numPaths);
/*24*/ //branch out into the next 1- and 2-digit combos
/*25*/ else if (endIx == stIx)
/*26*/ {
/*27*/ countValidPaths(stIx, endIx + 1, message, numPaths);
/*28*/ countValidPaths(stIx + 1, endIx + 1, message, numPaths);
/*29*/ }
/*30*/ //proceed to the next digit
/*31*/ else
/*32*/ countValidPaths(endIx + 1, endIx + 1, message, numPaths);
/*33*/ }
/*34*/ }
/*35*/
/*36*/ int mapDecoding(std::string message)
/*37*/ {
/*38*/ if (message == "")
/*39*/ return 1;
/*40*/ long numPaths = 0;
/*41*/ int modByThis = static_cast<int>(std::pow(10.0, 9.0) + 7);
/*42*/ countValidPaths(0, 0, message, &numPaths);
/*43*/ return static_cast<int> (numPaths % modByThis);
/*44*/ }
Я прошел 11/12 первоначальных тестовых случаев CodeFight, например, mapDecoding("123") = 3 а также mapDecoding("11115112112") = 104, Тем не менее, последний контрольный пример имеет message = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211"и моя программа выполняется слишком долго:
Expected_output: 782204094
My_program_output: <empty due to timeout>
я написал countValidPaths() как рекурсивная функция, и ее рекурсивные вызовы находятся в строках 27, 28 и 32. Я могу видеть, как такой большой ввод приведет к тому, что код займет так много времени, но я ломаю голову, пытаясь выяснить, какие более эффективные решения будет охватывать все возможные комбинации.
Таким образом, вопрос на миллион долларов: какие предложения вы хотите оптимизировать мою текущую программу, чтобы она работала гораздо быстрее?
Решение
Пара предложений.
Во-первых, эта проблема, вероятно, может быть сформулирована как проблема динамического программирования. У меня такой запах. Вы вычисляете одно и то же снова и снова.
Второе — понимание того, что длинные смежные последовательности «1» и «2» представляют собой последовательность Фибоначчи с точки зрения количества возможностей. Любое другое значение завершает последовательность. Таким образом, вы можете разбить строки на ряды единиц и двойки, оканчивающиеся любым другим числом. Вам понадобится специальная логика для завершения нуля, поскольку она также не соответствует символу. Поэтому разделите число строк, длину каждого сегмента, найдите число Фибоначчи (которое можно предварительно вычислить) и умножьте значения. Итак, ваш пример «11115112112» дает «11115» и «112112», а f (5) = 8 и f (6) = 13, 8 * 13 = 104.
Ваша длинная строка представляет собой последовательность из 1 и 2 длиной 100 цифр. Следующая Java-программа (извините, мой C ++ ржавый) правильно вычисляет значение этого метода
public class FibPaths {
private static final int MAX_LEN = 105;
private static final BigInteger MOD_CONST = new BigInteger("1000000007");
private static BigInteger[] fibNum = new BigInteger[MAX_LEN];
private static void computeFibNums() {
fibNum[0] = new BigInteger("1");
fibNum[1] = new BigInteger("1");
for (int i = 2; i < MAX_LEN; i++) {
fibNum[i] = fibNum[i-2].add(fibNum[i-1]);
}
}
public static void main(String[] argv) {
String x = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211";
computeFibNums();
BigInteger val = fibNum[x.length()].mod(MOD_CONST);
System.out.println("N=" + x.length() + " , val = " + val);
}
}
Другие решения
Других решений пока нет …