微软面试真题+面试官改编 leetcode 思路（哈希篇-加更）
longSwordMan · 2020-06-23 11:32:12 +08:00 · 1712 次点击这是一个创建于 1595 天前的主题，其中的信息可能已经有所发展或是发生改变。
由于帖子的篇幅所限，我们会对每一个分类都提及，如果想深挖且时间充裕的同学可以报一下我的课，我总结了十类改编题，每一类都有多个改编的案例，一类需要四-五个小时的钻研。
我们这里回过头最后再说一个哈希的改编案例，接下来我们要说 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，得解。
 |
1
longSwordMan OP 知道思路后，我们看一看改编真题：
1.把所有 major anagram 聚在一起。major anagram 得定义是，超过 50%的字母是通过调换位置得到，比如： "ate" 和 “tee”，字母 t 和 e 可以通过调换位置，使得两个单词有 50%以上相同。"ate"是"eeeee"的 major anagram，但"eeeee"不是"ate"的 major anagram 。 |
|
2
longSwordMan OP 这个时候，一定要坐稳，不能慌，题看着像但是死活想不出来其实是很受挫的，但是我们冷静一下，找找两题之间的联系。这个时候，哈希值相同的条件变了，变成一个 major anagram，也就是大于半数。那我们先从子问题出发，给定两个单词，要判断这哥俩是不是 major anagram 怎么办？先把第一个数组变成哈希，
|
|
3
longSwordMan OP 令 m=0for i in chars1:
if i in hashset: m += 1 else: m -= 1 如果 m>0 则第一个被哈希的数是第二数的 major anagram 。 所以我们在外对每个 string 都做一次这样的判断，O(n^3)得解。 |
|
4
longSwordMan OP 2. 改编真题：拼接 string 对于一个 string list， 给出所有可以通过拼接得到另一个元素得组合，如 ["a" ,"b" ,"abc", "c", "d" , "ad"]，输出，[ ( ["a","b","c" ], "abc"), (["a", "d"], "ad") ]
|
|
5
longSwordMan OP 首先，还是强调的，不能紧张。碰到这种题，说明你已经和微软的距离越来越近了，要思考内在的联系。
我们还是拆解成子问题，首先如果给定了 string，让你去数组里找组合，是不是容易一些，举例子，target： "abc" ["a", "bc" , "b" ,"c"]，我们建一个循环遍历数组，先指到“a”，判断：a 是 abc 的子数列，那么我们的问题就可以变成，target: "bc", ["bc", "b", "c"]；那么循环第二次，到“bc”，bc 是 abc 的子数列，问题变成：target:"a" ["a", "b", "c"]。以此类推。 |
|
6
longSwordMan OP 子问题清楚了，我们来看完整的。那么完整的问题我们就需要自己找出所有的 target，target 是什么呢？
无非就是所有长度>1 的元素而已，问题解决。 更多经典原题的改编，可以加微信 longswordMAN 进群+听直播，注明 V2EX 的 id 即可。 |
Select Language