【問題描述】[中等]
給定一個數字,我們按照如下規則把它翻譯為字元串:0 翻譯成 “a” ,1 翻譯成 “b”,……,11 翻譯成 “l”,……,25 翻譯成 “z”。一個數字可能有多個翻譯。請程式設計實作一個函數,用來計算一個數字有多少種不同的翻譯方法。
示例 1:
輸入: 12258
輸出: 5
解釋: 12258有5種不同的翻譯,分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"
提示:
0 <= num < 231
【解答思路】
1. 動态規劃
1.1 字元串周遊
時間複雜度:O(N) 空間複雜度:O(N)
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[s.length()];
}
}
class Solution {
public int translateNum(int num) {
char[] sc = String.valueOf(num).toCharArray();
int n = sc.length;
int[] f = new int[n + 1];
f[0] = 1;
for (int i = 1; i <= n; i++) {
//if (sc[i - 1] >= '0' && sc[i - 1] <= '9') {
f[i] += f[i - 1];
//}
if (i > 1) {
int a = (sc[i - 2] - '0') * 10 + (sc[i - 1] - '0');
if (a >= 10 && a <= 25) {
f[i] += f[i - 2];
}
}
}
return f[n];
}
}
1.2 數字求餘(壓縮空間)
時間複雜度:O(N) 空間複雜度:O(1)
class Solution {
public int translateNum(int num) {
int a = 1, b = 1, x, y = num % 10;
while(num != 0) {
num /= 10;
x = num % 10;
int tmp = 10 * x + y;
int c = (tmp >= 10 && tmp <= 25) ? a + b : a;
b = a;
a = c;
y = x;
}
return a;
}
}
2. 逆推遞歸
遞歸出口是num是隻有一位數,以xyzcba為例,先取最後兩位(個位和十位)即ba,如果ba>=26,必然不能分解成f(xyzcb)+f(xyzc),此時隻能分解成f(xyzcb);但還有一種情況,就是ba<=9,也就是該數十位上為0,此時也不能分解。代碼如下:
時間複雜度:O(N^2) 空間複雜度:O(1)
class Solution {
public int translateNum(int num) {
if (num<=9) {return 1;}
//xyzcba
int ba = num%100;
if (ba<=9||ba>=26) {return translateNum(num/10);}
else {return translateNum(num/10)+translateNum(num/100);}
}
}
#### 【總結】
###### 1.從前往後 從後往前 由結果逆推
###### 2.細節
2.1 整形轉字元串
String s = String.valueOf(num);
2.2整形轉字元數組
char[] sc = String.valueOf(num).toCharArray();
###### 3. 動态規劃流程
第 1 步:設計狀态
第 2 步:狀态轉移方程
第 3 步:考慮初始化
第 4 步:考慮輸出
第 5 步:考慮是否可以狀态壓縮
轉載連結:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/mian-shi-ti-46-ba-shu-zi-fan-yi-cheng-zi-fu-chua-6/
參考連結:https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/solution/di-gui-qiu-jie-shuang-bai-by-xiang-shang-de-gua-ni/