資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律學C++解碼給定訊息的程式
假設我們得到一個編碼的訊息，它是一串整數。這些整數可以對映到字母表中的特定字母。a對映到1，b對映到2，c對映到3，以此類推。還有一個字元'*'，它可以出現在訊息中，並且可以對映到1到9的任何數字。所以，給定一個訊息“input”，我們必須找出它可以解碼多少種方法。
因此，如果輸入類似於 input = "18"，則輸出將為2。
該訊息可以解碼為“ah”，因為1對映到“a”，8對映到“h”。此外，數字可以對映到“r”，因為18對映到“r”。因此，輸入共有2種解碼方式。
為了解決這個問題，我們將遵循以下步驟：
- n := 輸入的長度
- 定義一個大小為n+1的陣列 dynArr 並將其初始化為零
- p := 1
- k := '0'
- dynArr[0] := 1
- for i := 1 to n do −
- c := input[i - 1]
- 如果 c 等於 0 且 k 不等於 '1' 或 '2' 或 '*'，則：
- p := 0
- 退出迴圈
- 如果 input[i - 1] 等於 '*'，則：
- dynArr[i] := (dynArr[i - 1] * 9) mod m
- 如果 k 等於 '1' 或 '*'，則：
- dynArr[i] := (dynArr[i] + dynArr[i - 2] * 9) mod m
- 如果 k 等於 '2' 或 '*'，則：
- dynArr[i] := (dynArr[i] + (dynArr[i - 2] * 6) mod m) mod m
- 否則，
- 如果 c 不等於 '0'，則：
- 如果 k 等於 '1' 或 '*'，則：
- dynArr[i] := (dynArr[i] + dynArr[i - 2]) mod m
- 如果 (k 等於 '2' 或 '*') 且 input[i - 1] <= '6'，則：
- dynArr[i] := (dynArr[i] + (dynArr[i - 2]) mod m) mod m
- 如果 k 等於 '1' 或 '*'，則：
- k := c
- 如果 p 不為零，則返回 dynArr[n]，否則返回 0
示例
讓我們看看下面的實現，以便更好地理解：
#include<bits/stdc++.h>
using namespace std;
const long m = 1e9 + 7;
int solve(string input) {
int n = input.length();
long long dynArr[n + 1] = {0};
bool p = 1;
char k = '0';
dynArr[0] = 1;
for (int i = 1; i <= n; i++) {
char c = input[i - 1];
if (c == 0 && !(k == '1' || k == '2' || k == '*')) {
p = 0;
break;
}
if (input[i - 1] == '*') {
dynArr[i] = (dynArr[i - 1] * 9) % m;
if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2] * 9) % m;
if (k == '2' || k == '*') dynArr[i] = (dynArr[i] + (dynArr[i - 2] * 6) % m) % m;
} else {
if (c != '0') dynArr[i] = dynArr[i - 1];
if (k == '1' || k == '*') dynArr[i] = (dynArr[i] + dynArr[i - 2]) % m;
if ((k == '2' || k == '*') && input[i - 1] <= '6') dynArr[i] = (dynArr[i] + (dynArr[i - 2]) % m) % m;
}
k = c;
}
return p ? dynArr[n] : 0;
}
int main() {
cout<< solve("18") <<endl;
return 0;
}輸入
18
輸出
2
更新於：2021年10月19日
984 次瀏覽
廣告