LeetCode-06-单词顺序反转

发表于 更新于 阅读次数： 本文字数： 946 阅读时长 ≈ 3 分钟

LeetCode算法题：字符串中单词顺序反转。

题目

LeetCode：LeetCode 75 - 学习计划-06-反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

思路

从模块的功能看，输入内容可以有以下几种情况：

  1. 单字符单词、数字
  2. 混合数字的多字符单词

输出的情况较为固定，单词+空格…

代码

方案A-双指针

采用左右指针从输入字符串中从后向前找单词。

  1. right = left = len -1，从最右侧开始，寻找完整单词
  2. 以空格为界寻找左边界left
  3. 更新right = left ，寻找下一个单词
  4. 直到right = 0地址索引终止。
image can't load. 自后向前找单词O(n) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
char* reverseWords(char* s) {
    assert(s);

    int len = strlen(s);
    char* out_string = (char*)malloc(sizeof(char) * (len + 1));
    char* out_idx = out_string;

    char* right = s + len - 1;
    char* left = right;
    //处理单字符
    if (right == s)
    {
        memcpy((void*)out_idx, (void*)left, sizeof(char) * (right - left + 1));
        out_idx += right - left + 1;
        *out_idx = '\0';
        return out_string;
    }
    //处理多字符
    while (right > s)
    {
        while (*right == ' ' && right > s) right--;
        if (*right == ' ') break;
        left = right;
        while (*left != ' ' && left > s) left--;
        (left != s || (left == s && *left == ' ')) ? left += 1 : 0; //判断是否为首字符，防止越界
        memcpy((void*)out_idx, (void*)left, sizeof(char) * (right - left + 1));
        out_idx += right - left + 1;
        *(out_idx++) = ' ';
        right = left - 1;
    }
    *(out_idx - 1) = '\0';//字符串结束符
    return out_string;
}

此方案指针是从后向前移动，需要注意数组越界/指针越界。其中leetcode会报错，本地VS可运行成功。 > runtime error: store to address 0x502000000040 with insufficient space for an object of type ‘char’

另外此函数使用strlen函数空间复杂度为O(n)，需额外占用部分空间。

方案B-双反转

由于需要反转字符串内的单词顺序，因此可以分为以下几个步骤：

  1. 去除首尾空格、去除中间空格
  2. 反转整个字符串
  3. 反转单个单词

此种方案可以在原有字符串上进行改动，空间复杂度为O (1) ，修减空格、反转函数进行模块化。

image can't load. 反转字符串再反转单词O(1)
  1. 从前之后滤除空格。遇到单词后的空格/尾部结束符时仅输出1次空格，将后方字符前移。将尾部替换为结束符\0。
  2. 反转整个字符串。实现单词位置的反转。
  3. 反转单词。以空格/结束符为提示符查找单个单词进行反转。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
void trimString(char* s)
{
    int i = 0, j = 0;
    int len = strlen(s);

    //修剪前侧空格
    while (j<len && s[j] == ' ') j++;

    //修建中间空格
    while (j < len)
    {
        if (s[j] != ' ')
        {
            s[i++] = s[j++];
        }
        else
        {
            s[i++] = ' ';
            while (j < len && s[j] == ' ') j++;
        }
    }

    //修剪尾部空格
    if (i > 0 && s[i - 1] == ' ') i--;
    s[i] = '\0';

}

void reverseString(char* s,int start,int end)
{
    char tmp;
    while (start < end)
    {
        tmp = s[start];
        s[start] = s[end];
        s[end] = tmp;
        start++;
        end--;
    }
}

char* reverseWords(char* s) {
    if (s == NULL || *s == '\0') return NULL;

    trimString(s);

    int len = strlen(s);
    if (len == 0) return NULL;

    //反转整个字符串
    reverseString(s,0,len-1);
    
    int start = 0;
    for (int i = 0; i <= len; i++)
    {
        if (s[i] == ' ' || s[i] == '\0')
        {
            reverseString(s, start, i - 1);
            start = i + 1;
        }
    }

    return s;
}

————————— End —————————

远上寒山石径斜，白云深处有人家。–《山行》