58-I. 翻转单词顺序
1. 描述
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. “，则输出"student. a am I”。
2. 例子
示例 1:
输入: “the sky is blue”
输出: “blue is sky the”
示例 2:
输入: " hello world! "
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
示例 3:
输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
3. 限制
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
- 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
4. 题解
n = i_nums.size()
时间复杂度: O(n)
空间复杂度: O(1)，计算过程本身不额外占用空间
class Solution
{
private:
void trim(string &m_sentence)
{
if(m_sentence.empty()) return;
m_sentence.erase(0, m_sentence.find_first_not_of(" "));
m_sentence.erase(m_sentence.find_last_not_of(" ") + 1);
}
public:
// string reverseWords(string s)
string reverseWords(string &m_sentence)
{
// remove blanks at both sides
trim(m_sentence);
// remove redundant blanks between the string
int right = m_sentence.size() - 1;
for(int left = m_sentence.size() - 1; left >= 0; )
{
m_sentence[right] = m_sentence[left];
right--;
left--;
while(left >= 0 && m_sentence[left + 1] == ' ' && m_sentence[left] == ' ') left--;
}
m_sentence.erase(0, right + 1);
// first reverse
reverse(m_sentence.begin(), m_sentence.end());
m_sentence.push_back(' '); // guard
// second reverse
for(int left = 0, right = 0; right < m_sentence.size(); left = right)
{
while(m_sentence[right] != ' ') right++;
reverse(m_sentence.begin() + left, m_sentence.begin() + right);
while(right < m_sentence.size() && m_sentence[right] == ' ') right++;
}
m_sentence.pop_back();
return m_sentence;
}
};