每日一练（31）（翻转单词顺序）每日一练（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 res; //存放字符串的数组 for (char ch : s) { //遍历字符句子 if (ch == ' ') {//遇到空格 if (!temp.empty()) {//有前后置空格，需要判断临时字符串非空，反之可以去掉此判断 res.push_back(temp); temp.clear(); //清空临时字符串 } } else { temp += ch; } }

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

s += " "; //这里在最后一个字符位置加上空格，这样最后一个字符串就不会遗漏 string temp = ""; //临时字符串 vector 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 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; }

方法二：双指针
【每日一练（31）（翻转单词顺序）】算法流程：

我们使用两个指针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 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); }