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

好人好人好人好人

谢谢楼主，不过楼主不需要匿名吗？

这题也太难了吧...

插个眼 谢谢楼主

给你一个字符串 s，找到 s 中最长的回文子串。


示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：
输入：s = "cbbd"
输出："bb"

对于这个问题，我们首先应该思考的是，给一个字符串 s，如何在 s 中找到一个回文子串？
有一个很有趣的思路：既然回文串是一个正着反着读都一样的字符串，那么如果我们把 s 反转，称为 s'，然后在 s 和 s' 中寻找最长公共子串，这样应该就能找到最长回文子串。
比如说字符串 abacd，反过来是 dcaba，它的最长公共子串是 aba，也就是最长回文子串。
但是这个思路是错误的，比如说字符串 aacxycaa，反转之后是 aacyxcaa，最长公共子串是 aac，但是最长回文子串应该是 aa。
虽然这个思路不正确，但是这种把问题转化为其他形式的思考方式是非常值得提倡的。
下面，就来说一下正确的思路，如何使用双指针。
寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串。对于最长回文子串，就是这个意思：
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是呢，我们刚才也说了，回文串的长度可能是奇数也可能是偶数，如果是 abba这种情况，没有一个中心字符，上面的算法就没辙了。所以我们可以修改一下：
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

楼主好人！谢谢帮助国人

赞！感谢楼主！！！

对于这个问题，我们首先应该思考的是，给一个字符串 s，如何在 s 中找到一个回文子串？
有一个很有趣的思路：既然回文串是一个正着反着读都一样的字符串，那么如果我们把 s 反转，称为 s'，然后在 s 和 s' 中寻找最长公共子串，这样应该就能找到最长回文子串。
比如说字符串 abacd，反过来是 dcaba，它的最长公共子串是 aba，也就是最长回文子串。
但是这个思路是错误的，比如说字符串 aacxycaa，反转之后是 aacyxcaa，最长公共子串是 aac，但是最长回文子串应该是 aa。
虽然这个思路不正确，但是这种把问题转化为其他形式的思考方式是非常值得提倡的。
下面，就来说一下正确的思路，如何使用双指针。
寻找回文串的问题核心思想是：从中间开始向两边扩散来判断回文串。对于最长回文子串，就是这个意思：
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    更新答案

但是呢，我们刚才也说了，回文串的长度可能是奇数也可能是偶数，如果是 abba这种情况，没有一个中心字符，上面的算法就没辙了。所以我们可以修改一下：
for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

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

因为需要绕弯，所

简单想了一下，以站台作为对象也可以啊
首先建立一个表，统计每个站台有哪些车通过，复杂度O（N）
然后其实就是一个宽度搜索的问题，对于每一个点，“相邻”站台就是遍历这个站台换一次车能到的点，其中过滤掉已经访问过的站台并且存储换成次数
结束条件要么target到达，要么所有点都访问到没有新的点