什么网站做玩具的比较多,网站建设的付款方式,企业网络营销策划书模板,wordpress版小程序目录 151、反转字符串中的单词题目描述思路代码本题反思 151、反转字符串中的单词
题目描述
给你一个字符串 s #xff0c;请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个… 目录 151、反转字符串中的单词题目描述思路代码本题反思 151、反转字符串中的单词
题目描述
给你一个字符串 s 请你反转字符串中单词的顺序。
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。
注意输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中单词间应当仅用单个空格分隔且不包含任何额外的空格。
要求空间复杂度为O(1)
思路 去除多余空格:收尾无空格单词之间只有一个空格 定义快慢指针快指针负责寻找正确的元素慢指针负责从头开始给字符串赋值。 反转字符串反转单个单词 代码
class Solution {
public://原地反转字符串void reverse(string s, int start, int end) {for (int i start, j end; i j; i,j--) {swap(s[i], s[j]);//交换操作}}//去除多余空格void removeExtraSpaces(string s) {int slowIndex 0, fastIndex 0; // 定义快指针慢指针// 去掉字符串前面的空格while (s.size() 0 fastIndex s.size() s[fastIndex] ) {fastIndex;}for (; fastIndex s.size(); fastIndex) {// 去掉字符串中间部分的冗余空格if (fastIndex - 1 0 s[fastIndex] s[fastIndex - 1] s[fastIndex]) {continue;} else {s[slowIndex] s[fastIndex];}}if (slowIndex - 1 0 s[slowIndex - 1] ) { // 去掉字符串末尾的空格s.resize(slowIndex - 1);} else {s.resize(slowIndex); // 重新设置字符串大小}
}//反转字符串中的单词string reverseWords(string s) {removeExtraSpaces(s);//去除多余空格reverse(s, 0, s.size() - 1);//原地反转所有字符//开始逐个反转单词int start 0;//指向每一个单词的开头for (int i 0; i s.size(); i) {if (i s.size() || s[i] ) {//到达空格或字符串尾部说明一个单词结束进行反转reverse(s, start, i - 1);start i 1;//把start指向下一个单词的开头}}return s;}
};优化【去除多余空格函数】之后的代码
class Solution {
public://原地反转字符串void reverse(string s, int start, int end) {for (int i start, j end; i j; i,j--) {swap(s[i], s[j]);//交换操作}}//去除空格void removeExtraSpaces(string s) {int slow 0;//慢指针辅助赋值操作for (int i 0; i s.size();i) {if (s[i] ! ) {//如果目前遍历到的字符不是空格就进行处理if (slow ! 0) s[slow] ;//给每个单词之间添加空格while (i s.size() s[i] ! ) {s[slow] s[i];}}}s.resize(slow);//slow的大小就是删除多余空格后字符串的大小
}//反转字符串中的单词string reverseWords(string s) {removeExtraSpaces(s);//去除多余空格reverse(s, 0, s.size() - 1);//原地反转所有字符//开始逐个反转单词int start 0;//指向每一个单词的开头for (int i 0; i s.size(); i) {if (i s.size() || s[i] ) {//到达空格或字符串尾部说明一个单词结束进行反转reverse(s, start, i - 1);start i 1;//把start指向下一个单词的开头}}return s;}
};时间复杂度O(n) 空间复杂度O(1)原地修改字符串。 本题反思
对于字符串的操作类似于数组也是利用双指针查找正确元素然后进行覆盖操作达到修改字符串的目的。寻找正确字符的过程就是去除多余空格的过程。比起整体反转字符串加入了在整体字符串中反转其中的单词这需要额外添加条件判断。
