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

YankeeDoodle 发表于 2021-5-6 10:55
最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在 ...

如果我们使用暴力解法，代码大概是这样的：
for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案
思路很直接，但是显然，这个算法的复杂度肯定大于 O(N^2) 了，不好。

滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

感谢楼主！看的时候稍稍有些费力，希望大家在看题的时候能尽量把lc题号贴出来方便后人。我先来
益灞跋厮，柳乞儿，奇瘤

YankeeDoodle 发表于 2021-5-3 22:04
丢鸡蛋问题
如果你有2颗鸡蛋，和一栋36层高的楼，现在你想知道在哪一层楼之下，鸡蛋不会被摔碎，应该如何 ...

如果大家仔细想想这个问题，如果是严格按照题目，这题不要解啊， 1 楼就碎了啊。。。鸡蛋啊