面试题46:把数字翻译成字符串

给定一个数字,我们按照如下规则把它翻译为字符串:0翻译成“a”,1翻译成“b”,……,25翻译成“z”。一个数字可能有多种翻译。例如,12258有5种不同的翻译,分别是“bccfi”、“bwfi”、“bczi”、“mcfi”、“mzi”。求一个数字有多少种不同的翻译方法?

解题思路

  • 回溯法(暴力枚举)
  • 动态规划(回溯法可以减少递归次数)

上代码(C++香)

法一:回溯法,很easy
int countN = 0;

// 回溯法
void dfs(int num[], int n, int index){
    if(index == n){
        countN++;
        return ;
    }
    // 如果当前值是1,并且后面至少还有1位数
    if((num[index] == 1) && (index < n - 1))
        dfs(num, n, index + 2);
    // 如果当前值是2,并且后面至少还有1位数,并且下一位小于6
    else if((num[index] == 2) && (index < n - 1) && (num[index + 1] < 6))
        dfs(num, n, index + 2);
    // 也可以只走一步
    dfs(num, n, index + 1);
}
法二:动态规划

  找到状态转移方程:\(f(i)=f(i+1)+g*f(i+2)\),其中当第i位数字和第i+1两位数字拼接起来的数字在10~25之间时,g为1,否则为0。

int GetTranslationCount(const string& number)
{
    int length = number.length();
    int* counts = new int[length];
    int count = 0;
	// 倒推
    for(int i = length - 1; i >= 0; --i)
    {
        count = 0;
         if(i < length - 1)
         	count = counts[i + 1];
         else
            count = 1;
        if(i < length - 1)
        {
            int digit1 = number[i] - '0';
            int digit2 = number[i + 1] - '0';
            int converted = digit1 * 10 + digit2;
            if(converted >= 10 && converted <= 25)
            {
                if(i < length - 2)
                    // 加上上面的判断就是count = count[i + 1] + count[i + 2]
                    count += counts[i + 2];
                else
                    // i = length - 2,即倒数第二位就有两种方法
                    count += 1;
            }
        }
        counts[i] = count;
    }

    count = counts[0];
    delete[] counts;

    return count;
}

int GetTranslationCount(int number)
{
    if(number < 0)
        return 0;

    string numberInString = to_string(number);
    return GetTranslationCount(numberInString);
}
上一篇:矩阵快速幂-1246


下一篇:数据库之mysql多表查询(子查询)以及pymysql等相关内容-46