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