Zappos OA 算法题

想问下楼主第一题的time complexity，  我的想法总是你n^3....

liujzhi2 发表于 2016-2-10 04:45
想问下楼主第一题的time complexity，  我的想法总是你n^3....

第一题是最难的
我用n^3做的 快的方法没想出来

感觉只能这样做啊， 要不然就要dfs。。更慢。。。

大成若缺 发表于 2016-2-10 01:45
我想了一下 是正数

好的哈 如果全是正数的话 就简单很多~

hyj143 发表于 2016-2-10 08:02
好的哈 如果全是正数的话 就简单很多~

是正数 但是我可能没有用最优解

第三题如果字符串是 ceeb 结果是多少

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

jedihy 发表于 2016-2-10 09:05
最快O(n)可以做，但是太难写。
O(n^2)可以很简单的写出来，就是扫描数组的时候，把那个字符当成回文的中 ...

对， 这是manchester算法
但是这种比n^3还要慢 不知道为什么

lc有相似的题目longest palindrome substring，n^2的明显比n^3快很多,n^3用python根本没法ac

补充内容 (2016-2-10 09:22):
求大米

jedihy 发表于 2016-2-10 09:21
lc有相似的题目longest palindrome substring，n^2的明显比n^3快很多,n^3用python根本没法ac

补充内容 (20 ...

好的，你把O(n)的算法讲出来，我给你大米