实操案例:字符串哈希表操作
摘要:当遇到C语言库没有字符串哈希表的时候,该如何进行操作。
有考C语言可信编程认证的同事经常会问到,C语言库没有字符串哈希表操作,那考试遇到了怎么办。虽然历次考试的题目中没有必须要用到C语言哈希表的题目(至少我都能用常规C做出来),但是还需要防患未然,这里给出一道有代表性的题目,可以尝试做做看:https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
这题不考虑编程语言的话,用哈希表会比较简单,那要是用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- 代码
有了字符串哈希函数,就能够将大串字符串转换成数字,数字进而可以作为数组的下标(key)存储信息。那么哈希表的大小怎么取呢?一般大小要大于存储的数据个数,比如最多100个数据,存到哈希表的话大小肯定要大于100才行。对于这题而言,没有明确告诉你单词的最大个数,只能估值了,这里经过几轮提交测试,得到哈希表大小与通过用例个数的关系,说明这道题目最多的单词数可能在300左右,平均个数<50个吧:
这里给出我的解答:
C 代码
版权声明: 本文为 InfoQ 作者【华为云开发者社区】的原创文章。
原文链接:【http://xie.infoq.cn/article/b17a4972689c87ada20566785】。文章转载请联系作者。
评论