leetcode 151. 翻转字符串里的单词 c代码三种方案

最新推荐文章于 2024-02-06 03:30:22 发布

yyyyyyyuande

最新推荐文章于 2024-02-06 03:30:22 发布

阅读量1.2k

点赞数 1

分类专栏： Leetcode 文章标签： leetcode 翻转字符串里的单词

本文链接：https://blog.csdn.net/fuyuande/article/details/98941427

版权

Leetcode 专栏收录该内容

21 篇文章

订阅专栏

如题：

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

示例 2：
输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：
输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

说明：
无空格字符构成一个单词。
输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
 

进阶：
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

这道题在数组专项练习遇到过，第一反应就是简单，没多想，上去就是撸代码，结果考虑边界用时N分钟，晕了过去。

回过头仔细思考了下，这道题逻辑不难，但是边界处理部分很重要，稍有不慎就会出错，尤其是c语言。

方案大概有三种：

方法1：从后往前逐个拷贝单词到另一个数组中，需要使用额外数组空间N。
方法2：像镜像一样，先反转整个字符串，然后逐个反转每个单词，最后去除头部空格，中间空格以及尾部空格。此方案优点是空间复杂度低。

方法3：使用栈，从后往前将单词入栈，然后顺序出栈即可，同方法1一样，需要使用额外辅助空间。

题目进阶要求c语言使用O(1)复杂度，方案2可满足要求。三种方案都不复杂，但是代码实现还是很能考验水平，建议多练。

下面是方案2 镜像反转的c代码实现：


/*
 *  特殊情况：参数为空或者长度小于1
 *  方法1：从后往前逐个拷贝单词到另一个数组
 *  方法2：反转整个字符串，然后反转每个单词
 *  方法3： 从后往前应该使用栈
 */

void swap(char *a,  char *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}

void reverseWord(char *s, int first, int end)
{
    if (first == end)
        return;
    while(first < end)
        swap(s+(first++), s+(end--));
    return;   
}

char * reverseWords(char * s){
    int i, j, first, last,len,c;
    char *p, clast;
    
    //参数为空或者长度为0返回
    if (!s || strlen(s) < 1)
        return s;
    
    //反转字符串
    len = strlen(s);
    
    for (i = 0, j = len - 1; i < j;)
    {
        if (s[i] != s[j])
            swap(s+(i++), s+(j--));
        else
        {
            i++; j--;
        }   
    }
             
    //反转每个单词
    last = first = 0;
    while (1)
    {
        while(first < len && s[first] == ' ')first++;             
        if (first >= len)
            break;
        else
        {
            last = first;
            while(last < len && s[last] != ' ')last++;
            reverseWord(s, first, last - 1);
        }
        if (last >= len)
            break;
        first = last;
    }
    
    printf("%s\n", s);
        
    //去除开头空格
    i = 0;
    while(i < len && s[i] == ' ')
    {
        len--;
        s++;
    }   
                 
    if (len < 0)
        return s;

    //删除多余空格
    for (i = 0, j = 0, c = 0; i < len-1; i++)
    {
        while (i < len - 1 && s[i] == ' ' && s[i] == s[i+1])
        {
            c++; i++;
        }
        
        if (c && i < len - 1 && s[i+1] != ' ')
        {
            i++;
            while(i < len && s[i] != ' ')
            {
                swap(s+i-c, s+i);
                i++;
            }
            i--;
        }
    }

    //去除末尾空格
    len = strlen(s);
    while(len > 0 && s[len-1] == ' ')
    {
        s[len-1] = '\0';
        len--;
    }
    return s; 
}

=============================================================================================

Linux应用程序、内核、驱动开发交流讨论群(745510310)，感兴趣的同学可以加群讨论、交流、资料查找等，前进的道路上，你不是一个人奥^_^。