算法-删除字符串中的公共字符

题目: 输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。例如,输入“They are students.”和”aeiou”,则删除之后的第一个字符串变成”Thy r stdnts.”

解题思路: 好未来那这道题做过笔试题目,首先最简单的思路就是两层循环遍历,下面将“They are students.”称为字符串1,将“aeiou”称为字符串2。每遍历到字符串2中的一个字符,就在字符串1中找到相同的字符,找到之后删除它,并将字符串1后面的字符整体向前移动1位。所以这个过程的时间复杂度是O(n^3),下面我们就可以考虑如何优化它了:

1.如何解决顺序存储结构中删除后整体移动的问题? 假设当前遍历到字符串2中的“a”,现在遍历字符串1,要求是是“a”的话就删除,那么这个要求换一个思路就是不是“a”就保留,在不申请新的空间的情况下,我们只需要把要保留的字符覆盖字符串中1原来的字符,要删除的字符不做覆盖,此时就需要有两个指针,一个在控制整体的遍历过程,一个记录要插入的位置:

可以看到,在遍历的过程中,如果没有出现要删除的字符的话,p1和p2一直在同步走(同步走的过程也是要覆盖的过程,一直在用p1的指向字符覆盖p2,只是他们指向相同,覆盖也就没有意义了),而出现了要删除的字符,p2会停下来,指示p1指向的字符要覆盖的位置,这样的话,我们就能避免每一次删除后的整体平移,这样的话时间复杂度还有O(n^2)。

2.如何避免两层遍历的嵌套? O(n^2)的时间复杂度是由遍历两个字符串产生的,能否应用一些方法避免循环嵌套的问题,引入hash表。 两个遍历嵌套的过程无非是为了找到字符串2中的字符在字符串1中是否出现,那么如果我们对字符串1建立hash表,在遍历字符串2时就可以根据hash索引直接找到要删除的字符,这样的话时间复杂度就可以降到O(n),下面考虑字符串2中出现重复字符的情况,无所谓啊,反正都是要删了的。 所以我们就能对字符串2建立一个hash表了,hash函数选择:(int)arr2[n]。在字符串2中出现的字符,在hash表中的值为1,未出现的字符表值为0。 hash表范围的选取: a :97 A :65 z :122 Z :90 标点符号还在字母之前,所以hash范围选成256就足够了。 所以总的来说,我们用一个O(256)的空间复杂度,将时间复杂度从O(n^2)将为O(n),所以如果n很大的话,这个替换是值得的。

代码实现:

#include "iostream"    

using namespace std;
void  DeleteChar(char arr1[],char arr2[]);
int main()
{   
  char str1[] = "They are students.";
  char str2[] = "aeiou";
  cout<<str1<<endl;
  DeleteChar(str1,str2);
  cout<<str1<<endl;
  getchar();
  return 0;
}
void  DeleteChar(char *arr1,char *arr2)
{
    if(arr1 == NULL && arr2 == NULL)
        return;
    //创建hash表
    int hash_table[256] = { 0 };
    char *p1 = arr1;
    char *p2 = arr2;
    int index =0;
    //遍历删除串
    while(*p2 != '\0')
    {
        hash_table[(int)*p2] = 1;
        p2++;
    }
    //遍历待删除串
    while (*p1 != '\0')
    {
        //该字符不需要删除
        if( 0 == hash_table[(int)*p1] )
        {
            arr1[index]= *p1;
            index++;
        }
        p1++;
    }
    arr1[index]='\0';
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

python:函数的高级特性

1873
来自专栏我的博客

sizeof用法

sizeof()功能:计算数据空间的字节数 1.与strlen()比较 strlen()计算字符数组的字符数,以”\0″为结束判断,不计算为’\...

2774
来自专栏python3

python3--列表推导式,生成器表达式,内置函数

3,python不但使用迭代器协议,让for循环变得更加通用,大部分内置函数,也是使用迭代器协议访问对象的,例如sum函数是python的内置函数,该函数使用迭...

2700
来自专栏书山有路勤为径

1.C与C++

使用c++中的标准库类型vector可以很轻松的完成任务。 不需要管理内存分配,对不同的类型都可以处理

1144
来自专栏GIS讲堂

postgis常用函数介绍(二)

通过函数st_isempty(geom)可以判断geometry是否为空,返回是布尔型的true或者false,具体使用如下:

1223
来自专栏数据小魔方

左手用R右手Python系列之——迭代器与迭代对象

接触过Python的小伙伴儿肯定都知道,Python中关于迭代器和可迭代对象运用的很广泛。迭代器可以以一种非常友好的方式使用在循环中,不仅节省内存,还能优化代码...

3708
来自专栏编程

Go语言中new和make的区别

Go语言中new和make是内建的两个函数,主要用来创建分配类型内存。在我们定义生成变量的时候,可能会觉得有点迷惑,其实他们的规则很简单,下面我们就通过一些示例...

1907
来自专栏Phoenix的Android之旅

你不知道的HashMap

面试中经常会问到常用数据结构,比如HashMap。 相信你平时几乎每天都会用到HashMap,但是你知道它是的实现原理是怎样的吗? 这里先提几个问题:HashM...

853
来自专栏我爱编程

Day6函数式编程2/3

返回函数 函数作为返回值 高阶函数除了可以接受函数作为参数外,还可以把函数作为结果值返回。 实现一个可变参数的求和。 def lazy_sum(*args):...

3486
来自专栏我的博客

选择排序

分类: 选择排序(选择排序,堆排序,平滑排序,笛卡尔树排序,锦标赛排序,圈排序) 思想: 1、从左至右遍历,找到最小(大)的元素,然后与第一个元素交换。 2、从...

3228

扫码关注云+社区