1.清除空格
编写一个程序,把字符串中的每个空格清除掉。例如输入“we are happy.”,则输出“wearehappy.”。
- 编程思路
由于字符串的内存分配方式是连续分配的。我们从字符串当中删除一个空格字符时,需要把后面所有的字符往前移动一个字节的位置。但如果每次删除都需要移动字符串后面的字符的话,对于一个长度为n 的字符串而言,删除一个空格字符的时间复杂度为o(n) 。而对于本题而言,有可能要删除的空格字符的个数是n ,因此该方法就删除而言的时间复杂度为o(n2) 。
事实上,我们并不需要在每次删除一个空格的时候都去移动后面所有的字符。我们可以设想,当一个空格需要被删除的时候,我们把它所占的位置让它后面的字符来填补,也就相当于这个空格被删除了。具体方法为:
(1)定义两个指针p1和p2,p2用于遍历原始字符串,p1用于指向结果字符串中当前赋予的非空格字符。初始状态都指向字符串首字符。
(2)如果p2指向的元素不为空格,那么将p2指向的内容赋值给p1,然后p1和p2指向下一个元素;如果p2指向的内容为空格,那么p2指向下一个元素,p1保持不动。
(3)直到p2指向字符串末尾的“