資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
服裝研究
法律研究C++ 中的解碼方式 II
假設有一條訊息，包含字母 A-Z，使用以下對映方式編碼為數字：
'A' -> 1, 'B' -> 2, ... , 'Z' -> 26
現在，編碼的字串也可以包含字元 '*'，它可以被視為 1 到 9 之間的任何一個數字。因此，如果我們有包含數字和字元 '*' 的編碼訊息，那麼我們必須找到解碼它的總方法數。如果答案非常長，我們可以使用模 109 + 7 來獲得最終結果。因此，如果輸入只有 '*'，則可能有 9 種可能的方式，這些都是 1 到 9 的所有數字，因此這些是 A 到 I。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個函式 add()，它將接收 a, b，
- 返回 ((a mod m) + (b mod m)) mod m
- 定義一個函式 mul()，它將接收 a, b，
- 返回 ((a mod m) * (b mod m)) mod m
- 從主方法執行以下操作：
- n := s 的大小
- 定義一個大小為 n + 1 的陣列 dp
- dp[0] := 1
- 如果 s[0] 等於 '0'，則：
- 返回 0
- 如果 s[0] 等於 '*'，則 dp[1] := 9，否則 dp[1] := 1
- 初始化 i := 2，當 i <= n 時，更新 (i 加 1)，執行：
- first := s[i - 2], second := s[i - 1]
- 如果 second 等於 '*'，則：
- dp[i] := add(dp[i], mul(9, dp[i - 1]))
- 否則，如果 second > '0'，則：
- dp[i] := dp[i - 1]
- 如果 first 等於 '*'，則：
- 如果 second 等於 '*'，則：
- dp[i] := add(dp[i], mul(15, dp[i - 2]))
- 否則，如果 second <= '6'，則：
- dp[i] := add(dp[i], mul(2, dp[i - 2]))
- 否則
- dp[i] := add(dp[i], mul(1, dp[i - 2]))
- 如果 second 等於 '*'，則：
- 否則，如果 first 等於 '1' 或 first 等於 '2'，則：
- 如果 second 等於 '*'，則：
- 如果 first 等於 '1'，則：
- dp[i] := add(dp[i], mul(9, dp[i - 2]))
- 否則，如果 first 等於 '2'，則：
- dp[i] := add(dp[i], mul(6, dp[i - 2]))
- 如果 first 等於 '1'，則：
- 否則，如果 (first - '0') * 10 + (second - '0') <= 26，則：
- dp[i] := add(dp[i], dp[i - 2])
- 如果 second 等於 '*'，則：
- 返回 dp[n]
讓我們來看下面的實現，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli m = 1e9 + 7;
class Solution {
public:
lli add(lli a, lli b){
return ((a % m) + (b % m)) % m;
}
lli mul(lli a, lli b){
return ((a % m) * (b % m)) % m;
}
int numDecodings(string s) {
int n = s.size();
vector <int> dp(n + 1);
dp[0] = 1;
if(s[0] == '0') return 0;
dp[1] = s[0] == '*' ? 9 : 1;
for(int i = 2; i <= n; i++){
char first = s[i - 2];
char second = s[i - 1];
if(second == '*'){
dp[i] = add(dp[i], mul(9, dp[i - 1]));
}else if(second > '0'){
dp[i] = dp[i - 1];
}
if(first == '*'){
if(second == '*'){
dp[i] = add(dp[i], mul(15, dp[i - 2]));
}else if (second <= '6'){
dp[i] = add(dp[i], mul(2, dp[i - 2]));
}else{
dp[i] = add(dp[i], mul(1, dp[i - 2]));
}
}else if(first == '1' || first == '2'){
if(second == '*'){
if(first == '1'){
dp[i] = add(dp[i], mul(9, dp[i - 2]));
}else if(first == '2'){
dp[i] = add(dp[i], mul(6, dp[i - 2]));
}
}else if((first - '0') * 10 + (second - '0') <= 26){
dp[i] = add(dp[i], dp[i - 2]);
}
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << (ob.numDecodings("2*"));
}輸入
“2*”
輸出
15
更新於：2020年6月1日
208 次瀏覽
廣告