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

好像是leetcode 336？ https://leetcode.com/problems/palindrome-pairs/

1.1暴力
     本题可以想到暴力做法，我们枚举每一对字符串的组合，暴力判断它们是否能够构成回文串即可。时间复杂度 O(n^2\times m)O(n^2 ×m)，其中 n是字符串的数量，m是字符串的平均长度。时间复杂度并不理想，考虑进行优化。

1.2  枚举前缀和后缀
   假设存在两个字符串 s1 和 s2，s1+s2是一个回文串，记这两个字符串的长度分别为 len_1和 len_2，我们分三种情况进行讨论：
1,len 1=len 2，这种情况下 s_1 是 s_2的翻转。
2,len1>len2，这种情况可以将是s1拆成左右两部分t_1和 t_2，其中 t_1 是 s2的翻转，t_2是一个回文串。
也就是说，我们要枚举字符串 k 的每一个前缀和后缀，判断其是否为回文串。如果是回文串，我们就查询其剩余部分的翻转是否在给定的字符串序列中出现即可。
注意到空串也是回文串，所以我们可以将 k 拆解为 k+∅ 或 ∅+k，这样我们就能将情况 1 也解释为特殊的情况 2 或情况 3。
而要实现这些操作，我们只需要设计一个能够在一系列字符串中查询「某个字符串的子串的翻转」是否存在的数据结构，有两种实现方法：
我们可以使用字典树存储所有的字符串。在进行查询时，我们将待查询串的子串逆序地在字典树上进行遍历，即可判断其是否存在。
我们可以使用哈希表存储所有字符串的翻转串。在进行查询时，我们判断带查询串的子串是否在哈希表中出现，就等价于判断了其翻转是否存在。
时间复杂度：O(n*m^2) )，其中 n是字符串的数量，m 是字符串的平均长度。对于每一个字符串，我们需要 O(m^2)地判断其所有前缀与后缀是否是回文串，并O(m^2)地寻找其所有前缀与后缀是否在给定的字符串序列中出现。
空间复杂度：O(n×m)，其中 n 是字符串的数量，m 是字符串的平均长度。为字典树的空间开销。

1.3字典树 + Manacher
注意到方法一中，对于每一个字符串 k，我们需要 O(m^2)地判断 k 的所有前缀与后缀是否是回文串，还需要 O(m^2) 地判断 k 的所有前缀与后缀是否在给定字符串序列中出现。我们可以优化这两部分的时间复杂度。
对于判断其所有前缀与后缀是否是回文串：
利用 Manacher 算法，可以线性地处理出每一个前后缀是否是回文串。
对于判断其所有前缀与后缀是否在给定的字符串序列中出现：
对于给定的字符串序列，分别正向与反向建立字典树，利用正向建立的字典树验证 k 的后缀的翻转，利用反向建立的字典树验证 k 的前缀的翻转。

感谢楼主！先收藏下

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。期间仅可乘坐公交车。求出最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

！谢谢楼主！

插眼插眼，马上要onsite了。虽然是面的前端，但是巨硬貌似是无差别出题

本题是一个无向图的搜索问题，但是题意很容易把我们弄混，可能一开始以为要将站台作为图上的点，其实应该将车作为点，如果两辆车的路线之间存在公共站点，那么就视作这两个点之间存在连线；

因为需要绕弯，所以，同时用到了多个映射用于保存车和站台、站台和车、车和车之间的关系。

已经将问题转化为图的搜索问题了，那就很好做了，常规的做法就是将点与点的关系存在映射之中，建立邻接表，然后搜索映射。

非常感谢！特别有用的信息，赶紧把者2题做一下

大佬好人一生平安
友情提示大佬保护好个人信息以免被有心之人利用

吃葡萄问题

有三种葡萄，每种分别有 `a, b, c` 颗，现在有三个人，第一个人只吃第一种和第二种葡萄，第二个人只吃第二种和第三种葡萄，第三个人只吃第一种和第三种葡萄。
现在给你输入 `a, b, c` 三个值，请你适当安排，让三个人吃完所有的葡萄，算法返回吃的最多的人最少要吃多少颗葡萄。