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

解题思路见下图


这道题的数学解法太秀了，简单说下我的理解：
思路及算法
预备知识：贝祖定理
我们认为，每次操作只会让桶里的水总量增加 x，增加 y，减少 x，或者减少 y。
你可能认为这有问题：如果往一个不满的桶里放水，或者把它排空呢？那变化量不就不是 x 或者 y 了吗？接下来我们来解释这一点：
首先要清楚，在题目所给的操作下，两个桶不可能同时有水且不满。因为观察所有题目中的操作，操作的结果都至少有一个桶是空的或者满的；
其次，对一个不满的桶加水是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于直接从初始状态给这个桶加满水；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态分别给两个桶加满；
再次，把一个不满的桶里面的水倒掉是没有意义的。因为如果另一个桶是空的，那么这个操作的结果等价于回到初始状态；而如果另一个桶是满的，那么这个操作的结果等价于从初始状态直接给另一个桶倒满。
因此，我们可以认为每次操作只会给水的总量带来 x 或者 y 的变化量。因此我们的目标可以改写成：找到一对整数 a, b使得
ax+by=z
而只要满足 z≤x+y，且这样的 a, b存在，那么我们的目标就是可以达成的。这是因为：
若 a≥0,b≥0，那么显然可以达成目标。
若a<0，那么可以进行以下操作：
往 y 壶倒水；
把 y 壶的水倒入 x 壶；
如果 y 壶不为空，那么 x 壶肯定是满的，把 x 壶倒空，然后再把 y 壶的水倒入 x 壶。
重复以上操作直至某一步时 x 壶进行了 a 次倒空操作，y 壶进行了 b 次倒水操作。
若b<0，方法同上，x 与 y 互换。
而贝祖定理告诉我们， ax+by=z 有解当且仅当 z 是 x, y的最大公约数的倍数。因此我们只需要找到 x, y的最大公约数并判断 z 是否是它的倍数即可。

你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。
我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

示例 1：
输入：clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
输出：3
解释：
我们选中 [0,2], [8,10], [1,9] 这三个片段。
然后，按下面的方案重制比赛片段：
将 [1,9] 再剪辑为 [1,2] + [2,8] + [8,9] 。
现在我们手上有 [0,2] + [2,8] + [8,10]，而这些涵盖了整场比赛 [0, 10]。

区间问题肯定按照区间的起点或者终点进行排序
这道题的思路是先按照起点升序排序，如果起点相同的话按照终点降序排序

为什么这样排序呢，主要考虑到这道题的以下两个特点：
1、要用若干短视频凑出完成视频[0, T]，至少得有一个短视频的起点是 0。
2、如果有几个短视频的起点都相同，那么一定应该选择那个最长（终点最大）的视频

这一条就是贪心的策略，因为题目让我们计算最少需要的短视频个数，如果起点相同，那肯定是越长越好，不要白不要，多出来了大不了剪辑掉嘛。
这样我们就可以确定，如果clips[0]是的起点是 0，那么clips[0]这个视频一定会被选择。
当我们确定clips[0]一定会被选择之后，就可以选出第二个会被选择的视频
我们会比较所有起点小于clips[0][1]的区间，根据贪心策略，它们中终点最大的那个区间就是第二个会被选中的视频
然后可以通过第二个视频区间贪心选择出第三个视频，以此类推，直到覆盖区间[0, T]，或者无法覆盖返回 -1。

堆箱子。给你一堆n个箱子，箱子宽 wi、深 di、高 hi。箱子不能翻转，将箱子堆起来时，下面箱子的宽度、高度和深度必须大于上面的箱子。实现一种方法，搭出最高的一堆箱子。箱堆的高度为每个箱子高度的总和。

动态规划 O(n^2)：
先将数组按照任何一条边降序重排，目的是为了降低里层循环次数。
使用dp一维数组记录以序号i箱子为顶时的最大高度。
计算每个箱子i时，在约束条件下，找到所有箱子k（i可以放在k的上面），并计算以k为顶最大高度与i的高度之和，取最大值。
所有箱子都操作完后，取dp数组元素的最大值。

回溯算法 O(n!)：
回溯就是 穷举+剪枝，下面的算法结果是正确的，但是大数据量时会超时。
排序
遍历，将各个箱子作为底
在剩下的箱子中，以2步骤的箱子为底和约束条件下，寻找合适的箱子，递归重复2，直到所有箱子。计算高度和。
在高度和中取最大值。

我咋看不见？积分不够？

同表示 看不见题目