【千字分析】劍指 Offer 46. 把數字翻譯成字符串

來老鐵幹了這碗代碼 2021-09-19 04:14:21 阅读数:613

千字 分析 offer 字符串 字符

我是小張同學,立志用更簡潔的代碼做更高效的錶達


給定一個數字,我們按照如下規則把它翻譯為字符串:0 翻譯成 “a” ,1 翻譯成 “b”,……,11 翻譯成 “l”,……,25 翻譯成 “z”。一個數字可能有多個翻譯。請編程實現一個函數,用來計算一個數字有多少種不同的翻譯方法。

示例 1:

輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯,分別是"bccfi", “bwfi”, “bczi”, “mcfi"和"mzi”

提示:

0 <= num < 231

這是一道典型的動態規劃題目。對於一個數 num[i],我們有兩種選擇:

只翻譯自己;
和前面的數字組合翻譯,前提是組合的數在 10 − 25 10-25 1025 之間。
我們可以用 d p ( i ) dp(i) dp(i) 錶示前 i i i 個數字的翻譯方法數。根據以上兩種選擇,我們進行如下分析:

*如果只翻譯自己,比如 12345 12345 12345,如果 5 5 5 單獨翻譯,那麼方法數與 1234 1234 1234 是一樣的, d p ( i ) = d p ( i − 1 ) dp(i)=dp(i-1) dp(i)=dp(i1)
如果和前面的數字組合,比如 12351235,如果 3535 組合翻譯,從兩方面考慮:
35 35 35 看成一個整體,雖然加了 55 但是和沒加是一樣的,狀態 d p ( i ) = d p ( i − 1 ) dp(i)=dp(i-1) dp(i)=dp(i1)
35 35 35 組合就意味著不能再組合了,相當於條件 1 1 1 中的單獨翻譯自己,方法數與 12 12 12 是一樣的。這時 d p ( i ) = d p ( i − 2 ) dp(i)=dp(i-2) dp(i)=dp(i2)
以上兩種情况相加即可。
故狀態轉移函數為:

d p ( i ) = { d p ( i − 2 ) + d p ( i − 1 ) 前面兩個數在1–25之間 d p ( i − 1 ) e l s e dp(i)= \begin{cases} dp(i-2)+dp(i-1)& \text{前面兩個數在1--25之間}\\ dp(i-1)& \text{$else$} \end{cases} dp(i)={ dp(i2)+dp(i1)dp(i1)前面兩個數在1–25之間else

再考慮邊界條件:

d p ( 0 ) = d p ( 1 ) = 1 dp(0)=dp(1)=1 dp(0)=dp(1)=1

注意:條件 1 1 1 星號處不是 d p ( i ) = d p ( i − 1 ) + 1 dp(i)=dp(i-1)+1 dp(i)=dp(i1)+1。比如 12 12 12 如果 2 2 2 單獨翻譯, 12 12 12 只有一種翻譯方法。

C++動態規劃解法

class Solution {

public:
int translateNum(int num) {

string str = to_string(num);
int len = str.size();
if(len < 2) return len;
vector<int> dp(len+1);
dp[1] = 1;
dp[0] = 1;
for(int i = 2;i <= len;i++){

int n = (str[i-2] - '0') * 10 + (str[i-1] - '0');
if(n >= 10 && n <= 25) dp[i] = dp[i-2]+dp[i-1];
else dp[i] = dp[i-1];
}
return dp[len];
}
};

此外,還有一種更簡潔的數字求餘+遞歸方法

class Solution {

public:
int translateNum(int num) {

if(num > 9 && num < 26) return 2;
else if(num < 100) return 1;
if(num % 100 > 25 || num % 100 < 10) return translateNum(num/10);
else return translateNum(num/10) + translateNum(num/100);
}
};
版权声明:本文为[來老鐵幹了這碗代碼]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/09/20210919041420528P.html