[问答题]
char *removechar(char *dst,const char *pattern)
{
if(dst==NULL|| pattern==NULL)
return NULL;
if(*pattern==0)
return dst;
bool hashmap[256]={false};
while(*pattern!=0)
hashmap[*pattern++]=true;
char *p=dst,*q=dst;
while(*q!=0)
{
if(hashmap[*q]==false)
{
*p=*q;
++p;
}
++q;
}
*p=0;
return dst;
}
发表于 2015-08-28 16:45:23
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
奉上解释
利用线性hash制作bitmap,使复杂度将为o(M+N),不是传统的o(M*N)
字符串的比较是基础。
//#define _REMOVE // 两处相同的 //删除模式串中出现的字符 #ifdef _REMOVE char *removeStr(char *A, char *B) { //大小写相关的话 int bitMapAll[26][2] = {0}; //ascii 0:0x31 ,A:0x41, B:0x61 if (A == NULL) return NULL ; if (B == NULL) return NULL; while (*B != '\0') { if ( (*B >= 'A' && *B <= 'Z' ) ) bitMapAll[(*B) - 'A'][1] = 1; else if (*B >= 'a' && *B <= 'z' ) bitMapAll[(*B) - 'a'][0] = 1; B++; } char *temp = new char[strlen(A)]; //A;//destory it int cnt = 0; while (*A != '\0') { if (*A >= 'A' && *A <= 'Z' ) if (bitMapAll[(*A) - 'A'][1]) //if(bitMapAll[*A+'A'-'a']) { A++; continue; } if (*A >= 'a' && *A <= 'z') if (bitMapAll[(*A) - 'a'][0]) { A++;; continue; }; cnt++; *temp = *A; A++; temp++; } *temp = '\0'; return temp - cnt; } //40minutes: //bitmap complex ;反转？ int main()//o(N) { char mA[] = "welcome to asted"; char mB[] = "aeiou"; char *A = mA, *B = mB; A = removeStr(A, B); printf("%s\n", A); system("pause"); delete A; return 0; //"This is the world"，B="abcdefghi" ,===>A="Ts s t worl" //char mA[]="This is the world"; //char mB[]="abcdefghi"; //如“welcome to asted”,模式串为“aeiou” } #endif