前景提要
由于帖子的篇幅所限,我们会对每一个分类都提及,如果想深挖且时间充裕的同学可以报一下我的课,我总结了十类改编题,每一类都有多个改编的案例,一类需要四-五个小时的钻研。
我们这里回过头最后再说一个哈希的改编案例,接下来我们要说 array 和 linked list 这对相爱相杀的兄弟。
我们接着来看一个哈希表的例子:老规矩,先上原题:
给定 string 数组把所有“同构词”聚在一起。
例: ["eat", "tea", "tan", "ate", "nat", "bat"], 返回: [
["ate", "eat","tea"],
["nat","tan"],
["bat"] ]
说明:如果两个单词所组成的字母完全相同,只是字母位置不同,我们叫它们 anagrams 。首先我们冷静分析一下,既然是用哈希表,一定要有适合做 key 的元素。那么需要找到适合的 key,应该怎么去做呢?我们观察一下,"tea" 和“ate”只是存在顺序的区别,最终这两个单词能够被映射到同样的”同构词“,也就是我们的 group 需求,把 anagram 全凑起来,我们在每次哈希前,把字母排个序,那么所有 anagram 的哈希值就会一样。我们用 string 做 key,不过需要将 key 排序后的结果当 key,得解。