这是一个创建于 2007 天前的主题，其中的信息可能已经有所发展或是发生改变。
在微软作了三四年的面试官，面过几百人，早已经知道现在的小朋友喜欢刷题，自然不会傻到原原本本的去考 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]
 | 1 longSwordMan OP  1 分析：简单题，考的是哈希表，暴力两重循环必挂。现在网上的帖子都喜欢和你说 leetcode 第 XX 题 是高频题，其实都是懒人思维，属于新手的思维误区。真正高频的是一些特定的知识点，如果按这种“原题照搬”思维，题目稍微做一些变招，大概率是要马失前蹄。 这里的真正的高频考点是数据结构哈希表，划重点：哈希表的应用面试必考，一定会以某种形式在题目的某一部出现，以后还会讲到哈希表和二叉树，哈希表和二位数组等其他数据结构结合的变招。 |
| 2 longSwordMan OP 面试官改编思路： 1. 不同的运算规则，可以是乘除法，可以发明一个运算规则。 真题： 给定一个整数数组和一个目标值，找出数组中乘积为目标值的两个数。 示例: 给定 nums = [2, 7, 11, 15], target = 14 因为 nums[0] * nums[1] = 2 * 7 = 14 所以返回 [0, 1] 其实换汤不换药，乘除法注意考虑边界情况即可（除以零），如果面试官自己发明的运算法：比如运算符：bla 的规则是: X 'bla' Y = X*Y - X -Y 。 同样的，查表规则改一下而已，换汤不换药，注意考虑边界情况 。 |
| 3 longSwordMan OP 2. 换一个数据结构，看面试者是否能够利用规则，在时间复杂度上进一步优化。 当然有序数组也可以改成二叉树等其他数据结构，或者是一些具备某特性的数据结构。有序数组的话，注意用二分查找，可以把时间复杂度降到 O （ logn ），注意哈希表的构建时间复杂度是 O （ n ），能直接用二分查找就直接用，不要考虑哈希。 真题： 给定一个“拐弯数组”，由两个有序数组拼接而成，但两数组升降序相反。 如：[1,2,3] + [6, 5, 4] ---> [1,2,3, 6, 5,4]。 要求在拐弯数组中找到给定的 target 。 这题如果用哈希，虽然是 O(n)，但不是最优，没有用到数组的特性。我们先用二分法找到拐点，再到两个有序数组中二分，把复杂度优化到 O （ logn ） |
| 4 longSwordMan OP 3. 变成多数之和，比如 3 sum 。这样的改写容易真题： 给定一个有序整数数组和一个目标值，找出数组和为目标值的三个数。 示例: 给定 nums = [2, 7, 11, 15], target = 20 因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20 所以返回 [0, 1, 2] |
| 5 longSwordMan OP 思路类似，查两次表，但注意排除第一个数，比如 2+2+2 这种一个数重用多次的情况。 当然这都是容易的，如果三个数，再结合第 1 条变化，查表次数仍然是两次，但不要被复杂的运算搞晕，然后注意边界条件即可。 看完了这几个我出的改编面试真题，不知道看官们是否对原来的刷题方式有所改观呢？总之，没有所谓的高频题，只有高频知识点，我们刷题的同时也要勤加思考，思考背后的考察知识点，甚至可以依照我上面分享的改编思路，自己给自己出题，这样才能把刷题的效率最大化。刚才说的三类变体，本质上都是对 [哈希表] 这个知识点的考察，如果对题目本身死记硬背，而忽视知识本身，是非常低效的。那么哈希表这个数据结构的意义就在于：可以通过 O （ 1 ）的时间复杂度来查找元素是否存在于集合中，而不用 O （ n ）来遍历查找。 下次更新一些新的真题，着重说一些其他的哈希表的面试变招，会结合 leetcode 原题来说。 |
 | 6 noreplay 2020-06-10 12:30:35 +08:00 via Android 等更新，收藏了 |
 | 7 GromHellscream 2020-06-10 12:35:07 +08:00 谢谢分享，先收藏一波。 |
 | 8 hdbzsgm 2020-06-10 12:38:04 +08:00 1 是这个思路 我刷题喜欢 按模块来 链表 数组 哈希 树 图 然后再看看 字符串 greedy dp dfs bfs 类似变种的题就差不多了 |
| 9 longSwordMan OP @hdbzsgm 同路中人 |
| 10 longSwordMan OP @hdbzsgm 握爪 |
 | 11 basefas 2020-06-10 13:11:17 +08:00 所以说专栏呢？ |
 | 12 also24 nbsp; 2020-06-10 13:19:12 +08:00 @longSwordMan #3 有序数组的话，可以直接双指针 O(n) 解决吧 [ 1, 2, 3, 5, 8, 9 ], target = 8 1+9 = 10 > 8 1+8 = 9 > 8 1+5 = 6 < 8 2+5 = 7 < 8 3+5 = 8 |
