题意

直接描述就是题意：将一个字符中所有的整数前后加上符号“*”，其他字符保持不变。连续的数字视为一个整数

限制:字符串长度不大于100

方法

状态记录

说是在数字前后加上星号。所以我们需要判断数字开始和结束。

当前一个字符不是数字，而现在的字符是数字时，表示这里是数字的开始。

当前一个字符是数字，而现在的字符不是数字时，这里是数字的结束。

因此我们遍历字符串，在遍历过程中利用一个状态变量来记录上一个字符是否是数字，来判断是否需要加星号

以样例数据Jkdi234klowe90a3为例

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    char s[110];
    while(~scanf("%s",s)){
        int state = 0;
        int n = strlen(s);
        for(int i = 0;i<n;i++){ // 遍历字符串
            if(state == 0 && isdigit(s[i])){ // 上一个是非数字，现在是数字
                printf("*");
            }else if(state == 1 && !isdigit(s[i])){ // 上一个是数字，现在非数字
                printf("*");
            }
            printf("%c",s[i]);
            state = isdigit(s[i]); // 更新
        }
        if(state == 1){ // 结尾处理
            printf("*");
        }
        printf("\n");
    }
    return 0;
}

复杂度分析

时间复杂度: 除了读入的部分$O(n)O(n)$ ,剩余的处理过程中，遍历了字符串，遍历的位置是常数时间的处理效率，所以总时间复杂度为$O(n)O(n)$

空间复杂度: 主要的空间是储存字符串，所以空间复杂度为$O(n)O(n)$。对于字符串的储存我们除了读入参数输入，并无修改操作，除了储存字符串存储其余的变量为常数个，所以除了读入的必要的部分的空间复杂度为$O(1)O(1)$

字符数组的指针技巧

我们的字符数组在内存上是连续的。而读入字符串会让字符串的结尾多一个 '\0'

结合这两点，我们让读入的字符从字符数组的下标1开始，这样下标0始终是'\0'

同时结束的字符也是'\0', 所以字符串被读入后，在字符数组中的记录实际为

'\0'字符串'\0'

由此我们就可以减少边界的额外if处理，直接比较相邻字符 是否一个数字一个非数字了

代码

#include<bits/stdc++.h>
using namespace std;
char s[110]; // 初始化为 0
int main(){
    while(~scanf("%s",s+1)){ // 读入从s[1]开始
        int n = strlen(s+1);
        for(int i = 0;i <= n;i++){
            if(isdigit(s[i])^isdigit(s[i+1])){ // 相邻字符判断
                printf("*");
            }
            printf("%c",i == n?'\n':s[i+1]); // 结尾处理
        }
    }
    return 0;
}

复杂度分析

时间复杂度: 本质上和第一种算法时一样的，只是简化了边界处理逻辑，所以时间复杂度依然是$O(n)O(n)$

空间复杂度: 依然主要是字符串读入,所以空间复杂度为$O(n)O(n)$。对于字符串的储存我们除了读入参数输入，并无修改操作，除了储存字符串存储其余的变量为常数个，所以除了读入的必要的部分的空间复杂度为$O(1)O(1)$