当前位置:职场发展->面试->C++面试题-算法题1:删除字符串中所有空格字符

原创版权标志C++面试题-算法题1:删除字符串中所有空格字符

作者:codexia  发表时间:2016/2/25 0:09:04  阅读:
[摘要] 题目: 给定一个字符串,字符串的内容不限,请用一个算法将字符串中的所有空格删除。 要求: 1.不能使用复杂的数据类型,不能使用额外的数组、结构体、链表等。 2.时间复杂度为O(n)。
文章来源:C++技术网原创文章版权所有,会员文章禁止转载。非会员文章转载做好本文超链接即表示授权转载。通过文章下面的分享按钮可以自由分享所有文章。
C++面试题-算法题1:删除字符串中所有空格字符

题目:
给定一个字符串,字符串的内容不限,请用一个算法将字符串中的所有空格删除。
要求:
1.不能使用复杂的数据类型,不能使用额外的数组、结构体、链表等。
2.时间复杂度为O(n)。

题目解题思路:

    我们使用两个整型变量,一个用于记录当前遍历字符数组的元素的位置,一个用于记录下一个字符将放在哪一个位置。
    因为删除了空格字符后,后面的字符得向前移动。所以才需要记录位置。对于遍历位置的记录,这个都好理解,因为数组要从头到尾遍历来判断每一个元素是否为空格字符。
    第二个记录位置的变量,则是理解的关键。因为这个变量的处理,也就提现了你的思维方式。如果你将这个变量用于记录空格字符出现的位置,那么恭喜你,你已经走上了不归路。字符串中的空格有多少,谁也不知道。我们又不能使用数组来处理(题目的要求),没法借助数组来处理空格问题。如果你的思维陷入在这里,将永远找不到答案。
    然而,如果你将第二个记录位置的变量,用于记录下一个非空格字符存放的位置,那么分分钟搞定这个算法题。我们只要依次将非空字符按照顺序防止一遍即可,并且如果前面有空格字符,自然被后面的非空格字符替换,这也正是题目要求删除空格字符的目的。
    这个题目,只要你是从非空格字符重新排列位置的角度来想的,非常简单。千万不要被常用的数组方式处理,不要被这些思路给带成思维定势了。这个题目就是明显的两种处理方法,要么是从空格字符下手,要么就是从非空格字符下手。如果你不幸先从空格字符下手了,那么你在搞不定的时候,要尽快想着换一个角度来想问题,换到使用非空格字符来处理。因为这些算法题,难度本身不会很大,就算难度很大的算法题,换一个思路通常对于解题很有帮助。

下面是完整的算法题代码:

#include<stdio.h>
void main()
{
 char str[50]="this is a website: www.cjjjs.cn!";
 int next=0;
 for (int i=0;str[i]!='\0';i++)
 {
 if (str[i]!=' ')
 {
 str[next++]=str[i];
 }
 }
 str[next]=0;
 printf(str);
}
文章来源:C++技术网原创文章版权所有,会员文章禁止转载。非会员文章转载做好本文超链接即表示授权转载。通过文章下面的分享按钮可以自由分享所有文章。


返回顶部

在线提问
问题标题:
问题描述:(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)

C++技术网群幕群聊

弹幕