| 14 also24 2020-06-10 13:23:19 +08:00 @longSwordMan #3 对于有序数组二分查找的方案， 因为第一个数字还是要遍历的也就是 O(n) ， 然后查询第二个数字的时候走二分查找需要 O(logn)， 所以实际上总体复杂度是 O(nlogn) 吧 |
 | 16 eastlhu 2020-06-10 13:27:14 +08:00 期待大佬的专栏 |
 | 17 WhyLevi 2020-06-10 14:47:39 +08:00 via iPhone 干货拉满 |
 | 18 xuzywozz 2020-06-10 15:24:18 +08:00 多谢分享，收藏了 |
 | 19 yamasa 2020-06-10 15:42:20 +08:00 马克 |
| 20 yamasa 2020-06-10 15:42:31 +08:00 收藏，后面学习 |
 | 21 zhouwei520 2020-06-10 15:44:28 +08:00 期待专栏文章 |
| 22 also24 2020-06-10 16:01:07 +08:00 3 @basefas #11 @eastlhu #16 @zhouwei520 #21 翻了下知乎，翻到了原回答和专栏地址： https://www.zhihu.com/question/32019460/answer/1268448274 https://zhuanlan.zhihu.com/c_1253290991295655936 BTW：看到原回答下面其实也在讨论二分查找解法实际上是 O(nlogn) 而不是 O(log) 的事儿 |
 | 23 Jooooooooo 2020-06-10 17:49:08 +08:00 好帖子 |
 | 24 gzfrankie 2020-06-10 18:43:08 +08:00 via iPhone @also24 二分那道题是 O(logn)啊，那道题跟哈希是没关系的。 这道题暴力解法就是 O(n)，从头到尾扫一次，直到扫到 num[i-1]<num[i] && num[i+1]>num[i+2]成立，那么 num[i]就是拐点。所以如果你提供一个比 O(n)还要慢的方法，不是自作多情么… 二分怎么做？起始范围选[0..n-1]，i 定为中点(n-1)/2 三个条件： 1.若 num[i-1]<num[i] && num[i+1]>num[i+2]成立，那么 num[i]就是拐点 2.若 num[i-1]<num[i] && num[i+1]<num[i+2]，那么前半边的数可以舍弃，二分范围定为[(n-1)/2, n-1]，继续二分 3.若 num[i-1]>num[i] && num[i+1]>num[i+2]，那么后半边的数可以舍弃，二分范围定为[0, (n-1)/2]，继续二分 因为每次二分都可以舍弃一半的数不用看，所以是 logn 。 *以上伪代码简洁起见我没有考虑各种边界条件。 |
| 25 longSwordMan OP @also24 感谢搬运，给定有序数组，查找目标的情况下二分查找是 O(logn)，如果超过 O （ n ）没理由不用哈希 |
| 26 longSwordMan OP @gzfrankie 正解 |
| 27 longSwordMan OP 晚些会拉群，加我的人太多操作不过来 |
| 28 longSwordMan OP @gzfrankie 征用一下哈，很多跟我帖的同学还是不懂 |
| 29 gzfrankie 2020-06-10 21:13:45 +08:00 via iPhone @longSwordMan 没问题的 |
 | 30 angcz 2020-06-10 21:52:59 +08:00 很棒啊 不过在论坛连载还是有很多不便之处 最好开个博客吧 |
