刷题_反转字符串里的单词

发表于2024-04-02更新于2025-09-28阅读次数

内容

原题名叫做：反转字符串中的单词。不是把每个字符全部反转，而是按词为整体反转。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入：s = "the sky is blue"
输出："blue is sky the"

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：
1. 1 <= s.length <= 104
2. s 包含英文大小写字母、数字和空格 ' '
3. s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

分析

  1. 首先把多余的空格删除
  2. 把整体进行逆序
  3. 按空格划分，逆序每个单词

代码

解1_

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
class Solution {
public:
    // 返回结尾下标
    int moveLeft(std::string& s, int idx, int wordLen, int step)
    {
        // if(s == nullptr || idx < 0) return;
        if (step != 0)
        {
            int i = 0;
            while (i < wordLen)
            {
                s[idx - step + i] = s[idx + i];
                ++i;
            }
        }
        return idx - step + wordLen - 1;
    }
    std::string removeExtraSpace(std::string& s)
    {
        int cur = s.length() - 1;
        while (s[cur] != '\0' && s[cur] == ' ')
        {
            --cur;
        }
        int lastSpace = cur;
        int validEndIdx = cur;
        while (cur >= 0)
        {
            while (cur >= 0 && s[cur] != '\0' && s[cur] != ' ')
            {
                --cur;
            }
            lastSpace = cur;
            ++cur;
            while (lastSpace >= 0 && s[lastSpace] != '\0' && s[lastSpace] == ' ')
            {
                --lastSpace;
            }
            if (lastSpace != -1)
                ++lastSpace;
            validEndIdx = moveLeft(s, cur, validEndIdx - cur + 1, cur - lastSpace - 1);
            cur = lastSpace - 1;
        }
        s.resize(validEndIdx + 1);
        return s;
    }
    void reverseWord(char* cp, int len)
    {
        for (int i = 0; i < len / 2; ++i)
        {
            char tmp = cp[i];
            cp[i] = cp[len - 1 - i];
            cp[len - 1 - i] = tmp;
        }

    }
    std::string reverseWords(std::string s)
    {
        removeExtraSpace(s);
        reverseWord((char *)s.c_str(), s.length());
        const char* ccp = s.c_str();
        char* cp = (char *)ccp;
        int len = 0;
        // 这里如果直接给ccp+1会越过\0导致越界，leetcode报错heap-buffer-overflow通不过
        while (*ccp != '\0')
        {
            while (*ccp != '\0' && *ccp != ' ')
            {
                ++len;
                ++ccp;
            }
            reverseWord(cp, len);
            len = 0;
            if(*ccp != '\0')
            {
                ++ccp;
                cp = (char*)ccp;
            }
        }
        return s;
    }
};
int main()
{
    Solution sol = Solution();
    std::string str("  345  1 2 89    ");
    std::string res = sol.reverseWords(str);
    std::cout << res << std::endl;
}

测试结果：345 1 2 89
C语言版

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
int moveLeft(char* s, int idx, int wordLen, int step)
{
    if (step != 0)
    {
        int i = 0;
        while (i < wordLen)
        {
            s[idx - step + i] = s[idx + i];
            ++i;
        }
    }
    return idx - step + wordLen - 1;
}
int removeExtraSpace(char* s, int len)
{
    if (len <= 0) return 0;
    int cur = len - 1;
    while (cur >= 0 && s[cur] != '\0' && s[cur] == ' ')
    {
        --cur;
    }
    int lastSpace = cur;
    int validEndIdx = cur;
    while (cur >= 0)
    {
        while (cur >= 0 && s[cur] != '\0' && s[cur] != ' ')
        {
            --cur;
        }
        lastSpace = cur;
        ++cur;
        while (lastSpace >= 0 && s[lastSpace] != '\0' && s[lastSpace] == ' ')
        {
            --lastSpace;
        }
        if (lastSpace != -1)
            ++lastSpace;
        validEndIdx = moveLeft(s, cur, validEndIdx - cur + 1, cur - lastSpace - 1);
        cur = lastSpace - 1;
    }
    s[validEndIdx + 1] = '\0';
    return validEndIdx + 1;
}
void reverseWord(char* cp, int len)
{
    for (int i = 0; i < len / 2; ++i)
    {
        char tmp = cp[i];
        cp[i] = cp[len - 1 - i];
        cp[len - 1 - i] = tmp;
    }
}
char* reverseWords(char* s)
{
    const char* ccp = s;
    int slen = 0;
    while (*ccp++ != '\0')
    {
        ++slen;
    }
    int newlen = removeExtraSpace(s, slen);
    reverseWord(s, newlen);
    ccp = s;
    char* cp = s;
    int len = 0;
    while (*ccp != '\0')
    {

        while (*ccp != '\0' && *ccp != ' ')
        {
            ++len;
            ++ccp;
        }
        reverseWord(cp, len);
        len = 0;
        // 这里如果直接给ccp+1会越过\0导致越界，leetcode报错heap-buffer-overflow通不过
        if (*ccp != '\0')
        {
            ++ccp;   // 最后一次会越界
            cp = (char*)ccp;
        }
    }
    return s;
}

优化消除空格函数

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
// 返回新串长度
int removeExtraSpace(char* s, int len)
{
    int i = 0;
    int cur = 0;
    while (i < len)
    {
        while (i < len && s[i] == ' ')
        {
            ++i;
        }
        // s[i] != ' ', = char
        while (i < len && s[i] != ' ')
        {
            s[cur++] = s[i++];
        }
        if (i >= len)
        {
            if (i > cur)
            {
                s[cur] = '\0';
            }
            // 一定要break
            break;
        }
        // s[i] == ' ' || s[i] == '\0'
        s[cur++] = s[i++];
    }
    // 坑
    if (s[cur - 1] == ' ')
    {
        --cur;
        s[cur] = '\0';
    }
    return cur;
}

坑

心得

这个题目属于

总结