leetcode-151-翻转字符串里的单词

题目描述:

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

示例:  

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

说明:

  • 无空格字符构成一个单词。
  • 输入字符串可以在前面或者后面包含多余的空格,但是反转后的字符不能包括。
  • 如果两个单词间有多余的空格,将反转后单词间的空格减少到只含一个。

进阶: 请选用C语言的用户尝试使用 O(1) 空间复杂度的原地解法。

要完成的函数:

void reverseWords(string &s) 

说明:

1、这道题给定一个字符串s,相当于一个英文句子,要求把这个句子中的单词反转一下,后面的要放在前面,前面放在后面。

这个句子中可能会有多余的空格,可能会出现在第一个字符前面,可能出现在单词之间,可能出现在最后一个字符后面。

你要将多余的空格去掉,最前面和最后面不能有空格,单词之间的空格只能有一个。

c或c++语言用户使用O(1)空间复杂度的原地解法,在字符串中修改,函数类型是void,不用返回。

2、这道题如果允许多定义一个新字符串(长度与给定字符串相同),那么从给定字符串的后面读起,读出的字符从新的字符串的前面开始写起。

在写的过程中,调整新字符串的空格,使之符合要求,最后调用resize函数修改新字符串的长度,这道题也就解决了。

但现在要求原地解法,那么只能逐个交换了,后面跟前面交换,这样子换完之后,单词内部顺序也是反过来的,那再在单词内部交换一下,也就ok了。

至于多余的空格问题,可以在交换之前,先解决掉这个问题,把后面的字符往前面移。

笔者的代码思路如下,举个例子,字符串是   "(两个空格)the(三个空格)sky(两个空格)is(一个空格)blue(两个空格)":

1、先反转整个字符串,变成(两个空格)eulb(一个空格)si(两个空格)yks(三个空格)eht(两个空格)。

2、把后面的字符往前挪,去掉多余的空格,变成eulb(一个空格)si(一个空格)yks(一个空格)eht

3、在单词内部进行反转,变成blue(一个空格)is(一个空格)sky(一个空格)the。

所以具体代码如下:(附详解)

    void reverseWords(string &s) 
    {
        reverse(s.begin(),s.end());//先进行整个字符串的反转
        int i=0,j=0,start=0,t;
        while(i<s.size())//把字符往前挪,去掉多余的空格
        {
            while(i<s.size())//找到第一个非空格字符
            {
                if(s[i]!=' ')
                    break;
                i++;
            }
            if(i==s.size())break;//如果找不到非空格字符,此时已经i==s.size(),所以直接结束这一部分的任务
            j=i+1;
            while(j<=s.size())//找到i后面的第一个空格字符,位置记为j
            {
                if(s[j]==' '||s[j]=='\0')
                    break;
                j++;
            }
            while(i<j)//把i和j之间的字符往前挪,第一个就搬动到start这个位置,第二个搬动到start+1这个位置……
            {
                s[start]=s[i];
                start++;
                i++;
            }
            s[start]=' ';//搬完一个单词之后,start现在这个位置变成空格字符
            start++;//start到空格的下一位,作为新的单词的起点
            i++;//i退出循环时,i==j,现在i++,变成空格的下一位,继续找下一个单词的起点
        }
        if(start==0)//边界条件,如果结束了上述任务之后,start还是为0,说明根本就没有非空格字符,那么s变成空字符串
			s=s.substr(0,0);
		else
		{
			s=s.substr(0,start-1);//去掉字符串后面多余的长度
	        i=0,j=1;
	        while(i<s.size())//把每一个单词反转过来
	        {
	        	while(j<=s.size())//找到空格位置,记为j
		        {
		        	if(s[j]==' '||s[j]=='\0')
		        		break;
		        	j++;
				}
				t=j+1;//记下来,作为下一个单词的起始位置
				j--;
				while(i<j)//单词内部反转
				{
					swap(s[i],s[j]);
					i++;
					j--;	
				}
				i=t,j=i+1;//更新i和j的位置
			}   
		}

上述代码实测4ms,beats 98.93% of cpp submissions。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏十月梦想

运算符

=就是简单给变量的赋值,+(-,*,/,%,.)=等同于左边加上(减去,乘上,除以,求余数,字符连接)右边赋值给昨天

703
来自专栏我和PYTHON有个约会

25. 企业级开发基础6:面向对象特征(继承)

继承是让我们抽象的对象之间存在一定的所属关系 在继承关系中,我们一定要明确会出现这样的一种关系~父类、子类,子类继承自父类,可以继承父类中的公开的属性和方法(...

731
来自专栏程序员八阿哥

年薪20万Python工程师进阶(4):一文读懂Python可迭代对象、迭代器和生成器

序列可以迭代的原因:iter 函数。解释器需要迭代对象 x 时,会自动调用 iter(x)。内置的 iter 函数有以下作用:

1083
来自专栏zingpLiu

Go语言的数组

在 Go 语言里,数组是一个长度固定的数据类型,用于存储一段具有相同的类型的元素的连续块。数组存储的类型可以是内置类型,如整型或者字符串,也可以是某种结构类型。

1254
来自专栏机器学习实践二三事

python基础----函数作为返回值

从一个例子讲起 高阶函数除了可以接受函数作为参数外,还可以把函数作为结果值返回。 还是考虑这个问题:对可变参数进行求和 看了上一讲的已经知道,可以使用’*’...

2725
来自专栏Golang语言社区

【Go 语言社区】Go语言运算符

运算符是一个符号,告诉编译器执行特定的数学或逻辑操作。 Go语言有丰富的内置运算符和运算符提供的以下几种类型: 算术运算符 关系运算符 逻辑运算符 位运算符 赋...

36316
来自专栏流媒体

C++多态

当类存在虚函数时,编译器会为该类维护一个表,这个表就是虚函数表(vtbl),里面存放了该类虚函数的函数指针。在构造类的时候增加一个虚表指针(vptr)指向对应的...

1163
来自专栏Python小屋

详解Python函数式编程之map、reduce、filter

map()、reduce()、filter()是Python中很常用的几个函数,也是Python支持函数式编程的重要体现。不过,在Python 3.x中,red...

3716
来自专栏Albert陈凯

如何在 Scala 中科学地操作 collection(一)集合类型与操作

在日常项目开发中,我们几乎都会用到Scala中的集合以及一些集合操作。由于 Scala 中的集合操作灵活多变,对于刚接触Scala的开发者,在选用何种集合以及使...

2625
来自专栏Golang语言社区

Python基本运算符

什么是操作符? 简单的回答可以使用表达式4 + 5等于9,在这里4和5被称为操作数,+被称为操符。 Python语言支持操作者有以下几种类型。 算术运算符 比较...

4667

扫码关注云+社区

领取腾讯云代金券