| 31 also24 2020-06-10 22:33:56 +08:00 @gzfrankie #24 @longSwordMan #25 我知道为什么会产生误解了，我们说的压根不是同一道题目。 如下图所示，我其实针对的是黄色部分，我所说的题目是： 按照 Two Sum 的题目规则，寻找和为 target 的两个数，但是将给定数组改成有序数组。 针对黄色部分这道题，使用哈希解法和双指针解法的时间复杂度都为 O(n)，二分查找的时间复杂度为 O(nlogn)。 你们在说的是黄色部分的题目，即： 针对 『拐弯数组』，寻找给定的 target 。 针对蓝色部分这道题，使用哈希解法的时间复杂度是 O(n), 二分查找的时间复杂度为 O(logn) 顺带提一句，蓝色部分这道题，其实非常接近 leetcode 上的 『山脉数组中查找目标值』这道题： https://leetcode-cn.com/problems/find-in-mountain-array/ https://i.loli.net/2020/06/10/tVY6dhJgACaQbsP.png |
| 32 also24 2020-06-10 22:36:41 +08:00 修正 typo -> 你们在说的是蓝色部分的题目 |
| 33 longSwordMan OP @also24 是啊，所以第一题我没用二分查找啊，用了哈希，这不是整个帖子要表达的么？区别啥时候用哈希啥时候不用 |
| 34 also24 2020-06-10 22:51:35 +08:00 @longSwordMan #33 黄色部分是你在 3 楼发的前半部分，被误解成了在第一题的基础上替换为『有序数组』，其它条件不变。 知乎上和你争吵的那位，也是这样理解了，所以才一直认定是 O(nlogn) 的复杂度。 |
| 35 longSwordMan OP @also24 是的，我其实已经在说第二题了，估计没转过来。。 |
| 36 also24 2020-06-10 22:57:12 +08:00 @longSwordMan #35 因为你后面在说 『改编思路』嘛，而且改编 1 、改编 3 都是确实和原题主体内容一致的。 自然会觉得是改编 2 也是从原题上发展而来的。 结果蓝色部分的改编 2，从题目内容角度来说，其实和 Two Sum 已经完全无关了。 |
| 37 longSwordMan OP @also24 是的，第一篇的改编不是太好，主要是希望从简单题入手。后续可以关注我该系列的第二，第三篇 |
| 38 also24 2020-06-10 23:00:33 +08:00 1 |
 | 39 chendeshen 2020-06-10 23:08:29 +08:00 via Android 这个适合开个微信群 |
| 40 longSwordMan OP @also24 是的，感谢指出缺点 |
 | 41 0xo 2020-06-10 23:14:30 +08:00 via Android 在地上也看到 lz 了，lz 为啥后来被禁言了[好奇] |
| 42 longSwordMan OP @ccvzz 我也想知道。。。 |
 | 43 shiji 2020-06-10 23:43:57 +08:00 via iPhone 为什么我最近总看到这篇文章... |
 | 44 Ahian 2020-06-11 00:53:08 +08:00 via Android 权威 |
| 45 longSwordMan OP @Ahian 过奖哈 |
| 46 longSwordMan OP 我们接着再看一题，看一看怎么去用动态规划的思路来解题。 给定整数数列 nums, 找到连续和最大的子数列，并返回数列和和，例： Input: [-2,1,-3,4,-1,2,1,-5,4], Output: 6 其中[4,-1,2,1]加起来为 6 。 |
| 47 longSwordMan OP 还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。那么正确的解法是怎样的呢？我们接下来说这道题背后考察的要点和面试官改编的思路。 我估计不少人需要 O(n^3)才做得出来，如果我告诉你，这题的最优解法是 O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要头脑冷静分析，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有八九是背答案，依然是不给过。 |
| 48 longSwordMan OP 如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？ |
| 49 longSwordMan OP 大家可以思考一下，这题的思路在哪，晚上来更新答案。 |
| 50 longSwordMan OP 这两天疫情加重，和领导各种开会讨论下一阶段的工作安排，有点忙破头，断了几天大家海涵，接下去会继续我们的问题改写 |
| 51 longSwordMan OP 有思路的同学可以回复一下代码实现，晚上我会统一回复 |
| 52 longSwordMan OP 我们接着今天早上的话题继续聊。 今天早上我们谈到当确定了数组中的某一个元素作为子数列的元素，我们该如何找最大的子数列的问题。那我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？ 这时候，我们往前看一位，如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个以 A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是 A[i-1]为尾数的子数列，拼上 A[i]。那么以此类推，在一轮循环中，我们找到以 A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。 |
| 53 longSwordMan OP 我们举例说明：[1, 1, 3, 4, 1, 2, 1, 5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为 arr[1]的前一个数 arr[0]为终点的子数列是负数，所以以 arr[1]为终点，最大子数列就是自己，和就是 1，以此类推，直到最后一位。 |
| 54 longSwordMan OP 在这里，前一位和后一位的联系就是上述的规则：如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个最大子数列就是{A[i]}，只有一个元素，反之，则是 A[i-1]为尾数的子数列，拼上 A[i]，用前一轮的结果，来推算下一个脚标的结果。 |
| 55 longSwordMan OP 代码实现： def max_subarray(A): max_ending_here = max_so_far = A[0] for x in A: max_ending_here = max(x, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far |
| 56 longSwordMan OP 大家可以先思考一下，明天我会继续更新这种题型的变体，如果有疑问可以在评论区留言。 |
| 57 longSwordMan OP 在昨天我们讲完了原题，那今天想与大家分享一下这类题型的变体： 1. 给定一个数列，例如 [2, 1, 3, 4, 1, 2, 1, 5, 4] ， 求一个连续的数列使得数列内的元素乘积最大。 |
| 58 longSwordMan OP 第一印象相信大家都会感到，很相似。但我们思考一下终究有什么不同，唯一的不同就是，可能负负得正。那么，我们不仅要记录正向的最大，还要记录负向的最大。方便起见，我们把最大负向值表做最小值。 |
| 59 longSwordMan OP 所以，这题动态规划的关系就是：目前角标的最大乘积是，如果该数为负，则和前一位数结尾的最小值相乘，若果为正，则和前一位数结尾的最大值相乘；目前角标的最小乘积是，如果该数为负，则和前一位数结尾的最大值相乘，若果为负，则和前一位数结尾的最小值相乘。 |
| 60 longSwordMan OP 我们再看变体 2 2. 有一个数列，代表牌的顺序，在 21 点游戏中能得到的最高点数（最接近，且小于 21 点） 参考一下我们前题题的做法，如果向后找爆点了（大于 21 ），则把数组的最左端元素删去，直到小于 21 。由于牌点数大于 21 点的期望是 3 张牌，所以时间复杂度上仍然是 O （ N ） |
| 61 longSwordMan OP 也就是著名的二十一点问题，（学会了就可以制霸赌场了）大家思考一下这题作为改编，和原题有什么关联，应该如何去解 |
| 62 longSwordMan OP 也就是做四次运算，把最大最小的都考虑上。 |
| 63 longSwordMan OP 我们接着通过原题和面试真题改编，看一看关于哈希表的应用。 我们先来看 leetcode 上第 1 号问题：Two Sum： 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] |
| 64 longSwordMan OP 简单题，考的是哈希表，暴力两重循环必挂。现在网上的帖子都喜欢和你说 leetcode 第 XX 题 是高频题，其实都是懒人思维，属于新手的思维误区。真正高频的是一些特定的知识点，如果按这种“原题照搬”思维，题目稍微做一些变招，大概率是要马失前蹄。 |
| 65 longSwordMan OP 这里的真正的高频考点是数据结构哈希表，划重点：哈希表的应用面试必考，一定会以某种形式在题目的某一部出现，以后还会讲到哈希表和二叉树，哈希表和二位数组等其他数据结构结合的变招。大家可以思考一下在原题基础上我们可以如何改编？下午与大家分享面试官的改编思路。 |
| 66 longSwordMan OP 下面给大家分享一下作为面试官的改编思路： 1. 不同的运算规则，可以是乘除法，可以发明一个运算规则。 |
| 67 longSwordMan OP 真题： 给定一个整数数组和一个目标值，找出数组中乘积为目标值的两个数。 |
| 68 longSwordMan OP 示例: 给定 nums = [2, 7, 11, 15], target = 14 因为 nums[0] * nums[1] = 2 * 7 = 14 所以返回 [0, 1] |
| 69 longSwordMan OP 其实换汤不换药，乘除法注意考虑边界情况即可（除以零），如果面试官自己发明的运算法：比如运算符：bla 的规则是: X 'bla' Y = X*Y - X -Y 。 同样的，查表规则改一下而已，换汤不换药，注意考虑边界情况 。 |
| 70 longSwordMan OP 接着给大家分享下一个改变思路： 换一个数据结构，看面试者是否能够利用规则，在时间复杂度上进一步优化。真题： 给定一个有序整数数组和一个目标值，找出数组中和为目标值的两个数。 |
| 71 longSwordMan OP 示例: 给定 nums = [2, 7, 11, 15], target = 13 因为 nums[0] + nums[2] = 13 所以返回 [0, 2] |
| 72 longSwordMan OP 当然有序数组也可以改成二叉树等其他数据结构，或者是一些具备某特性的数据结构。有序数组的话，注意用二分查找，可以把时间复杂度降到 O （ logn ） |
| 73 longSwordMan OP 今天继续给大家分享关于这道题的最后一个面试官改变思路： 变成多数之和，比如 3 sum 。这样的改写容易真题： 给定一个有序整数数组和一个目标值，找出数组和为目标值的三个数。 |
| 74 longSwordMan OP 示例: 给定 nums = [2, 7, 11, 15], target = 20 因为 nums[0] + nums[1] + nums[2] = 2 + 7 + 11 = 20 所以返回 [0, 1, 2] |
| 75 longSwordMan OP 思路类似，查两次表，但注意排除第一个数，比如 2+2+2 这种一个数重复用多次的情况。 |
| 76 longSwordMan OP 当然这都是容易的，如果三个数，再结合第 1 条变化，查表次数仍然是两次，但不要被复杂的运算搞晕，然后注意边界条件即可。 |
 | 77 9LCRwvU14033RHJo 2020-11-03 12:28:27 +08:00 谢谢。变题思路很有意思，学会了就可以自己给自己出题了。 @longSwordMan |
Select Language