微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 58-1. 翻转单词顺序

剑指offer 58-1. 翻转单词顺序

题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

示例 1：

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

示例 2：

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

示例 3：

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

说明：

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

题解

(字符串翻转) O(n)

  1. 使用双指针算法先翻转每个单词
  2. 然后翻转整个字符串

但在字符串的开头、中间、结尾都可能会有空格，我们需要把这三部分多余的空格去掉，只保留每个单词之间的空格。而且题目要求使用 O(1) 的空间完成，所以只能复用字符串，用一个指针 k 从前往后存储有效的字符部分，翻转结束后 k 后面多余的字符都删掉。

[i, j] 单词部分放到 [k, t] 位置上。

时间复杂度

整个字符串需要被扫描两遍，所以时间复杂度为 O(n)

空间复杂度

O(1)

C++ 代码

class Solution {
public:
    string reverseWords(string s) {
        int k = 0;
        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] == ' ') continue;
            // k 指向单词的开头，t 指向这个单词末尾的下一个位置
            int j = i, t = k;
            while (j < s.size() && s[j] != ' ') s[t ++ ] = s[j ++ ];
            // 翻转单词 s[k]~s[t - 1]
            reverse(s.begin() + k, s.begin() + t);
            s[t ++ ] = ' ';
            i = j, k = t;
        }
        // 翻转结束后 k 指向的是下一个单词的开头，现在让它指向前一个位置的空格
        if (k) k -- ;
        // 删除空格以及下标 k 后面的字符
        s.erase(s.begin() + k, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

Java 代码

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder sb = new StringBuilder();
        for (int i = words.length - 1; i >= 0; i -- ) {
            if (!words[i].isEmpty()) {
                sb.append(words[i]).append(" ");
            }
        }
        return sb.toString().trim();
    }
}

Python 代码

class Solution:
    def reverseWords(self, s: str) -> str:
        words = s.split()
        words.reverse()
        return ' '.join(words)

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer