2017.8.5 Twitter OA test 4

1,3 题是一样的

第二题也超级简单
就是把两个array的odd/even index的输加起来比一下

感谢楼主，同抽到test4，麻烦问一下第一题是sql吗？

wxgymsfd 发表于 2017-8-13 08:03
感谢楼主，同抽到test4，麻烦问一下第一题是sql吗？

我没有sql，都是算法题

面壁者 发表于 2017-8-13 09:06
我没有sql，都是算法题

多谢楼主！祝offer多多！

请问下第三题dp做法怎么做的呢。我只会暴力。就是从左到右遍历一遍。判断以这个字母为中心向两边扩展能有多少回文字符串。时间复杂度是n平方级别的。

sterftnmi 发表于 2017-8-29 04:13
请问下第三题dp做法怎么做的呢。我只会暴力。就是从左到右遍历一遍。判断以这个字母为中心向两边扩展能有多 ...

遍历思路使用马拉车算法做预处理时间复杂度可以降到O（nlogn），DP的话给你一个思路，用dp[i][j] = true 表示从i到j的子串为回文，递推条件为这个字符串去掉头元素和尾元素为回文，且头元素等于尾元素，即的dp[i+1][i-1] = true && s.charAt(i) == s.charAt(j)。当然还有可能有其他的思路。

Crazy Dogee 发表于 2017-8-29 04:38
遍历思路使用马拉车算法做预处理时间复杂度可以降到O（nlogn），DP的话给你一个思路，用dp[j] = true 表 ...

请问怎么用马拉车算法做预处理。 查了一下，可以帮助求最长的palindrome， 可是没想出来怎么用来求palindrome的个数。多谢

多谢楼主的分享！

请问lz有后续吗

FruitSon 发表于 2017-10-14 02:11
请问lz有后续吗

twitter后来来学校约了on campus，然后我withdraw没面了