【今日/总数】文章:0/2773 用户:0/10774 书籍:0/200
回顾2016,喜迎2017,以“回顾我与C++技术网的2016,展望C++技术网的2017”为主题,发表文章,将有机会赢得2个月的会员或现金红包。

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

作者:codexia  发表时间:2016/2/25 0:09:04  阅读:1709
[摘要]题目: 给定一个字符串,字符串的内容不限,请用一个算法将字符串中的所有空格删除。 要求: 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++技术网 原创文章版权所有,未经授权,禁止转载。



返回顶部

关于我们 QQ群 广告服务 增值服务 捐款资助 版权声明 RSS订阅 站点地图 百度网站地图 意见反馈
鄂ICP备14001349号-2, Copyright © 2014-2017, CJJJS.COM/CJJJS.CN, All Rights Reserved

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