[LeetCode字符串#03]图解翻转字符串中的单词,以及对于for使用的说明

翻转字符串中的单词

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

输入: "the sky is blue"
输出: "blue is sky the"

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

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

思路

"the sky is blue" ---> "eulb si yks eht"

然后再逐个将单词转回来

但是题目所给的输入有可能是不规范的

这就有点难搞

1、将字符串转换为标准形式（去除多余的空格，仅保留单词间的必要空格）

3、将反转字符串中的单词反转回正常顺序

代码

去除空格函数

就根据思路来写

void deleteExtraSpaces(string& s{
    //定义慢指针
    int slow = 0;
    //遍历字符串
    for(int fast = 0; fast < s.size(; ++fast{//++i和i++仅在效率上不同        
        if(s[fast] != ' '{
            //如果当前字符（单词）不是第一个字符（单词），那么要在单词前面加空格
            if(slow != 0{
                s[slow] = ' ';
                slow++;
            }
            //此时找到了单词的开头，需要将其按字符逐个移动到slow所指的位置
            //循环条件中需要再判断当前fast是否指向空格，指到就停止移动
            //进入下一个for循环，fast指针从道歉位置后移一位
            while(fast < s.size( && s[fast] != ' '{
                s[slow] = s[fast];
                slow++;
                fast++;
            }
        }
    }
    //因为去除了多余的空格，所以需要重新计算一下数组的大小
    s.resize(slow;//此时slow即为标准化后字符串数组的长度       
}

上述代码的过程图示如下：

反转函数

和反转字符串里面用的一样，当然也可以用c++提供的

void reverse(string& s, int start, int end{//注意要输入字符串的引用！
    //在for中同时维护两个变量
    for(int i = start, j = end; i < j; i++, j--{
        swap(s[i], s[j];
    }
}

完整代码

在主函数里面使用这两个函数完成解题逻辑

class Solution {
public:
    void deleteExtraSpaces(string& s{
        //定义慢指针
        int slow = 0;
        //遍历字符串
        for(int fast = 0; fast < s.size(; ++fast{//++i和i++仅在效率上不同        
            if(s[fast] != ' '{
                //如果当前字符（单词）不是第一个字符（单词），那么要在单词前面加空格
                if(slow != 0{
                    s[slow] = ' ';
                    slow++;
                }
                //此时找到了单词的开头，需要将其按字符逐个移动到slow所指的位置
                //循环条件中需要再判断当前fast是否指向空格，指到就停止移动
                //进入下一个for循环，fast指针从道歉位置后移一位
                while(fast < s.size( && s[fast] != ' '{
                    s[slow] = s[fast];
                    slow++;
                    fast++;
                }
            }
        }
        //因为去除了多余的空格，所以需要重新计算一下数组的大小
        s.resize(slow;//此时slow即为标准化后字符串数组的长度       
	}
    
    void reverse(string& s, int start, int end{
        //在for中同时维护两个变量
        for(int i = start, j = end; i < j; i++, j--{
            swap(s[i], s[j];
        }
	}
    
    string reverseWords(string s {
		//1、将字符串转换为标准形式，去除空格
        deleteExtraSpaces(s;
        //2、字符串整体反转
        reverse(s, 0, s.size( - 1;//记得减1
        //3、恢复每个单词的正常顺序
        //依旧使用快慢指针
        int slow = 0;//start,fast即为end
        for(int fast = 0; fast <= s.size(; ++fast{
            if(fast == s.size( || s[fast] == ' '{//到达空格或者字符串结尾倒要反转，不然会漏翻
                reverse(s, slow, fast - 1;
                slow = fast + 1;//从下一个单词的头开始
            }
        }
        return s;
    }
};

正确的思考方式应该是想清楚思路之后，实现每个部分需要的函数，然后再一块搭起来

注意点

1、for循环的特性

循环变量

for(int i = 0; i < xxx; i++{
    
}

上述是一个典型的for循环结构

for(int i = 0; i < xxx; i++

循环变量 i 进行初始化（赋初值），以及在每次{ }内代码执行完毕后对循环变量执行循环条件（即i++）

{ }内发生了什么，for循环本身是不管的。

{ }内对循环变量 i进行了操作，也是允许的

for(int i = 0; i < xxx; i++{
    i = 5;
}//那么下轮循环，i 就从6开始，而不是1

在本题中，大量运用了该特性，例如：截取遍历过程中的单词

`++i`和`i++`

实际上，在for的日常使用中，使用++i还是i++在结果上是没有区别的

++i的执行效率会好一些，仅此而已

详见

2、TBD

编程笔记 » [LeetCode字符串#03]图解翻转字符串中的单词,以及对于for使用的说明