关于leetcode:每日一练31翻转单词顺序

title: 每日一练（31）：翻转单词程序

categories:[剑指offer]

tags:[每日一练]

date: 2022/03/05

每日一练（31）：翻转单词程序

输出一个英文句子，翻转句子中单词的程序，但单词内字符的程序不变。为简略起见，标点符号和一般字母一样解决。例如输出字符串”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”

解释: 如果两个单词间有多余的空格，将反转后单词间的空格缩小到只含一个。

阐明：

无空格字符形成一个单词。

输出字符串能够在后面或者前面蕴含多余的空格，然而反转后的字符不能包含。

如果两个单词间有多余的空格，将反转后单词间的空格缩小到只含一个。

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

办法一：模板代码

办法出处：https://leetcode-cn.com/probl…

思路剖析

这类题目我的惯常做法，也是核心思想，就是先把句子中所有字符串取出放入字符串数组，再对数组中的字符串进行操作后从新连贯即可，具体问题具体细节还需

要按题目要求剖析

而遍历句子取字符串的思路，就是遇到字符把它放入长期字符串，遇到空格或者标点(如果有标点)，就把长期字符串输入，并且清空

模板代码

须要留神的是：这类题目能够分为两类，一类是有前置或者后置空格的，另一类是没有前置和后置空格的。

模板1、如果有前后置空格，那么必须判断长期字符串非空能力输入，否则会输入空串

s += " ";    //这里在最初一个字符地位加上空格，这样最初一个字符串就不会脱漏
string temp = "";   //长期字符串
vector<string> res; //寄存字符串的数组
for (char ch : s) { //遍历字符句子
    if (ch == ' ') {//遇到空格
        if (!temp.empty()) {     //有前后置空格，须要判断长期字符串非空，反之能够去掉此判断
            res.push_back(temp);
            temp.clear();        //清空长期字符串
        }
    } else {
        temp += ch;
    }
}

模板2、没有前后置的空格不须要判断空串

s += " ";    //这里在最初一个字符地位加上空格，这样最初一个字符串就不会脱漏
string temp = "";   //长期字符串
vector<string> res; //寄存字符串的数组
for (char ch : s) { //遍历字符句子
    if (ch == ' ') {//遇到空格
        res.push_back(temp);
        temp.clear();        //清空长期字符串
    } else {
        temp += ch;
    }
}

本题应用：模板1+反转整个字符数组+从新连贯

string reverseWords(string s) {
    s += " ";    //这里在最初一个字符地位加上空格，这样最初一个字符串就不会脱漏
    string temp = "";   //长期字符串
    vector<string> res; //寄存字符串的数组
    for (char ch : s) { //遍历字符句子
        if (ch == ' ') {//遇到空格
            if (!temp.empty()) {     //有前后置空格，须要判断长期字符串非空，反之能够去掉此判断
                res.push_back(temp);
                temp.clear();        //清空长期字符串
            }
        } else {
            temp += ch;
        }
    }
    s.clear();
    reverse(res.begin(), res.end());
    for (string &str : res) {
        s += str + ' ';
    }
    s.pop_back();    //去除最初一个空格
    return s;
}

办法二：双指针

算法流程：

• 咱们应用两个指针l、r来帮忙抉择每一个单词
• 在每次循环时，先去除所有单词右侧空格，获取某个单词的最右下标r，再获取单词的最左下标l
• 而后把单词s.substr(l + 1, r – l)退出ret，别忘了加空格哦
• 最初要把多余的空格去除ret.pop_back()

string reverseWords(string s) {
    int l = 0, r = s.size() - 1;
    string ret;
    while (r >= 0) {
        while (r >= 0 && s[r] == ' ') {
            --r;    //革除单词右侧空格
        }
        if (r < 0) {
            break;
        }
        for (l = r; l >=0 && s[l] != ' '; --l);    //取单词
        ret += (s.substr(l + 1, r - l) + " ");
        r = l;
    }
    if (ret.size()) {
        ret.pop_back();  //去除最初一个空格
    }
    return ret;
}

办法三：API istringstream

//栈
string reverseWords(string s) {
    stack<string> stk;
    string res, str;
    istringstream ss(s);
    while (ss >> str) {    //入栈
        stk.push(str),stk.push(" ");
    }
    if (!stk.empty()) {
        stk.pop();
    }
    while (!stk.empty()) {//出栈
        res += stk.top(), stk.pop();
    }
    return res;
}
//非栈
string reverseWords(string s) {
    istringstream ss(s);
    string res, str;
    while ( ss >> str) {
        res = str + ' ' + res;
    }
    return res.substr(0, res.size() - 1);
}