题目地址：https://leetcode-cn.com/problems/reverse-words-in-a-string-ii/
题目描述
Given an input string , reverse the string word by word.
Example:
Input: ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
Note:
1、 Awordisdefinedasasequenceofnon-spacecharacters.；
2、 Theinputstringdoesnotcontainleadingortrailingspaces.；
3、 Thewordsarealwaysseparatedbyasinglespace.；
Follow up: Could you do it in-place without allocating extra space?
题目大意
给定一个字符串，逐个翻转字符串中的每个单词。
解题方法
每个单词单独翻转+总的翻转
没记错的话是剑指offer上的题目，做法是用到了一个公式c b a = (aT bT cT)T，如果知道这个公式应该很好办了。
为什么需要公式而不是直接找到首尾单词互换位置呢？很容易看出每个单词的长度是不同的，互换位置可能会覆盖其他的单词。
C++代码如下：
class Solution {
public:
void reverseWords(vector<char>& s) {
if (s.empty()) return;
int pre = 0;
int cur = 0;
while (cur <= s.size()) {
if (cur == s.size() || s[cur] == ' ') {
reverse(s, pre, cur - 1);
pre = cur + 1;
}
cur ++;
}
reverse(s, 0, s.size() - 1);
}
// reverse [start, end]
void reverse(vector<char>& s, int start, int end) {
for (int i = 0; i <= (end - start) / 2; ++i) {
swap(s[start + i], s[end - i]);
}
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发