数据结构
网络
关系数据库管理系统 (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 次浏览
广告