N0.151 翻转字符串里的单词

给定一个字符串,逐个翻转字符串中的每个单词。

结果

执行用时 :
执行用时 :
8 ms, 在所有 cpp 提交中击败了 90.75%的用户
内存消耗 :
11.6 MB, 在所有 cpp 提交中击败了 30.30%的用户

分析

两种思路。

法一:标准的栈思路

这里我发现了一个很有趣的现象,就是如果使用了栈结构,然后对输出的 res 进行正向的相加,结果比不使用栈结构,对 res 进行逆向的相加,时间消耗和空间消耗都要低很多。
逆向相加省去了使用栈结构,并且理论上空间消耗只在 O(n)。
初步推测是因为逆向增加的移位字符会随着 res 的增加而迅速上升,进而拖慢了整体的进度。

以下是逆向增加的执行结果。

执行用时 :
28 ms, 在所有 cpp 提交中击败了 18.55%的用户
内存消耗 :
66.8 MB, 在所有 cpp 提交中击败了 18.94%的用户

法二:stringstream

stringstream 法可以用于分割被空格、制表符等符号分割的字符串。
但是由于 stringstream 的构造函数会特别消耗内存,所以最终的结果(无论是时间还是空间)十分难看。

IMG_8CC94A1E421C-1.jpeg

法三:Python 一行解法

很鲨雕的解法。。。python 果然还是简单啊

class Solution:
    def reverseWords(self, s: str) -> str:
        return ' '.join(re.split(' *',s.strip())[::-1])

代码

# 栈
class Solution {
public:
    string reverseWords(string s) {
        int len = s.size();
        s += " ";
        stack<string> ss;
        for(int i = 0; i < len; ++i){
            if(s[i] == ' ') continue;
            int left = i;
            while(s[i] != ' ') ++i;
            ss.push(s.substr(left,i-left));
        }
        string res = "";
        while(!ss.empty()){
            res += ss.top() + " ";
            ss.pop();
        }
        return res.substr(0,res.length()-1);
    }
};


# 流
class Solution {
public:
    string reverseWords(string s) {
        stringstream ss;
        string ans="",temp;
        ss<<s;
        while(ss>>temp)
            ans=" "+temp+ans;
        if(ans!="")
            ans.erase(ans.begin());
        return ans;
    }
};

后记

时隔一周,再临 LeetCode。
这一周干了一件很没有意义的事情,无论从那个方面来说都非常地没有意义。
这段经历让我更深刻地认识到一件事情,不是所有的人都值得托付信任。