HJ96 题解 | #表示数字#

题意分析

• 给你一个字符串，需要你将这个字符串的所有整数的前后加上*，其他字符的相对顺序保持不变。

思路分析

• 思路比较简单，为了方便处理第一个和最后一个字符串的特殊情况，我们先在初始的字符串的前后各添加一个无关字符x,然后我们对这个字符串进行遍历.

  • 我们每遍历一个字符，先判断这个字符是否是非数字字符，然后再判断这个字符的前面是否是数字字符。如果满足，那么说明这个字符的前面是一个整数，我们在这个字符的前面加上一个*即可。
  • 我们每遍历一个字符，先判断这个字符是否是数字字符，然后再判断这个字符的前面是否是非数字字符。如果满足，那么说明这个字符的后面是一个整数，我们在这个字符的前面加上一个*即可。

• 另外，我们需要用一个额外的字符串来存储最后的结果。

• 样例图解如下

C++

• 代码如下
  • 对字符串只进行了一次遍历处理，时间复杂度为$O(n)O(n)$
  • 用一个额外的字符串来存储最后的结果，空间复杂度为$O(n)O(n)$

#include<bits/stdc++.h>

using namespace std;
bool judge(char x){
    return x<='9'&&x>='0';
}
int main(){
    string s;
    while(cin>>s){
        string ans="";
        // 在首尾添加一个非数字字符，方便进行处理
        s="x"+s+"x";
        int len=s.size();
        for(int i=1;i<len;i++){
            // 如果这个字符是数字，前一个字符不是数字
            if(judge(s[i])){
                if(!judge(s[i-1])){
                    ans+="*";
                }
                ans+=s[i];
            }
            // 如果这个字符不是数字，前一个字符是数字
            if(!judge(s[i])){
                if(judge(s[i-1])){
                    ans+="*";
                }
                ans+=s[i];
            }
        }
        s="";
        len=ans.size();
        // 删除最后一个字符就是我们要的答案了
        for(int i=0;i<len-1;i++){
            s+=ans[i];
        }
        cout<<s<<endl;
    }
    return 0;
}

Python

• 代码如下
  • 对字符串只进行了一次遍历处理，时间复杂度为$O(n)O(n)$
  • 用一个额外的字符串来存储最后的结果，空间复杂度为$O(n)O(n)$

while True:
    try:
        s=input()
        out=''
        # flag为1，表示之前的是数字，否则表示之前的是非数字
        flag=0
        for i in s:
            # 如果这个字符是数字
            if i.isdigit():
                # 如果之前的是非数字
                if flag ==0:
                    out += '*' + i
                    flag=1
                else:
                    out += i
            # 如果此时这个字符是非数字
            else:
                # 如果之前的是数字
                if flag==1:
                    out += '*'+i
                    flag=0
                else:
                    out += i
        if s[-1].isdigit():
            out +='*'
        print(out)
    except:
        break