coursera OA面经 8.31

WTYJack 发表于 2016-9-2 10:13
我觉得不需要，只要遍历一次，不停更新最大子串的头和长度就行了，比如遇到字母比head小的就加个长度，比 ...

好像这样是更优化了！谢谢提醒！

WTYJack 发表于 2016-9-2 10:13
我觉得不需要，只要遍历一次，不停更新最大子串的头和长度就行了，比如遇到字母比head小的就加个长度，比 ...

或许只要确认head的位置就可以了，因为排在最后的应该永远是以最优head开头最长的substring吧

Crystal_yy 发表于 2016-9-2 10:49
或许只要确认head的位置就可以了，因为排在最后的应该永远是以最优head开头最长的substring吧

赞！这样代码简单好多，谢谢指教！

abczabczcbazbaczcab，这样的话应该答案从zcba……（到底），要记录之前最优head（z）的位置，如果遇到同是最优head，two pointer比较z后面的值来更新最优head，字典顺序不是比长度吧

感谢分享！

WTYJack 发表于 2016-9-2 10:13
我觉得不需要，只要遍历一次，不停更新最大子串的头和长度就行了，比如遇到字母比head小的就加个长度，比 ...

这是个O(n^2)的做法吧

补充内容 (2016-9-4 07:06):
我的做法和你一样，这是O(n^2)时间O(1)空间的，应该还有O(n)时间的做法

liuqi627 发表于 2016-9-4 07:05
这是个O(n^2)的做法吧

补充内容 (2016-9-4 07:06):

是O(N)呀，每个元素只遍历一次，比较完substring就可以根据结果直接把指针往后推了

WTYJack 发表于 2016-9-4 09:02
是O(N)呀，每个元素只遍历一次，比较完substring就可以根据结果直接把指针往后推了

这个比较substring也是O(n)的呀

liuqi627 发表于 2016-9-4 10:15
这个比较substring也是O(n)的呀

就是可以根据比较的结果，比方说在第k位上区分出大小后，把i直接移动到k，因为i到k和之间的子串已经判断过是和最大的子串的k-i位相等了，有点儿two pointers的感觉

WTYJack 发表于 2016-9-4 09:02
是O(N)呀，每个元素只遍历一次，比较完substring就可以根据结果直接把指针往后推了

你们有没有考虑出现multiple的z的情况呢  zfkzfkzkfzkfzfkzz 比如这种循环的 就会有很多candidate子串..