数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中统计相邻字符ASCII值差为1的字符串数量
给定一个数字num作为输入。目标是计算长度为num的可能的字符串数量，使得所有相邻字符的ASCII值之差为1。
如果num为2，则字符串将为“ab”、“ba”、“bc”、“cb”，……“yz”、“zy”。
让我们通过例子来理解
输入 − num=3
输出 − 相邻字符ASCII值差为1的字符串数量为 − 98
解释 − 一些示例字符串为：“abc”、“aba”、“cde”……“xyx”、“zyz”、“xyz”。
输入 − num=2
输出 − 相邻字符ASCII值差为1的字符串数量为 − 50
解释 − 一些示例字符串为：“ab”、“ba”、“cd”……“xy”、“zy”、“yz”。
下面程序中使用的算法如下
对于长度 = 2。
以a开头的字符串 = “ab”
以b开头的字符串 = “ba”, “bc”
以c开头的字符串 = “cd”, “cb”...............
对于长度 = n。
以a开头的字符串 = 长度为n-1且以b开头的字符串的数量
以b开头的字符串 = 长度为n-1且以a或c开头的字符串的数量
以c开头的字符串 = 长度为n-1且以b或d开头的字符串的数量
我们将使用动态规划来解决这个问题。
使用一个数组arr[num+1][27]。arr[i][j]中包含长度为i且以字母序号j开头的字符串的数量。所有arr[1][j]对于字符串“a”、“b”……“z”都将为1。
其余的arr[2 to num+1][0 to 25]，设置arr[i][j]=arr[i-1][j+1] (j=0)。否则设置arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1];
结果将是第num行的计数之和。
输入整数num
函数difference_strings(int num)接收num并返回相邻字符ASCII值差为1的字符串数量
将初始计数设置为0。
用全0初始化arr[num + 1][27]。
用全1初始化arr[1][0 to 25]。
使用两个for循环遍历二维数组arr[][]，从第2行到最后一行，列从0到25，遍历所有26个字母。
对于j=0，起始字符为'a'。将当前计数设置为arr[i][j] = arr[i - 1][j + 1];
否则设置arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1])
现在，在上述循环结束后，遍历最后一行并将arr[num][ 0 to 25]添加到计数中。
返回计数作为结果。
示例
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
return 0;
}输出
如果我们运行上面的代码，它将生成以下输出：
Count of strings where adjacent characters are of difference one are: 50
853 次浏览
