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

[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]

[ccvzz]

在地上也看到 lz 了，lz 为啥后来被禁言了[好奇]

[longSwordMan]

@ccvzz 我也想知道。。。

[shiji]

为什么我最近总看到这篇文章...

[Ahian]

权威

[longSwordMan]

@Ahian 过奖哈

[longSwordMan]

我们接着再看一题，看一看怎么去用动态规划的思路来解题。

给定整数数列 nums, 找到连续和最大的子数列，并返回数列和和，例：

Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6

其中[4,-1,2,1]加起来为 6 。

[longSwordMan]

还是老套路，一个角标变两个角标而已，和上题一样，暴力两重循环必挂。那么正确的解法是怎样的呢？我们接下来说这道题背后考察的要点和面试官改编的思路。

我估计不少人需要 O(n^3)才做得出来，如果我告诉你，这题的最优解法是 O(n)，咋一看是不是不敢相信？我们要想不去暴力解，必须要头脑冷静分析，这个子数列的一些特征。作为面试官，如果这题面试者不假思索地写答案，如果还写对了，十有八九是背答案，依然是不给过。

[longSwordMan]

如果，我们确定了数组中的某一个元素作为子数列的元素，那么我们该如何找最大的子数列？我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？

[longSwordMan]

大家可以思考一下，这题的思路在哪，晚上来更新答案。

[longSwordMan]

这两天疫情加重，和领导各种开会讨论下一阶段的工作安排，有点忙破头，断了几天大家海涵，接下去会继续我们的问题改写

[longSwordMan]

有思路的同学可以回复一下代码实现，晚上我会统一回复

[longSwordMan]

我们接着今天早上的话题继续聊。

今天早上我们谈到当确定了数组中的某一个元素作为子数列的元素，我们该如何找最大的子数列的问题。那我们不妨把问题简化一下：如果，我们确定了数组中的某一个元素作为子数列的最末位数，那么我们该如何找最大的子数列？

这时候，我们往前看一位，如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个以 A[i]为尾数的最大子数列就是{A[i]}，只有自身一个元素；反之，如果和是正数，则是 A[i-1]为尾数的子数列，拼上 A[i]。那么以此类推，在一轮循环中，我们找到以 A[i]为终点的子数列最大和，一轮循环过后，就得到我们的答案了。

[longSwordMan]

我们举例说明：[−1, 1, −3, 4, −1, 2, 1, −5, 8]，以第一个数为终点，最大的子数列就是自己，最大和为-1，第二个数，因为 arr[1]的前一个数 arr[0]为终点的子数列是负数，所以以 arr[1]为终点，最大子数列就是自己，和就是 1，以此类推，直到最后一位。

[longSwordMan]

在这里，前一位和后一位的联系就是上述的规则：如果以 A[i-1]作为尾数的子数列，加起来全是负值，那么这个最大子数列就是{A[i]}，只有一个元素，反之，则是 A[i-1]为尾数的子数列，拼上 A[i]，用前一轮的结果，来推算下一个脚标的结果。

[longSwordMan]

代码实现：
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

[longSwordMan]

大家可以先思考一下，明天我会继续更新这种题型的变体，如果有疑问可以在评论区留言。

[longSwordMan]

在昨天我们讲完了原题，那今天想与大家分享一下这类题型的变体：
1. 给定一个数列，例如 [−2, 1, −3, 4, −1, 2, 1, −5, 4] ， 求一个连续的数列使得数列内的元素乘积最大。

[longSwordMan]

第一印象相信大家都会感到，很相似。但我们思考一下终究有什么不同，唯一的不同就是，可能负负得正。那么，我们不仅要记录正向的最大，还要记录负向的最大。方便起见，我们把最大负向值表做最小值。

[longSwordMan]

所以，这题动态规划的关系就是：目前角标的最大乘积是，如果该数为负，则和前一位数结尾的最小值相乘，若果为正，则和前一位数结尾的最大值相乘；目前角标的最小乘积是，如果该数为负，则和前一位数结尾的最大值相乘，若果为负，则和前一位数结尾的最小值相乘。

[longSwordMan]

我们再看变体 2

2. 有一个数列，代表牌的顺序，在 21 点游戏中能得到的最高点数（最接近，且小于 21 点）

参考一下我们前题题的做法，如果向后找爆点了（大于 21 ），则把数组的最左端元素删去，直到小于 21 。由于牌点数大于 21 点的期望是 3 张牌，所以时间复杂度上仍然是 O （ N ）