java编程删除相同字符,[剑指offer]删除在另一个字符串中出现的字符

剑指offer上的字符串相关题目。

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

这里主要要分析两个方面&＃xff1a;

1、如何判断那些字符是需要删除的字符。同很多字符串问题一样&＃xff0c;可以开辟一个哈希数组&＃xff0c;全部初始化为false&＃xff0c;将第二个字符串中字符对应的映射位置置为ture&＃xff0c;表示这些位置对应的字符在第一个字符串中需要删除。

2、关于删除字符的操作&＃xff0c;每次删除一个&＃xff0c;而后把后面的元素均左移一位&＃xff0c;由于要删除的字符可能有多个&＃xff0c;这种方法的时间复杂度为O(n*n)。我们这里有O(n)的删除方法&＃xff0c;我们可以设想&＃xff0c;当一个字符需要被删除的时候&＃xff0c;我们把它所占的位置让它后面的字符来填补&＃xff0c;也就相当于这个字符被删除了。在具体实现中&＃xff0c;我们可以定义两个指针(pFast和pSlow)&＃xff0c;初始的时候都指向第一字符的起始位置。当pFast指向的字符是需要删除的字符&＃xff0c;则pFast直接跳过&＃xff0c;指向下一个字符。如果pFast指向的字符是不需要删除的字符&＃xff0c;那么把pFast指向的字符赋值给pSlow指向的字符&＃xff0c;并且pFast和pStart同时向后移动指向下一个字符。这样&＃xff0c;前面被pFast跳过的字符相当于被删除了。用这种方法&＃xff0c;整个删除在O(n)时间内就可以完成。

前面也有篇删除重复字符的博文用到了该删除方法&＃xff0c;见这里&＃xff1a;http://blog.csdn.net/ns_code/article/details/21328151。

另外&＃xff0c;有一点需要注意&＃xff0c;char的范围在-128-127&＃xff0c;unsigned char的范围才是在0-255&＃xff0c;因此ASCII值在128-255之间的字符&＃xff0c;如果保存为了char型&＃xff0c;其转化为int值的范围是在-128--1之间&＃xff0c;这点在下面的代码中有体现。

根据以上思路写出的代码如下&＃xff1a;

#include#include#define MAX 256

void DeleteChars(char *str1,char *str2)

{

if(str1&＃61;&＃61;NULL || str2&＃61;&＃61;NULL)

return;

bool hashtable[MAX];

memset(hashtable,0,sizeof(hashtable));

//将str2中字符对应的hashtable数组中的位置上的值设为ture

while(*str2 !&＃61; &＃39;\0&＃39;)

{

//ASCII值在128-255之间的的字符&＃xff0c;

//用char保存&＃xff0c;转化为int型,在-128--1之间

int index;

if(*str2 >&＃61; 0)

index &＃61; *str2;

else

index &＃61; *str2 &＃43; 256;

hashtable[index] &＃61; true;

&＃43;&＃43;str2;

}

char *pFast &＃61; str1;

char *pSlow &＃61; str1;

while(*pFast !&＃61; &＃39;\0&＃39;)

{

int index;

if(*pFast >&＃61; 0)

index &＃61; *pFast;

else

index &＃61; *pFast &＃43; 256;

//无论是否碰到要删除的字符&＃xff0c;pFast都后移&＃xff0c;

//只有没碰到要删除的字符时&＃xff0c;pSlow才后移

if(!hashtable[index])

*pSlow&＃43;&＃43; &＃61; *pFast;

&＃43;&＃43;pFast;

}

*pSlow &＃61; &＃39;\0&＃39;;

}

int main()

{

char str1[] &＃61; "They are students";

char str2[] &＃61; "Tt";

DeleteChars(str1,str2);

puts(str1);

return 0;

}

测试结果&＃xff1a;

http://www.dengb.com/Javabc/777601.htmlwww.dengb.comtruehttp://www.dengb.com/Javabc/777601.htmlTechArticle剑指offer上的字符串相关题目。 题目&＃xff1a;输入两个字符串&＃xff0c;从第一字符串中删除第二个字符串中所有的字符。例如&＃xff0c;输入They are students.和aei...