89°

算法-在字符串中删除特定的字符

题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。

例如, 输入”i want to be a excellent programmers”和”aem”,则删除之后的第一个字符串变成”i wnt to b  xcllnt progrrs"

分析:要编程完成这道题要求的功能可能并不难。毕竟,这道题的基本思路就是在第一 个字符串中拿到一个字符,在第二个字符串中查找一下,看它是不是在第二个字符串中。如果在的话,就从第一个字符串中删除。但如何能够把效率优化到让人 满意的程度,却也不是一件容易的事情。也就是说,如何在第一个字符串中删除 一个字符,以及如何在第二字符串中查找一个字符,都是需要一些小技巧的。

首先我们考虑如何在字符串中删除一个字符。由于字符串的内存分配方式是连续 分配的。我们从字符串当中删除一个字符,需要把后面所有的字符往前移动一个 字节的位置。但如果每次删除都需要移动字符串后面的字符的话,对于一个长度 为 n 的字符串而言,删除一个字符的时间复杂度为 O(n)。而对于本题而言,有可 能要删除的字符的个数是 n,因此该方法就删除而言的时间复杂度为 O(n2)。

事实上,我们并不需要在每次删除一个字符的时候都去移动后面所有的字符。我 们可以设想,当一个字符需要被删除的时候,我们把它所占的位置让它后面的字 符来填补,也就相当于这个字符被删除了。在具体实现中,我们可以定义两个指 针(psou和 pkey),初始的时候都指向第一字符的起始位置。当 psou 指向的字符是需要删除的字符,则 psou 直接跳过,指向下一个字符。如果 psou 指向的字符是不需要删除的字符,那么把 psou 指向的字符赋值给 pkey 指向的字符, 并且 psou 和 pkey同时向后移动指向下一个字符。这样,前面被psou 跳过的字符相当于被删除了。用这种方法,整个删除在 O(n)时间内就可以完成。

接下来我们考虑如何在一个字符串中查找一个字符。当然,最简单的办法就是从 头到尾扫描整个字符串。显然,这种方法需要一个循环,对于一个长度为 n 的字 符串,时间复杂度是 O(n)。 由于字符的总数是有限的。对于八位的 char 型字符而言,总共只有 28=256 个字 符。我们可以新建一个大小为 256 的数组,把所有元素都初始化为 0。然后对于 字符串中每一个字符,把它的 ASCII 码映射成索引,把数组中该索引对应的元素 设为1。这个时候,要查找一个字符就变得很快了:根据这个字符的 ASCII 码, 在数组中对应的下标找到该元素,如果为 0,表示字符串中没有该字符,否则字符串中包含该字符。此时,查找一个字符的时间复杂度是 O(1)。其实,这个数组 就是一个 hash 表。

基于上述分析,我们可以写出如下代码:

 1 #define _CRT_SECURE_NO_WARNINGS
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 
 5 char *  deleteStr(char *source, char *key)  6 {  7 
 8     int hashTable[256];  9     memset(hashTable, 0, sizeof(hashTable)); 10     char *point_sou, *point_key; 11     point_sou = key; 12     while (*point_sou != '\0')//待删除字符在哈希表里赋值为1
13  { 14         hashTable[*point_sou] = 1; 15         point_sou++; 16  } 17     point_sou = source; 18     point_key = source; 19     while (*point_sou != '\0') 20  { 21         if (!hashTable[*point_sou])//哈希表不为1时不是待删除字符,将sou指针指向的字符赋给key指针指向的字符,将两指针同时向后移
22  { 23             *point_key = *point_sou; 24             point_key++; 25  } 26         point_sou++;  //是待删除字符,sou指针继续向前移,key指针停留在待删除字符前 27     //下一次循环判断是不是待删除字符,不是,将sou指针指向的字符赋给key指针指向的字符,souce也就相当于删除了前面的字符
28 
29  } 30     *point_key = '\0'; 31     return source; 32 
33 } 34 
35 int main() 36 { 37     char p[] = "i want to be a excellent programmers"; 38     char key[] = "aem"; 39     printf("%s\n", deleteStr(p, key)); 40 }

 

原文链接:https://www.cnblogs.com/cyyz-le/p/11181975.html

全部评论: 0

    我有话说: