在微软做了四年面试官，分享一下刷 leetcode 的正确姿势

2020-06-10 12:26:10 +08:00
 longSwordMan

在微软作了三四年的面试官，面过几百人，早已经知道现在的小朋友喜欢刷题，自然不会傻到原原本本的去考 leetcode 的原题。所以最好不要通过死记硬背，想要碰到原题来制霸面试。

划重点：编程面试，只有高频知识点，没有所谓的高频题。

众所周知，微软以及诸多其他大厂的面试算法题主要是以 leetcode 为素材的改编，我现在分享一些面试真题以及我自己和同事作为面试官的改编思路，希望可以帮到还在苦战刷题的同学。我会将大部分的 leetcode 原题过一遍，再附上面试真题的改写思路，尽量讲得傻瓜。由于篇幅限制，在这里我只举几个小栗子，更多面试真题和改写大家可以关注我的专栏文章。

我尽量保持每周两更+回复评论，看后续的反馈情况决定是否改变更新频率以及增减分享的内容，每条评论回复都会看，也可以加微信交流：longswordMAN，注明 V2EX 的 id 即可。

————————————————————————————————————————

废话不多说，正题开始：

我们先来看 leetcode 上第 1 号问题：Two Sum：

给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。

你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

10179 次点击
所在节点    LeetCode
77 条回复
longSwordMan
2020-06-18 11:51:28 +08:00
也就是著名的二十一点问题，（学会了就可以制霸赌场了）大家思考一下这题作为改编，和原题有什么关联，应该如何去解
longSwordMan
2020-06-18 11:54:02 +08:00
也就是做四次运算，把最大最小的都考虑上。
longSwordMan
2020-06-19 11:01:06 +08:00
我们接着通过原题和面试真题改编，看一看关于哈希表的应用。

我们先来看 leetcode 上第 1 号问题：Two Sum：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。

示例:
给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
longSwordMan
2020-06-19 11:01:38 +08:00
简单题，考的是哈希表，暴力两重循环必挂。现在网上的帖子都喜欢和你说 leetcode 第 XX 题 是高频题，其实都是懒人思维，属于新手的思维误区。真正高频的是一些特定的知识点，如果按这种“原题照搬”思维，题目稍微做一些变招，大概率是要马失前蹄。
longSwordMan
2020-06-19 11:02:59 +08:00
这里的真正的高频考点是数据结构哈希表，划重点：哈希表的应用面试必考，一定会以某种形式在题目的某一部出现，以后还会讲到哈希表和二叉树，哈希表和二位数组等其他数据结构结合的变招。大家可以思考一下在原题基础上我们可以如何改编？下午与大家分享面试官的改编思路。
longSwordMan
2020-06-19 16:50:22 +08:00
下面给大家分享一下作为面试官的改编思路：
1. 不同的运算规则，可以是乘除法，可以发明一个运算规则。
longSwordMan
2020-06-19 16:50:40 +08:00
真题：
给定一个整数数组和一个目标值，找出数组中乘积为目标值的两个数。
longSwordMan
2020-06-19 16:50:54 +08:00
示例:
给定 nums = [2, 7, 11, 15], target = 14
因为 nums[0] * nums[1] = 2 * 7 = 14
所以返回 [0, 1]
longSwordMan
2020-06-19 16:51:07 +08:00
其实换汤不换药，乘除法注意考虑边界情况即可（除以零），如果面试官自己发明的运算法：比如运算符：bla 的规则是: X 'bla' Y = X*Y - X -Y 。 同样的，查表规则改一下而已，换汤不换药，注意考虑边界情况 。
longSwordMan
2020-06-21 13:53:32 +08:00
接着给大家分享下一个改变思路：
换一个数据结构，看面试者是否能够利用规则，在时间复杂度上进一步优化。真题：
给定一个有序整数数组和一个目标值，找出数组中和为目标值的两个数。
longSwordMan
2020-06-21 13:53:44 +08:00
示例:
给定 nums = [2, 7, 11, 15], target = 13
因为 nums[0] + nums[2] = 13
所以返回 [0, 2]
longSwordMan
2020-06-21 13:53:57 +08:00
当然有序数组也可以改成二叉树等其他数据结构，或者是一些具备某特性的数据结构。有序数组的话，注意用二分查找，可以把时间复杂度降到 O （ logn ）
longSwordMan
2020-06-22 11:06:39 +08:00
今天继续给大家分享关于这道题的最后一个面试官改变思路：
变成多数之和，比如 3 sum 。这样的改写容易真题：
给定一个有序整数数组和一个目标值，找出数组和为目标值的三个数。
longSwordMan
2020-06-22 11:06:53 +08:00
示例:
给定 nums = [2, 7, 11, 15], target = 20
因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20
所以返回 [0, 1, 2]
longSwordMan
2020-06-22 11:07:05 +08:00
思路类似，查两次表，但注意排除第一个数，比如 2+2+2 这种一个数重复用多次的情况。
longSwordMan
2020-06-22 11:07:14 +08:00
当然这都是容易的，如果三个数，再结合第 1 条变化，查表次数仍然是两次，但不要被复杂的运算搞晕，然后注意边界条件即可。
9LCRwvU14033RHJo
2020-11-03 12:28:27 +08:00
谢谢。变题思路很有意思，学会了就可以自己给自己出题了。 @longSwordMan

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://ex.noerr.eu.org/t/680304

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX