一亩三分地论坛

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

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

[Leetcode] leetcode提交算法性能较低怎么办?

[复制链接] |试试Instant~ |关注本帖
英伦十六世纪 发表于 2016-8-5 17:00:17 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
最近lz开始刷题,很多题目的提交结果只能击败小于10%的提交。心里略慌,查看了网上博客的解法,很多算法的性能也很低。感觉这样刷题没有太大效果,想问下地里各位有什么解决的方法?
wujingzhishui 发表于 2016-8-5 20:52:25 | 显示全部楼层
正在刷题的路过下 一开始都这样 写多了 就会首先想好的solution了 当然你光刷ez的话确实提高不大
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-8-6 02:02:11 | 显示全部楼层
大部分情况下不TLE能通过的解都是可以接受的。。一般brute force过不了。。然后你得看你的run time在哪个mode,有时只beat10%是因为大部分人都在你那个mode。。
回复 支持 反对

使用道具 举报

zhuyinghua1203 发表于 2016-8-6 03:30:17 | 显示全部楼层
In such case, why not learn from those posts that have top 10% speed?

BTW, people post there solutions on leetcode
回复 支持 反对

使用道具 举报

sheepmiemies 发表于 2016-8-6 05:43:11 | 显示全部楼层
本帖最后由 sheepmiemies 于 2016-8-6 06:46 编辑

既然慢就多思考优化呀。。。通常有以下思路 (临时总结,仅供参考):
*1. 找性能瓶颈。比如排序是nlogn最耗时,有没有办法不排序直接得到答案?比如two sum,不排序,直接上hashmap
2. 优化代码。有挺多种情况
(1) 有没有多余的操作?比如不必要的copy
(2) 递归能不能换迭代?在递归的overhead比较高的时候,提升会明显一些
(3) 有没有可能剪枝避免重复操作?个人觉得,DP的memorization有一点点剪枝的感觉,然后就是比如combination sum那种backtracking的题,并不需要全部solution都试一遍
(*4) 巧妙的操作或者数据结构。比如bit operation,或者用数组代替hashmap,因为hashmap(比如c++中)多少还是有overhead的
*3. 找新的算法。去看书,搜blog或者看论坛discussion。

国内很多blog只要解出来就贴,感觉比较浮躁,当然也有好的。可以选择直接看leetcode的discussion啊。。。带星号的表示可能稍微难一点,但是多加练习就不难了。
然后大概时间能在大多数人在的范围就可以了,中等或者中等偏上。论坛有些神人解法很叼,可以参考,但是不适合面试的时候用(非大牛的话),除非你就是研究算法的。。。。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 英伦十六世纪 发表于 2016-8-6 08:10:11 | 显示全部楼层
zpinthehouse 发表于 2016-8-6 02:02
大部分情况下不TLE能通过的解都是可以接受的。。一般brute force过不了。。然后你得看你的run time在哪个mo ...

run time mode是指时间复杂度的形式吗? nlogn n^2?
回复 支持 反对

使用道具 举报

 楼主| 英伦十六世纪 发表于 2016-8-6 08:11:08 | 显示全部楼层
zhuyinghua1203 发表于 2016-8-6 03:30
In such case, why not learn from those posts that have top 10% speed?

BTW, people post there solu ...

THX, I will pay attention to it then.
回复 支持 反对

使用道具 举报

 楼主| 英伦十六世纪 发表于 2016-8-6 08:11:58 | 显示全部楼层
sheepmiemies 发表于 2016-8-6 05:43
既然慢就多思考优化呀。。。通常有以下思路 (临时总结,仅供参考):
*1. 找性能瓶颈。比如排序是nlogn最耗 ...

受益匪浅,太感谢了!
回复 支持 反对

使用道具 举报

mming1993 发表于 2016-8-6 08:50:31 | 显示全部楼层
AC就很好了,再考虑一些可以想到的改进,多看看discussion,不用刻意追求一些太难的算法,很多算法确实很快但是思维都是反人类的。。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-8-6 12:34:22 | 显示全部楼层
英伦十六世纪 发表于 2016-8-6 08:10
run time mode是指时间复杂度的形式吗? nlogn n^2?

就是leetcode不是所有提交的运行时间画成柱状图了么。。不同复杂度的做法一般在不同的峰值周围。。你看下你在哪个峰值就能知道是不是有更简单的方法。。因为跟你复杂度相同的方法不算在你beat的哪个百分比里面。。

其实你可以看看discuss里排名靠前的答案你就知道有什么更好的方法了,不过我觉得只要你的方法能Accepted,复杂度都满足最基本的要求了。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 02:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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