共计 2457 个字符,预计需要花费 7 分钟才能阅读完成。
摘要: 当遇到 C 语言库没有字符串哈希表的时候,该如何进行操作。
有考 C 语言可信编程认证的共事常常会问到,C 语言库没有字符串哈希表操作,那考试遇到了怎么办。尽管历次考试的题目中没有必须要用到 C 语言哈希表的题目(至多我都能用惯例 C 做进去),然而还须要防患未然,这里给出一道有代表性的题目,能够尝试做做看:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一些长度雷同的单词 words。找出 s 中恰好能够由 words 中所有单词串联造成的子串的起始地位。
留神子串要与 words 中的单词齐全匹配,两头不能有其余字符,但不须要思考 words 中单词串联的程序。
示例:输出:s = "barfoothefoobarman",
words = ["foo","bar"]
输入:[0,9]
解释:从索引 0 和 9 开始的子串别离是 "barfoo" 和 "foobar"。输入的程序不重要, [9,0] 也是无效答案。
这题不思考编程语言的话,用哈希表会比较简单,那要是用 C 语言的话,能够本人撸个哈希表用,凑合这类题目还是入不敷出的。
思路的话参考 https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-6/ 中的解法二,这里只讲下怎么最简略结构一个哈希表。
首先是选取哈希函数,这里我用的是 djb2 算法,参考 http://www.cse.yorku.ca/~oz/hash.html,碰撞率相当低,散布均衡,实现也很简略,就两三行代码,记住要害数字 (5381 和 33)。
If you just want to have a good hash function, and cannot wait, djb2 is one of the best string hash functions i know. it has excellent distribution and speed on many different sets of keys and table sizes.
Language- 代码
unsigned long
hash(unsigned char *str)
{
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
有了字符串哈希函数,就可能将大串字符串转换成数字,数字进而能够作为数组的下标(key)存储信息。那么哈希表的大小怎么取呢?个别大小要大于存储的数据个数,比方最多 100 个数据,存到哈希表的话大小必定要大于 100 才行。对于这题而言,没有明确通知你单词的最大个数,只能估值了,这里通过几轮提交测试,失去哈希表大小与通过用例个数的关系,阐明这道题目最多的单词数可能在 300 左右,均匀个数 <50 个吧:
5 -> 110/173
10 -> 143/173
50 -> 170/173
100 -> 170/173
300 -> 172/173
400 -> 173/173
这里给出我的解答:
C 代码
// 字符串最大值,hash 表大小,估值和理论数据个数无关
#define MAXWORDCOUNT 1000
static int wordCount[MAXWORDCOUNT];
static int currWordCount[MAXWORDCOUNT];
// ref: http://www.cse.yorku.ca/~oz/hash.html
unsigned long DJBHash(const char* s, int len) {
unsigned long hash = 5381; // 经验值,hash 抵触概率低,散布均衡
while (len--) {hash = (((hash << 5) + hash) + *(s++)) % MAXWORDCOUNT; /* hash * 33 + c */
}
return hash;
}
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){memset(wordCount, 0, sizeof(wordCount));
*returnSize = 0;
const int kSLen = strlen(s);
if (kSLen == 0 || wordsSize == 0) return NULL;
const int kWordLen = strlen(words[0]);
// 将单词数量存到哈希表中,key: word, value: 单词数量
for (int i = 0; i < wordsSize; ++i)
++wordCount[DJBHash(words[i], kWordLen)];
int *result = malloc(sizeof(int) * kSLen);
for (int i = 0; i < kWordLen; ++i) {for (int j = i; j + kWordLen * wordsSize <= kSLen; j += kWordLen) {
// 统计以后窗口的单词数量
for (int k = (j == i ? 0 : wordsSize - 1); k < wordsSize; ++k)
++currWordCount[DJBHash(s + j + k * kWordLen, kWordLen)];
// 判断两个哈希表是否相等,即窗口中的单词是否和给定词典齐全匹配
if (memcmp(wordCount, currWordCount, sizeof(wordCount)) == 0)
result[(*returnSize)++] = j;
--currWordCount[DJBHash(s + j, kWordLen)];
}
// 哈希表清零操作
memset(currWordCount, 0, sizeof(currWordCount));
}
return result;
}
点击关注,第一工夫理解华为云陈腐技术~