编译环境
本系列文章所提供的算法均在以下环境下编译通过。
【算法编译环境】Federa 8，linux 2.6.35.6-45.fc14.i686
【处理器】 Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz
【内存】 2025272 kB
前言
本篇文章和上一篇文章所采用思路同出一则，做为两篇来讲，是觉得如果文章太长需要翻页很多，显然不好。显然长篇大论会让人不仅仅视觉疲劳，也会让人很不耐烦。除非幽默风趣生动。才能让小伙伴们有耐心看下去。好了， 闲话不多说。书接上回，上文用到的方法大致可以总结为：“一次扫描，向左平移”。时间复杂度为O（N）。本次算法依然采用这种方法。当然本题还用到了 “字符串hash”，这种方法也在不少算法中取得了四两拨千斤的效果，小伙伴们要记住这些名词。这让我突然想到了小时候做数学题时的小技巧。这些大概就是属于小技巧，我们可以称之为“算法小技巧”。
本系列文章均系笔者所写,难免有一些错误或者纰漏，如果小伙伴们有好的建议或者更好的算法，请不吝赐教。
正文
【题目】
输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
【例子】
输入”They are students.” 和”aeiou”则删除之后第一个字符串变成 Ｔhy r stdnts。
【分析】
这道题来之微软，也不是很难。这说明牛X的公司也未必全是难题。所以小伙伴们不要被公司给吓倒。
就本题来讲，大致思路在上面也提到，就是对字符串1进行扫描，然后判断当前字符是否在子字符串中出现，如果出现，则忽略不计，继续下一位，反之则复制到i指针处（i指针是指向输出的位置，初始化为0）。
那这里有一个问题了，判断一个字符在字符串2中是否出现，如果用平时的方法，需要O（N）复杂度。显然不行。那什么方法是O（1）呢？当然只有hash算法了。“字符串hash”，我们可以把这个当作专有名词记住，让你在任何时候都知道用它。，我们对字符串2进行hash初始化，然后对字符串1就可以直接判断了。这里举一个例子吧。（虽然很简单，但也有可能我表达不清晰，让大家有所误解。）ASCII编码至于256个，每个char类型其实都是一个整数，在C语言里面我们可以定义int hash_table[256]。比如A的值是65，如果A存在则我们只要设置hash_table[(int)'A'] = 1即可。
上面一堆废话，其实大致可以总结如下：
用i指针来控制输出，j指针来处理子字符串出现的字符。这么说简单明了吧。
算法的文字描述如下：
第一步：初始化hash表，并将子字符串中出现的字符对应的hash表位置设置1；
第二步：用i指针控制输出开始为0，j指针从0处开始扫描；
第三步：当j遇见第一个子字符串中未的字符，赋给i处.i指向下一位；反之，跳过;
第四步：循环第三步，直到字符串末尾停止。。
【代码】
#include <iostream> #include <cstring> char * string_del_characters( char * const src, const char * const dest ) { int destLen = strlen( dest ); int hash_table[256] = { 0 }; char * p = src; int index = 0; for( int i = 0; i < destLen; i++ ) { hash_table[ (int)dest[i] ] = 1; } while( *p != ' ' ) { if( 0 == hash_table[(int)*p] ) { src[index++] = *p; } p++; } src[index] = ' '; return src; } int main( int argc, char ** argv ) { char src[] = "They are students."; char dest[] = "aeiou"; char * pResult = string_del_characters( src, dest ); std::cout << pResult << std::endl; }
【结论】
作者
出处：http://www.cnblogs.com/gina
本文版权归作者所有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。