迅雷的一道面试题。。。看谁做出来
时间：2010-06-08 来源：sinodragon21
写一个方法：
public String delString(String A,String B){
.....方法体......
}
用高效的方式从A中剔除包含B的字符，例如String A="hi are you ok";
String B="io";delString方法返回"h are yu k"
注意：不能使用String的instand of ,splid,char at等等库函数
请问怎么做？
===============================================================
最近在网上看到篇文章，一起拜一拜暴雪
先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有 这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把 这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。
最合适的算法 自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常 小，下面看看在MPQ中的Hash算法
unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
while(*key != 0)
{
ch = toupper(*key++);
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
Blizzard 的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一 个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表 (Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快 的O(1)，现在仔细看看这个算法吧
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}
看到此，我想大家都在想一个很 严重的问题："如果两个字符串在哈希表中对应的位置相同怎么办？",毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是 用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对 应的字符串就OK了。
事情到此似乎有了完美的结局，如果是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而 Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。
中 国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个 不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。
现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延" 的方式来解决问题，看看这个算法：
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos + 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
return -1; //Error value
}
======================================================
前面不是有人说用hash了么....其实也可以说不叫hash
既然是关于字符的，那首先对字符串B的字符建个出现数组bool bToDelete[]，
字符的个数总是有限的，比如限制字符是在小写英文字母集合中,那数组大小就开26即可，0-25分别表示字符a-z
bToDelete[0] = 1 表示B中存在字符‘a’，否则表示没有‘a’；
bToDelete[1] = 1 表示B中存在字符‘b’，否则表示没有‘b’；
……
bToDelete[25] = 1 表示B中存在字符‘z’，否则表示没有‘z’；
然后扫描一边字符串B，即可确定bToDelete。
接 下来扫描一边字符串A，再建一新字符串C保存删除后的结果。
即bToDelete[A[i]-'a']=0，则存入C中。。。。。
算 法复杂度O（n），不需要平方级别的。
=======================================================
想速度快，只能空间换时间。
Set=Map方法其实和上面的暴雪崇拜者的 方法是一样的。
步骤一 设计一个散列函数可以散列出hashCode,
步骤2 然后把b字符串的所有字符 用这个散列函数计算出一个code，把code当作偏移作为数组下标，把数组的那个偏移的单位标记成true；
步骤3 把a字符串所有字符，计算散列，查看在这个散列作为坐标情况下那个单位的标记是true还是false 是true说明有这个字符，是false说明b字符串中没有a当前这个字符。
提供一种简单方法：
{
1 int [] hashtable = new Int32[2<<16];
2 把hashtable里内容置0
3 char[] bchars = B.toCharArray();
4 for(char tempch:bchars)
{ hashtable[(uint)tempch] = 1;}
5 string result="";
6 char[] achars = A.toCharArray();
7 for(char tempaa :achars)
{if(hashtable[(uint)tempaa)]!=1
result += tempaa;
}
8 return result;
}
缺陷还是一点，需要开设的空间太大。可能大家不是很清楚，当空间过大需要用到swap虚拟内存 时，也许效率会得不偿失。
给出一个改进方案：由于b中每个字符都是char（在java中char用unicode编码占2字节），也就 是char用16位表示，2的16次方是65536.需要开设65536个空间吗？好像65536不是很大的空间，但是为了构造节约型社会，能省则省。
把 65536个标志用的空间，从Int32 降低为bool,也就是说 只需要65536/32=2048个int单元即可。
太晚了具体做法不给出 了，有兴趣的可以实现一下，提示：位存储
算法和程序是一回事，如果不是这样，程序员真可以当民工了
=======================================================
public String delString(String A,String B){
.....方法体......
}
用高效的方式从A中剔除包含B的字符，例如String A="hi are you ok";
String B="io";delString方法返回"h are yu k"
注意：不能使用String的instand of ,splid,char at等等库函数
请问怎么做？
===============================================================
最近在网上看到篇文章，一起拜一拜暴雪
先提一个简单的问题，如果有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有 这个字符串并找到它，你会怎么做？
有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把 这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。
最合适的算法 自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常 小，下面看看在MPQ中的Hash算法
unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;
while(*key != 0)
{
ch = toupper(*key++);
seed1 = cryptTable[(dwHashType << 8) + ch] ^ (seed1 + seed2);
seed2 = ch + seed1 + seed2 + (seed2 << 5) + 3;
}
return seed1;
}
Blizzard 的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一 个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表 (Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快 的O(1)，现在仔细看看这个算法吧
int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;
if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}
看到此，我想大家都在想一个很 严重的问题："如果两个字符串在哈希表中对应的位置相同怎么办？",毕竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是 用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我遇到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对 应的字符串就OK了。
事情到此似乎有了完美的结局，如果是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而 Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。
中 国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，如果说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个 不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。
现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延" 的方式来解决问题，看看这个算法：
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;
while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos + 1) % nTableSize;
if (nHashPos == nHashStart)
break;
}
return -1; //Error value
}
======================================================
前面不是有人说用hash了么....其实也可以说不叫hash
既然是关于字符的，那首先对字符串B的字符建个出现数组bool bToDelete[]，
字符的个数总是有限的，比如限制字符是在小写英文字母集合中,那数组大小就开26即可，0-25分别表示字符a-z
bToDelete[0] = 1 表示B中存在字符‘a’，否则表示没有‘a’；
bToDelete[1] = 1 表示B中存在字符‘b’，否则表示没有‘b’；
……
bToDelete[25] = 1 表示B中存在字符‘z’，否则表示没有‘z’；
然后扫描一边字符串B，即可确定bToDelete。
接 下来扫描一边字符串A，再建一新字符串C保存删除后的结果。
即bToDelete[A[i]-'a']=0，则存入C中。。。。。
算 法复杂度O（n），不需要平方级别的。
=======================================================
想速度快，只能空间换时间。
Set=Map方法其实和上面的暴雪崇拜者的 方法是一样的。
步骤一 设计一个散列函数可以散列出hashCode,
步骤2 然后把b字符串的所有字符 用这个散列函数计算出一个code，把code当作偏移作为数组下标，把数组的那个偏移的单位标记成true；
步骤3 把a字符串所有字符，计算散列，查看在这个散列作为坐标情况下那个单位的标记是true还是false 是true说明有这个字符，是false说明b字符串中没有a当前这个字符。
提供一种简单方法：
{
1 int [] hashtable = new Int32[2<<16];
2 把hashtable里内容置0
3 char[] bchars = B.toCharArray();
4 for(char tempch:bchars)
{ hashtable[(uint)tempch] = 1;}
5 string result="";
6 char[] achars = A.toCharArray();
7 for(char tempaa :achars)
{if(hashtable[(uint)tempaa)]!=1
result += tempaa;
}
8 return result;
}
缺陷还是一点，需要开设的空间太大。可能大家不是很清楚，当空间过大需要用到swap虚拟内存 时，也许效率会得不偿失。
给出一个改进方案：由于b中每个字符都是char（在java中char用unicode编码占2字节），也就 是char用16位表示，2的16次方是65536.需要开设65536个空间吗？好像65536不是很大的空间，但是为了构造节约型社会，能省则省。
把 65536个标志用的空间，从Int32 降低为bool,也就是说 只需要65536/32=2048个int单元即可。
太晚了具体做法不给出 了，有兴趣的可以实现一下，提示：位存储
算法和程序是一回事，如果不是这样，程序员真可以当民工了
=======================================================
相关阅读 更多 +
