托福备考规划051620

发表于 2020-04-19 更新于 2021-12-20 分类于英语学习
本文字数： 1.3k 阅读时长 ≈ 1 分钟

文章被加密了，输入密码后方可阅读~

LeeCode151 翻转字符串里的单词

发表于 2020-04-10 更新于 2021-12-21 分类于计算机，算法
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

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

示例 1：

1 2	输入: "the sky is blue" 输出: "blue is sky the"

示例 2：

1
2
3

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

题目链接：151. 翻转字符串里的单词

C++解题

思路1：整体反转+单词反转

我们也可以不使用语言中的 API，而是自己编写对应的函数。在不同语言中，这些函数实现是不一样的，主要的差别是有些语言的字符串不可变（如 Java 和 Python)，有些语言的字符串可变（如 C++)。
对于字符串可变的语言，不需要再额外开辟空间了，直接在字符串上原地实现。在这种情况下，反转字符和去除空格可以一起完成。

代码如下：

class Solution {
public:
    string reverseWords(string s) {
        // 反转整个字符串
        reverse(s.begin(), s.end());

        int n = s.size();
        int idx = 0;
        for (int start = 0; start < n; ++start) {
            if (s[start] != ' ') {
                // 填一个空白字符然后将idx移动到下一个单词的开头位置
                if (idx != 0) s[idx++] = ' ';

                // 循环遍历至单词的末尾
                int end = start;
                while (end < n && s[end] != ' ') s[idx++] = s[end++];

                // 反转整个单词
                reverse(s.begin() + idx - (end - start), s.begin() + idx);

                // 更新start，去找下一个单词
                start = end;
            }
        }
        s.erase(s.begin() + idx, s.end());
        return s;
    }
};

复杂度分析：

时间复杂度: \(O(N)\)，其中 N 为输入字符串的长度。
空间复杂度: \(O(1)\)

思路2 利用双端队列或栈

将字符串分成单词一个个放到双端队列或栈中,按照栈的顺序输出

代码如下：

class Solution {
public:
    string reverseWords(string s) {
        int left = 0, right = s.size() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s[left] == ' ') ++left;

        // 去掉字符串末尾的空白字符
        while (left <= right && s[right] == ' ') --right;

        deque<string> d;
        string word;

        while (left <= right) {
            char c = s[left];
            if (word.size() && c == ' ') {
                // 将单词 push 到队列的头部
                d.push_front(move(word));
                word = "";
            }
            else if (c != ' ') {
                word += c;
            }
            ++left;
        }
        d.push_front(move(word));
        
        string ans;
        while (!d.empty()) {
            ans += d.front();
            d.pop_front();
            if (!d.empty()) ans += ' ';
        }
        return ans;
    }
};