微软近期高频面试题分享 + 分析（四）

最近来微软面试的小朋友通过概率实在太低了，代码老是写不对，我们组已经十连拒了，不得不感叹，现在出的面试题越来越难了，我决定还是上来地里透透题，说点最近我们组面试常考高频题和解析（毕竟岗位机会也不能都让三锅霸占了对不）。招人艰难，看微软机会的小伙伴，也欢迎LinkedIn勾搭：https://www.linkedin.com/in/andy-yongjian-deng-212977200/

注意打招呼的时候备注一下，方便识别友军，hhhh。

带娃有压力，尽量保持一周两更，大家海涵。

往期链接：
微软近期高频面试题分享 + 分析（一）

微软近期高频面试题分享 + 分析（二）

微软近期高频面试题分享 + 分析（三）

逃脱阻碍者

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget, ytarget] 。地图上有一些阻碍者，以数组 ghosts 给出，第 i 个阻碍者从 ghosts[i] = [xi, yi] 出发。所有输入均为整数坐标 。每一回合，你和阻碍者们可以同时向东，西，南，北四个方向移动，每次可以移动到距离原位置 1 个单位的新位置。当然，也可以选择不动 。所有动作同时发生。

如果你可以在任何阻碍者抓住你 之前 到达目的地（阻碍者可以采取任意行动方式），则被视为逃脱成功。如果你和阻碍者同时到达了一个位置（包括目的地）都不算是逃脱成功。

只有在你有可能成功逃脱时，输出 true ；否则，输出 false 。

lc题号：奇爸救，肆意流，伞霸凌

分割等和子集

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。
示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

YankeeDoodle 发表于 2021-5-11 10:51
逃脱阻碍者

你在进行一个简化版的吃豆人游戏。你从 [0, 0] 点开始出发，你的目的地是 target = [xtarget ...

曼哈顿距离【通过】
每个操作执行奇数次等于执行一次，执行偶数次等于没有执行，所以我们只需要考虑i操作是否执行就好。


思想
曼哈顿距离是指网格中从 A 点到 B 点的距离，计算公式为 dist(A, B) = abs(A.x - B.x) + abs(A.y - B.y)。
假设我们的起点是 S，阻碍者的起点是 G，目的地是 T。如果我们与阻碍者在 X 点相遇，则有 dist(G, X) <= dist(S, X)，表示阻碍者要么和我们同时到达 X 点，要么比我们更早到 X 点。
如果阻碍者从 G 出发先到达 X 再到达 T，与直接到达 T 相比有 dist(G, T) <= dist(G, X) + dist(X, T) <= dist(S, X) + dist(X, T)。因为三角形两边之和大于第三边，所以 dist(G, T) <= dist(G, X) + dist(X, T) 一定成立。
以上分析表明，让阻碍者直接到达目的地 T，与让阻碍者先到某个点 X 再到达目的地 T 的结果是一样的。如果阻碍者直接到达目的地会阻碍我们，那么阻碍者也一定会先于我们到达某一点 X ，在此与我们相遇；如果阻碍者直接到达目的地不会阻碍我们，那么阻碍者无论怎么走也无法阻碍我们。
因此，这个问题可以简化为我们与所有阻碍者都在最短时间内直接到达目的地是否会与阻碍者相遇。
画个抽象的示意图来解释下为神马直接比较距离即可 A表示起点 B表示鬼魂�的位置 目的地为C 如果鬼魂�要在中间拦截 AC上必须有一点D 使得AD = DB 通过三角不等式 AC = AD + DC = DB + DC >= BC 如果鬼魂可以拦截到 那么鬼魂�最好的做法就是在终点等着 而不是去中间拦截 上面假设选择的是最短路径 乱走的话 相信鬼魂�会笑的更开心


算法
计算我们到目的地的曼哈顿距离是否小于所有阻碍者到达目的地的曼哈顿距离。

微软的题目这么难啊……哭了

mark，谢谢分享:)

mark 一下，谢谢楼主

YankeeDoodle 发表于 2021-05-12 20:01:14
分割等和子集

给你一个 只包含正整数 的 非空 数组nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

在微软做过一些面试，并没有用过题库。这个完全看组。本科intern面试斐波那契都没写好也让过了，不过入职以后表现还不错

马克一下谢谢

第一步要明确两点，「状态」和「选择」。
状态就是「背包的容量」和「可选择的物品」，选择就是「装进背包」或者「不装进背包」。

第二步要明确 dp 数组的定义
按照背包问题的套路，可以给出如下定义：
dp[i][j] = x 表示，对于前 i 个物品，当前背包的容量为 j 时，若 x 为 true，则说明可以恰好将背包装满，若 x 为 false，则说明不能恰好将背包装满。
比如说，如果 dp[4][9] = true，其含义为：对于容量为 9 的背包，若只是用前 4 个物品，可以有一种方法把背包恰好装满。
或者说对于本题，含义是对于给定的集合中，若只对前 4 个数字进行选择，存在一个子集的和可以恰好凑出 9。
根据这个定义，我们想求的最终答案就是 dp[N][sum/2]，base case 就是 dp[..][0] = true 和 dp[0][..] = false，因为背包没有空间的时候，就相当于装满了，而当没有物品可选择的时候，肯定没办法装满背包。

第三步，根据「选择」，思考状态转移的逻辑。
回想刚才的 dp 数组含义，可以根据「选择」对 dp[i][j] 得到以下状态转移：
如果不把 nums[i] 算入子集，或者说你不把这第 i 个物品装入背包，那么是否能够恰好装满背包，取决于上一个状态 dp[i-1][j]，继承之前的结果。
如果把 nums[i] 算入子集，或者说你把这第 i 个物品装入了背包，那么是否能够恰好装满背包，取决于状态 dp[i-1][j-nums[i-1]]。
首先，由于 i 是从 1 开始的，而数组索引是从 0 开始的，所以第 i 个物品的重量应该是 nums[i-1]，这一点不要搞混。
dp[i - 1][j-nums[i-1]] 也很好理解：你如果装了第 i 个物品，就要看背包的剩余重量 j - nums[i-1] 限制下是否能够被恰好装满。
换句话说，如果 j - nums[i-1] 的重量可以被恰好装满，那么只要把第 i 个物品装进去，也可恰好装满 j 的重量；否则的话，重量 j 肯定是装不满的。
最后一步，把伪码翻译成代码，处理一些边界情况。