每日一题 - 翻转字符串里的单词

reverse-words-in-a-string



一、描述



151. 翻转字符串里的单词



给定一个字符串，逐个翻转字符串中的每个单词。



说明：



• 无空格字符构成一个单词。

• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

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



进阶：

请选用 C 语言的用户尝试使 ,意思是说原地反转。



输入: "  hello world!  "

输出: "world! hello"

解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"

输出: "example good a"

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



这个题目试着这里开始入手



算法五个重要的特征：



• 有输入，有输出（题目已经给了）



• 可行性（复杂问题转化成熟悉子问题）



• 有穷性（在算法描述体现）



• 确切性（在算法描述体现）



*

*



二、思路



• 问题转化：三步走，重点：是连续空间删除一个字符，如何避免整体copy



题目明明是要求的反转字符串单词问题， 要想保证反转后没有多余空格。

>

在反转前消除空格

最终转化成在同一个连续空间，移动copy字符串问题。

不同空间肯定没有问题，同一个空间呢？内存重叠呢？

解决了：数组特点 地址空间连续，删除一个元素，后面整体一定问题。



子问题：



1. 单词有空格，去掉多余空格。

2. 反转单词。

3. 反转步骤1和2之后的字符串。



• 算法描述：



第一步：如何删除多余空格？



因为数据结构是数组，只能靠移动，



• 这个有一个拦路虎是 字符串，多个单词 ,如何循环移动多次？（通过队列保存拆分后单词这个想法可以想到）

• 假设 这是这个单词位置 A |B |C |D

• 输出: "example good a"



第二步：反转一个单词



如何确定每个单词位置。 非空



第三步：反转一个句子



三、代码



• 放轻松，虽然是c++实现，拒绝奇技淫巧，通俗易懂。



class Solution {

public:

string reverseWords(string s) {

int index =0;

// 去除多余空格后，字符串s大小肯定会发生变化置.[0 index]表示反转新结束位。

//理想情况 eg1，大小没有发生变化

//遍历一次 start单词开始位置,end单词位置。

for (int start=0;start<s.size();start++)

{

if (s[start] ==' ')

{

continue;//

}

//01 多个空格变成一个空格,反转后必须单词开头 eg2

if (index >0)

{

s[index++]=' ';

}

//02 寻找单词开始位置，结束位置

int end =start;

while (end <s.size() && s[end] !=' ' )

{

s[index++]=s[end++];//c语言中的 memmove和memcpy区别。

}

//03 反转单词长度

int word=end-start;

reverse(s.begin()+index-word,s.begin()+index);

//这里反转移动之后新单词位置index，不是start 和end。

//reverse(s.begin()+start,s.begin()+end);

start =end;

}

//04 反转句子

s.resize(index);

reverse(s.begin(),s.end());

return s;

}

};



• bug1 ：如果有多余空格，单词不是原地反转，//reverse(s.begin()+start,s.begin()+end);





分享最实用的经验 ， 希望每一位来访的朋友都能有所收获！

如果有疑问请联系我，一起探讨，进步。