牛客网题目单词倒排(c语言)

链接:单词倒排_牛客题霸_牛客网 (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图,大家可以看一看

牛客网题目单词倒排(c语言)

这个步骤实现的代码如下:

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图:

牛客网题目单词倒排(c语言)


 图有点丑,大家看不懂,可以看代码

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;
}

上一篇:常用关键字


下一篇:Python调用C语言采坑,window和linux