给你一个长度一百万的字符串s,全是由0-9的数字构成, 再给你一百万次的修改操作,每
时间: 2023-09-28 20:02:27 浏览: 36
个操作都是将s中的某个位置的数字修改为另一个数字。请你设计一个高效的算法,能够在接受了这一百万次的修改操作后,快速地回答出某个子串(以字符串的形式给出)在修改后的字符串中出现了多少次。
思路:
1. 统计每个位置出现的数字,可以使用一个长度为10的数组count来记录。
2. 遍历修改操作,对于每个修改操作,将原位置的数字从count中减去,将新位置的数字加到count中。
3. 通过累加count中每个数字出现的次数,可以得到所有子串中某个数字出现的次数。
具体步骤:
1. 初始化一个长度为10的数组count,用于统计每个数字出现的次数。
2. 遍历字符串s,将每个字符转化为对应的数字,并将该数字在count中加1。
3. 遍历修改操作,对于每个操作,将原位置的数字在count中减1,将新位置的数字在count中加1。
4. 根据题目要求的子串范围,从count中累加目标数字出现的次数。
5. 返回目标子串在修改后的字符串中出现的次数。
时间复杂度分析:
遍历字符串s的时间复杂度为O(n),遍历修改操作的时间复杂度为O(m),累加目标数字出现次数的时间复杂度为O(1)。总的时间复杂度为O(n+m)。
这个算法的核心思想是通过统计每个数字出现的次数来快速计算出子串中某个数字出现的次数。通过对字符串s和修改操作的遍历,可以保证修改后的字符串的数字统计是准确的。算法效率高且简单,可以应用到实际问题中。
相关问题
c语言输入一字符串 将其中的所有数字删除,并输出改动后的字符串及其长度
```c
#include <stdio.h>
#include <string.h>
int main()
{
char str[100];
int i, j;
printf("请输入字符串:");
scanf("%s", str);
// 删除数字
j = 0;
for (i = 0; i < strlen(str); i++) {
if (str[i] < '0' || str[i] > '9') {
str[j] = str[i];
j++;
}
}
str[j] = '\0'; // 字符串末尾加上'\0',构成一个新的字符串
printf("改动后的字符串为:%s\n", str);
printf("字符串长度为:%d\n", strlen(str));
return 0;
}
```
运行结果:
```
请输入字符串:abc123def456
改动后的字符串为:abcdef
字符串长度为:6
```
信息安全很重要,特别是密码。给定一个5位的正整数n和一个长度为5的字母构成的字符串s,加密规则很简单,字符串s的每个字符变为它后面的第k个字符,其中k是n的每一个数位上的数字。第一个字符对应n的万位上
的数字,第二个字符对应n的千位上的数字,以此类推,直到最后一个字符对应n的个位上的数字。具体地,如果一个字符是字母表的第i个字母,那么它加密后的字符就是字母表的第(i+k) % 26个字母。这里%表示模运算,也就是取余数。
例如,假设n是12345,s是"abcde",那么它的加密结果就是"cfhik"。解释如下:1对应数字k为1,所以s的第一个字符a要变成它后面的第1个字符,也就是b;2对应数字k为2,所以s的第二个字符b要变成它后面的第2个字符,也就是d;以此类推,直到s的最后一个字符e要变成它后面的第5个字符,也就是k。
由于信息安全非常重要,为了保护你的密码,请勿在公共场合泄露你的密码,尤其是不要在网络上公开发布。