题解 | #表示数字#
表示数字
http://www.nowcoder.com/practice/637062df51674de8ba464e792d1a0ac6
表示数字
描述
将一个字符中所有的整数前后加上符号“*”，其他字符保持不变。连续的数字视为一个整数。注意：本题有多组样例输入。
输入描述：
输入一个字符串
输出描述：
字符中所有出现的数字前后加上符号“*”，其他字符保持不变
方法一
思路分析
本题我的第一个想法是，首先设置判断数组判断每一位上面的字符是否为数字，如果是数字则记录为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)$
查看14道真题和解析