题目分析

  1. 题目给出了我们一个字符串，包含一些空格，基本上是给出一句英文语句
  2. 我们需要将语句中单词的顺序倒转，然后输出逆序后的语句

方法一：输入流处理

  • 实现思路

    • 由于我们输入的内容包含空格，因此cin>>s输入时可以在输入流中遇到空格时断开

    • 因此输入流处理方式可以自动帮我们截出单个的单词

    • 我们只要每次将新读到的单词放到最前面组成新的字符串迭代即可

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string s;
    string t;
    while(cin >> s) {		  // 输入流处理字符串
        s += " " + t;		// 读到的新单词要放到字符串最前面，然后补一个空格，再添上上一轮的字符串
        t = s;				// 迭代成新的字符串
    }
    cout << t;			  // 输出最终结果
    return 0;
}

复杂度分析

  • 时间复杂度：O(n)O(n)，读取字符串的时间开销
  • 空间复杂度：O(n)O(n)，输出结果中申请的新字符串的空间开销

方法二：双指针

  • 实现思路
    • 首先用getline函数读取输入字符串
    • 然后使用双指针的思路
      • 假设i指针指向一个单词首字符
      • 假设j指针沿着i指针开始的位置，向后遍历直到发现一个空格字符为止
      • 现在的两个指针之间就是我们待处理的单词，将该单词压入words数组中
    • 最后将words数组倒置，重新组织成字符串输出即可

alt

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    string s;
    getline(cin , s);
    vector<string> words;
    for(int i = 0; i < s.size(); i++) {			// i 指针指向单词首字符
        int j = i + 1;							 // j 和 i 指针同起点开始遍历
        while(s[j] != ' ' && j < s.size()) {		// 直到 j 指针发现空格或到达字符串末尾
            j++;
        }
        words.push_back(s.substr(i, j - i));	 // 顺序压入单词
        i = j;									 // 迭代下一轮的单词起点
    }
    
    reverse(words.begin(), words.end());		 // 倒序words向量
    for(string s : words) {						 // 组织成新的字符串输出
        cout << s << " ";
    }
    
    return 0;
}

复杂度分析

  • 时间复杂度：O(n)O(n)，虽然其中包含双重循环，但是其作用只是一趟遍历字符串，时间开销仍是线性的
  • 空间复杂度：O(n)O(n)，使用了一个辅助字符串组的空间开销