共计 2336 个字符，预计需要花费 6 分钟才能阅读完成。
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);
}
