丰收在望 发表于 2024-7-23 17:55:40

LeetCode151. 反转字符串中的单词


拿到这道题,我们想一下,我们将整个字符串都反转过来,那么单词的顺序指定是倒序了,只不过单词本身也倒序了,那么再把单词反转一下,单词不就正过来了。
所以解题思路如下:
移除多余空格
将整个字符串反转
将每个单词反转
举个例子,源字符串为:"the sky is blue "
移除多余空格 : "the sky is blue"
字符串反转:"eulb si yks eht"
单词反转:"blue is sky the"
这样我们就完成了翻转字符串里的单词。
那么现在的思路就非常清晰明了了,先将整个字符串进行反转,再去除多余的空格,最后将每个单词进行反转
以下我对最难的部分---移除多余的空格进行讲解:
我们可以采用双指针的思想进行移除多余空格的操作,快指针用来遍历我们的数组,慢指针用于更新我们需要保留的元素的索引
不过有一个逻辑需要特别处理一下,就是要在每个单词之间加上空格(首单词除外)——判断逻辑可以表示为
if(slow!=0) s=' ';
这样就可以做到在每个单词之间加上空格,并且去除首字母前面的空格了。
具体函数实现的代码如下:

        //去除字符串中多余的空格
        void removeExtraSpaces(string& s)
        {
                int fast = 0, slow = 0;
                for (fast = 0; fast < s.size(); fast++) {
                        //快指针指向我们要保留的字符
                        if (s != ' ') {
                                //将每个单词之间加上空格,首单词除外
                                if (slow != 0) s = ' ';
                                //将单词中间的空格去除
                                while (fast < s.size() && s != ' ') {
                                        s = s;
                                }
                        }
                }
                s.resize(slow);
        }其余两个步骤的代码比较简单,我在这里就不过多赘述了
具体可以编译运行的代码如下:

class Solution {public:        //反转字符串中的某段        void reverse(string& s, int start, int end)        {                for (int i = start, j = end; i < j; i++, j--) {                        swap(s, s);                }        }        //去除字符串中多余的空格
        void removeExtraSpaces(string& s)
        {
                int fast = 0, slow = 0;
                for (fast = 0; fast < s.size(); fast++) {
                        //快指针指向我们要保留的字符
                        if (s != ' ') {
                                //将每个单词之间加上空格,首单词除外
                                if (slow != 0) s = ' ';
                                //将单词中间的空格去除
                                while (fast < s.size() && s != ' ') {
                                        s = s;
                                }
                        }
                }
                s.resize(slow);
        }        string reverseWords(string& s)        {                //移除字符串中多余的空格                removeExtraSpaces(s);                //反转这个字符串                reverse(s, 0, s.size() - 1);                //反转这个字符串中的每一个单词                int start = 0;                for (int i = 0; i
页: [1]
查看完整版本: LeetCode151. 反转字符串中的单词