公众号&＃xff1a;爱写bug&＃xff08;ID&＃xff1a;icodebugs&＃xff09;
翻转字符串里的单词
Given an input string, reverse the string word by word.
示例 1&＃xff1a;
输入: "the sky is blue"
输出: "blue is sky the"
示例 2&＃xff1a;
输入: " hello world! "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格&＃xff0c;但是反转后的字符不能包括。
示例 3&＃xff1a;
输入: "a good example"
输出: "example good a"
解释: 如果两个单词间有多余的空格&＃xff0c;将反转后单词间的空格减少到只含一个。
说明&＃xff1a;
- 无空格字符构成一个单词。
- 输入字符串可以在前面或者后面包含多余的空格&＃xff0c;但是反转后的字符不能包括。
- 如果两个单词间有多余的空格&＃xff0c;将反转后单词间的空格减少到只含一个。
进阶&＃xff1a;
请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。
Note:
- A word is defined as a sequence of non-space characters.
- Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
- You need to reduce multiple spaces between two words to a single space in the reversed string.
Follow up:
For C programmers, try to solve it in-place in O(1) extra space.
解题思路&＃xff1a;
Java 字符串不支持运算符重载&＃xff0c;无法用原地解法。 我们将字符串转为字符型数组并用两个指针来解这道题。指针 i 作为原字符串转为字符数组的索引&＃xff0c;从右向左移。指针 j 作为新字符数组索引&＃xff0c;从左向右赋值得到原数组 count 长度的字符。count记录遇到的字母数量&＃xff0c;每次遇到 空格 字符&＃xff0c;新数组得到从该空格字符 向右 count 个字符并刷新count 计数。
Java&＃xff1a;
class Solution {public String reverseWords(String s) {if (s.length()&＃61;&＃61;0)return s;//如果为空直接返回char strs[]&＃61;s.toCharArray(),ans[]&＃61;new char[s.length()];//字符串转为char字符数组int count&＃61;0,j&＃61;0;//全局变量j记录新数组索引for(int i&＃61;s.length()-1;i>&＃61;0;i--){指针i从右向左遍历strs字符if(strs[i]&＃61;&＃61;&＃39; &＃39;){//判断是否为空格字符int k&＃61;i&＃43;1;if(count>0){while (--count>&＃61;0){//从字符i向右count个字符赋给新数组ansans[j&＃43;&＃43;]&＃61;strs[k&＃43;&＃43;];}ans[j&＃43;&＃43;]&＃61;&＃39; &＃39;;count&＃61;0;//count初始化为0}}else if(i&＃61;&＃61;0){for(;i<&＃61;count;i&＃43;&＃43;)ans[j&＃43;&＃43;]&＃61;strs[i];//左移到第一个字符时证明不是以空格开头&＃xff0c;则从0获取count&＃43;1个个字符赋给ansj&＃43;&＃61;1;break;}else {count&＃43;&＃43;;//如果是字母&＃xff0c;则count累加1}}if(j<1)return "";//如果j依然是0&＃xff0c;则原字符串全为空格&＃xff0c;返回空字符串String string&＃61;String.valueOf(ans,0,j-1);//char数组转为字符串返回return string;}
}
为了考虑性能&＃xff0c;转成了多个判断&＃xff0c;所以有些繁琐。最终运行&＃xff1a;Your runtime beats 99.91 % of java submissions
Python3&＃xff1a;
python完全可以实现Java的思路&＃xff0c;不再复现。这里利用函数投机取巧&＃xff1a;
split() &＃xff0c;它可以把传入字符串剔除空格后返回 所有单词的数组
join() &＃xff0c;它可以指定一个数组以特定字符为间隔&＃xff0c;拼接成一个字符串
加上 [::-1] 反转数组&＃xff0c;一行代码既可实现该题目要求
&＃39; abc def &＃39; 原字符串
[&＃39;abc&＃39; , &＃39;def&＃39;] 剔除空格返回String型单词数组
[&＃39;def&＃39; , &＃39;abc&＃39;] 切片反转数组
&＃39;def abc&＃39; 拼接成字符串
class Solution:def reverseWords(self, s: str) -> str:return " ".join(s.split()[::-1]) # 剔除所有空格字符返回数组并反转&＃xff0c;以空格为间隔把数组拼成字符串
京公网安备 11010802041100号