打造最快的Hash表(转) [以暴雪的游戏的Hash为例]
先提一个简单的问题,如果有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?
有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但…也只能如此了。
先提一个简单的问题,如果有一个庞大的字符串数组,然后给你一个单独的字符串,让你从这个数组中查找是否有这个字符串并找到它,你会怎么做?
有一个方法最简单,老老实实从头查到尾,一个一个比较,直到找到为止,我想只要学过程序设计的人都能把这样一个程序作出来,但要是有程序员把这样的程序交给用户,我只能用无语来评价,或许它真的能工作,但…也只能如此了。
POJ打破传统,以前是做一题送一题,现在是做一题送两题,那么我们就不用客气了
言归正传 题号:2606 Rabbit hunt 2780 Linearity 1118 Lining Up
大致题意是输入N个点.计算能穿过最多的点的直线,并输出最大点的个数
资料由互联网收集整理,供新手参考学习 这里又生动点的演示:http://www.cnblogs.com/wangfupeng1988/archive/2011/12/26/2302216.html
这题是一道DP问题,我的想法如下:
1.可以令 deleteNum[pos]为输入字符串在pos处需要删除的最少字符数量;
2.如果输入字符串长度为len,则初始化deleteNum[len] = 0;(字符串由0开始计数)
//并查集
//注意类型匹配
const int maxn = 100002;
int DSet[maxn];
void init(int n) {
for(int i = 0 ; i <= n ; i ++)
DSet[i] = i;
}
int findP(int id) {
if(DSet[id] != id)
DSet[id] = findP(DSet[id]);
return DSet[id];
}
//返回根节点ID
int UnionEle(int a,int b) {
a = findP(a);
b = findP(b);
if(a > b)
a ^= b ^= a ^= b;
DSet[b] = a;
return a;
}
/**
* KMP模式匹配
* 算法复杂度O(m+n)
* ACM 模板
*
* @Author OWenT
* @link http://www.owent.net
*/
// 最大字符串长度
const int maxLen = 10000;
// 前一个匹配位置,多次匹配注意要重新初始化
// 注:preMatch[i]表示0~preMatch[i-1]能和?~i匹配
int preMatch[maxLen]={0};
/**
* kmp匹配算法
* @param char[] source 查找源
* @param char[] checked 查找目标
* @return int 根据以下两个分支返回值分别表示不同的含义
*/
int kmp_match(char source[],char checked[]) {
int i = 0, j = 0;
memset(preMatch, 0, sizeof(preMatch));
if(!checked[i]) // 被匹配串为空串,直接返回 0
return 0;
++ i;
while(checked[i]) {
for(j = preMatch[i - 1]; checked[i] != checked[j] && j; j = preMatch[j - 1]);
preMatch[i] = (checked[i] == checked[j])? j + 1 : 0 ;
++ i;
}
//计算匹配子串个数(子串间无重叠)(与以下一起二选一)
int num = 0;//计数变量
for(i = j = 0; source[i]; ++ i) {
if(checked[j] == source[i])
++ j;
else if(j)
-- i, j = preMatch[j - 1];
if(!checked[j])
++ num, j = 0;//如果要子串间重叠 则此句中j = 0 改成 j = preMatch[j - 1]
}
return num;
//计算首个匹配子串位置(与以上一起二选一)
for(i = j = 0; checked[j] && source[i]; ++ i) {
if(checked[j] == source[i])
++ j;
else if(j)
-- i, j = preMatch[j - 1];
}
//返回匹配的串的第一个字符出现位置(从1开始计数,0表示无匹配)
if(!checked[j])
return i - j + 1;
else
return 0;
return 0;
}