0

这是来自 CodeFights 的面试练习题。我有一个有效的解决方案，除了运行非常大的输入需要很长时间。

问题描述（来自上面的链接）

包含从tomessage的大写字母的最高机密已使用以下映射编码为数字：'A''Z'

'A' -> 1
'B' -> 2
...
'Z' -> 26

您是 FBI 特工，您需要确定可以解码消息的方式总数。

由于答案可能非常大，因此取模 10^9 + 7。

例子

对于message = "123"，输出应该是

mapDecoding(message) = 3.

"123"可以解码为"ABC" (1 2 3),"LC" (12 3)或"AW" (1 23), 所以总路数为3.

输入输出

[时间限制] 500ms (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*/ }

问题

我已经通过了 CodeFight 的 11/12 的初始测试用例，例如mapDecoding("123") = 3和mapDecoding("11115112112") = 104. 但是，最后一个测试用例有message = "1221112111122221211221221212212212111221222212122221222112122212121212221212122221211112212212211211"，我的程序执行时间太长：

Expected_output:      782204094
My_program_output:    <empty due to timeout>

我写成countValidPaths()一个递归函数，它的递归调用在第 27、28 和 32 行。我可以看到这么大的输入会导致代码花费这么长时间，但我绞尽脑汁想弄清楚还有什么有效的解决方案将涵盖所有可能的组合。

因此，百万美元的问题：您有什么建议可以优化我当前的程序，以便它在更短的时间内运行？

4

1 回答 1

1

几个建议。首先，这个问题可能可以表述为动态规划问题。它对我来说有那种气味。你一遍又一遍地计算同样的事情。

第二个观点是“1”和“2”的长连续序列就可能性的数量而言是斐波那契数列。任何其他值都会终止序列。因此，您可以将字符串拆分为由任何其他数字终止的 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);
}

}

于 2017-04-18T03:39:41.957 回答