表示数字

描述

将一个字符中所有的整数前后加上符号“*”，其他字符保持不变。连续的数字视为一个整数。
注意：本题有多组样例输入。
输入描述：
输入一个字符串
输出描述：
字符中所有出现的数字前后加上符号“*”，其他字符保持不变

方法一

思路分析

本题我的第一个想法是，首先设置判断数组判断每一位上面的字符是否为数字，如果是数字则记录为1，之后遍历字符串数组，如果是数字 首先输出*，输出连续的数字，最后输出*，不过代码没有通过

核心代码 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string temp;
    while(cin>>temp)
    {
        //cout<<temp<<endl;
        int n=temp.length();
        //cout<<n<<endl;
        vector<int>dp(n,0);
        for(int i=0;i<n;i++)
        {
            if(isdigit(temp[i]))//判断是否为数字 1表示为数字
            {
                if(i==0) dp[i]=1;
                else dp[i]=dp[i-1]+1;
            }
        }
//         for(int i=0;i<n;i++)
//             cout<<dp[i];
//         cout<<endl;
        string new_temp;
        int i=0;
        for(;i<n;)
        {
            if(dp[i]==0)//不是数字直接输出
            {
                cout<<temp[i];
                i++;
            }
            if(dp[i]==1)//如果是数字 首先输出*
            {
                int k=i;
                int count=1;
                cout<<"*";
                while(dp[i+1]!=0&&i<n)//输出连续的数字
                {
                    i++;
                }
                int j=i;
                
                cout<<temp.substr(k,j-k);
                cout<<"*";
                i=j;
            }      
        }
     //cout<<temp<<endl;
    }
    return 0;
}

复杂度分析

  • 时间复杂度：时间复杂度为$O(n)$
  • 空间复杂度：定义了一个数组判断是否为数字，空间复杂度为$O(1)$


方法二

思路分析

方法一种其实本不必设置一个数组存储判断结果，因此方法二直接判断，暴力解法

图解

字符串 Jkdi234klo
输出 J

k
d
i
遇到数字先输出* *

234
遇到的不是数字，输出*
 *

k
l
o


核心代码 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string temp;
    while(cin>>temp)
    {
        int n=temp.length();
        for(int i=0;i<n;)//单个字符判断
        {
            if(isdigit(temp[i]))//数字判断
            {
                cout<<"*";
                while(isdigit(temp[i]))//找到数字子串并输出
                {
                   cout<<temp[i];
                    i++;
                }
                cout<<"*";//数字子串最后的位置输出*
            }
            else
            {
                cout<<temp[i];
                i++;
            }
        }
        cout<<endl;
        
    }
}

复杂度分析

  • 时间复杂度：时间复杂度为$O(n)$
  • 空间复杂度：空间复杂度为$O(1)$

方法三

思路分析

不调用判断数字的函数

核心代码 

#include<stdio.h>
#include<string.h>
int main()
    {
    int i,len;
    char str[1000];
    while(scanf("%s",str)!=EOF)
        {
        len=strlen(str);
        for(i=0;i<len;)
            if(str[i]>='0'&&str[i]<='9')
            {
            printf("*");
            while(str[i]>='0'&&str[i]<='9')
                {
                printf("%c",str[i]);
                i++;
            }
            printf("*");
        }
        else 
        {
            printf("%c",str[i]);
            i++;
        }
    printf("\n");
    }
    return 0;
}

复杂度分析

  • 时间复杂度：时间复杂度为$O(n)$
  • 空间复杂度：空间复杂度为$O(1)$