链接:单词倒排_牛客题霸_牛客网 (nowcoder.com)
题目描述:
对字符串中的所有单词进行倒排。
说明:
1、构成单词的字符只有26个大写或小写英文字母;
2、非构成单词的字符均视为单词间隔符;
3、要求倒排后的单词间隔符以一个空格表示;如果原字符串中相邻单词间有多个间隔符时,倒排转换后也只允许出现一个空格间隔符;
4、每个单词最长20个字母;
数据范围:字符串长度满足 1 \le n \le 10000 \1≤n≤10000
输入描述:
输入一行以空格来分隔的句子
输出描述:
输出句子的逆序
示例1
输入:
I am a student
输出:
student a am I
示例2
输入:
$bo*y gi!r#l
输出:
l r gi y bo
法一
定义一个字符指针数组,用于保存每个单词的起始字符地址,接下来将非字母字符全部替换成为字符串结尾标志,则单词字符字母遇到结尾就结束了,相当于把一个字符串以非字母字符进行切割成为了多个字符串,最终对字符指针数组进行逆序打印每个单词即可。
代码如下:
#include<stdio.h>
#include<string.h>
int main()
{
char str[10000]={0};//字符串长度最多10000
int len=0;
gets(str);
char*ptr=str;
char*word[10000]={NULL};
while(*ptr!='\0')
{//如果是字母字符,则是单词的起始字母,将这个字符的地址存入word
if(islower(*ptr)||isupper(*ptr))
{
word[len++]=ptr;//保存每个单词的起始地址
while(*ptr!='\0'&&(islower(*ptr)||isupper(*ptr)))
{//把本次的单词字母字符走完,直到遇到非字母字符
ptr++;
}
continue;//不能继续向下,因为下边ptr++会跳过当前非字母字符
}
*ptr='\0';//将非字母字符变为\0
ptr++;
}
for(int i=len-1;i>=0;i--)
{
printf("%s ",word[i]);//针对所有单词的起始地址逆序开始打印即可
}
return 0;
}
法二
分为两个步骤:
(1)翻转字符串
(2)删除多余的空格和非字母字符
(1)翻转字符串:
这里更我写过的一篇博客就是左旋字符串的思路一样,1.先把整个字符串倒序。2.将每个单词倒序,就可以得到翻转后的字符串
下面有gif图,大家可以看一看
这个步骤实现的代码如下:
void reverse(char* left, char* right)
{
while (left<=right)
{
char tmp = *left;
*left = *right;
*right = tmp;
right--;
left++;
}
}
char* reverseWords(char* s)
{
int i = 0, j = 0;
int len = strlen(s);
while (i < len)//将不是字母的变成空格,方便后面操作
{
if (islower(s[i]) || isupper(s[i]))
{
i++;
}
else
{
s[i] = ' ';
i++;
}
}
i = 0;
while (i < len)
{
//找出单词中第一个字母
while (j < len && isspace(s[j]))
{
j++;
}
i = j;
while (j < len && !(isspace(s[j])))
{
j++;
}
reverse(s + i, s + j - 1);
i = j;
}
reverse(s, s + len - 1);
RemoveSpace(s, len);
return s;
}
(2)删除多余的空格和非字母字符
因为上面已经将非字母字符改为空格,现在将多余空格删除就可以了
因为题目要求单词间保留一个空格,所以双指针在走时,记得把单词间第一个空格给覆盖过去
当然还要记得一开始可能就要空格,要记得清除。但双指针走到最后是,有两种情况,第一种就是双指针结束后没有空格,第二种就是有一个空格,在对应的情况结尾加上\0,表示字符串结束
gif图:
图有点丑,大家看不懂,可以看代码
void RemoveSpace(char* s, int len)
{
int i = 0;
int j = 0;
//防止一开始就是空格
while (isspace(s[j]))
{
j++;
}
//处理中间
while (j < len)
{
if (j > 0 && isspace(s[j - 1]) && isspace(s[j]))
{
j++;
}
else
{
s[i++] = s[j++];
}
}
//处理收尾
if (i > 0 && isspace(s[i - 1]))
{
s[i - 1] = '\0';
}
else
{
s[i] = 0;
}
}
完整代码:
#include<stdio.h>
void RemoveSpace(char* s, int len)
{
int i = 0;
int j = 0;
//防止一开始就是空格
while (isspace(s[j]))
{
j++;
}
//处理中间阶段
while (j < len)
{
if (j > 0 && isspace(s[j - 1]) && isspace(s[j]))
{
j++;
}
else
{
s[i++] = s[j++];
}
}
//处理收尾阶段
if (i > 0 && isspace(s[i - 1]))
{
s[i - 1] = '\0';
}
else
{
s[i] = 0;
}
}
void reverse(char* left, char* right)
{
while (left<=right)
{
char tmp = *left;
*left = *right;
*right = tmp;
right--;
left++;
}
}
char* reverseWords(char* s)
{
int i = 0, j = 0;
int len = strlen(s);
while (i < len)//将不是字母的变成空格,方便后面操作
{
if (islower(s[i]) || isupper(s[i]))
{
i++;
}
else
{
s[i] = ' ';
i++;
}
}
i = 0;
while (i < len)
{
//找出单词中第一个字母
while (j < len && isspace(s[j]))
{
j++;
}
i = j;
while (j < len && !(isspace(s[j])))
{
j++;
}
reverse(s + i, s + j - 1);
i = j;
}
reverse(s, s + len - 1);
RemoveSpace(s, len);
return s;
}
int main()
{
char str[10000] = { 0 };
gets(str);
char* ret = reverseWords(str);
printf("%s", ret);
return 0;
}