一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 494|回复: 13
收起左侧

[算法题] LeetCode Shortest Palindrome

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
zkb2008116 发表于 2015-7-29 02:28:20 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽
zhuli19901106 发表于 2015-7-29 03:08:25 | 显示全部楼层
这俩都是暴力算法,所以如果第二个能AC,估计也是几百甚至上千毫秒吧?
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 03:08:53 | 显示全部楼层
这题有两个O(N)算法,楼主琢磨一下?其中一个思想略难,实现简单,一个思想简单,实现麻烦。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 03:11:52 | 显示全部楼层
一堆aaaaaaaa...aaaaaaaaaaaaaa是字符串算法的常见bad case,更常见的是这个aaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaab
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zkb2008116 发表于 2015-7-29 03:21:30 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 03:38:51 | 显示全部楼层
zkb2008116 发表于 2015-7-29 03:21
问题是为什么第一种算法就超时,第二种就AC啊?

第一种算法时间大概是第二种的两倍,你注意代码中的下标从哪儿开始。
暴力算法就别纠结这些了,反正写这个是通过不了面试的。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 03:47:01 | 显示全部楼层
超时不代表运行时间无穷大,比如运行时限制在2000ms,那么你1999ms也能AC,2002ms就超时了。这俩暴力算法道理是一样的,所以差别只在于常系数。
常系数这东西,快的和慢的可以差到数百倍之多,对运行时间有显著影响的。所以同复杂度的算法,写法不好的超时,写法好的通过很正常。
回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zkb2008116 发表于 2015-7-29 04:22:37 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 05:34:09 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-29 05:49 编辑
zkb2008116 发表于 2015-7-29 04:22
第一个是找到末尾往中间走,第二个是找到中间往两边走,不是一样的么。。

你怎么非关心这个。。你的关注点偏了,这题有更低复杂度的解,这个暴力解也就没有关注的价值。建议你了解下这俩概念:复杂度、程序调优
leetcode的关注点基本都在复杂度上,所以不要纠结任何代码细节,那都是程序调优的范畴。
复杂度首先要优化,然后再考虑代码细节的事。如果给个长度100万的字符串,这两个程序可以跑到天荒地老,没一个能过的。
建议别纠结这个,琢磨出O(N)的解法,你就不需要这俩了。

回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zkb2008116 发表于 2015-7-29 05:48:43 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 05:50:04 | 显示全部楼层
zkb2008116 发表于 2015-7-29 05:48
就算是dp找 palindrome 这一步也得要O(N^2)吧, O(N)暂时还做不出来。。。。

可以的,当然不骗你,网上题解也很多啊。
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-7-29 05:55:12 | 显示全部楼层
本帖最后由 zhuli19901106 于 2015-7-29 06:01 编辑
zkb2008116 发表于 2015-7-29 05:48
就算是dp找 palindrome 这一步也得要O(N^2)吧, O(N)暂时还做不出来。。。。

这些hard难度的题,每题都可以用暴力方法AC掉,然而那样对自己并没有提高
要尽力找出最优解,这个过程本身就是学习啊,我做这题时,也是琢磨了将近半天,到了半夜才突然有想法,然后把O(N)的算法写出来了。

你可以先试着想出 Longest Palindromic Substring 和 Implement strStr()这两题,这两题的O(N)算法都搞懂了,这题也就没问题了。

回复 支持 反对

使用道具 举报

头像被屏蔽
 楼主| zkb2008116 发表于 2015-8-6 22:51:45 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

zhuli19901106 发表于 2015-8-6 23:06:59 | 显示全部楼层

对啊,时间空间都是O(N)。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 20:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表