寄托家园留学论坛 › 论坛 › 寄托专业学术申请版 › 计算机科学CS版 › 刷题咯

返回列表

楼主: bibaboo0

[编程天地] 刷题咯 [复制链接]

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

16楼

发表于 2017-1-31 04:52:06 |只看该作者

280. Wiggle Sort 难度medium 耗时：未计时
一开始采用先排序后交换的方法。O(nlogn)
后来看答案发现有O(n)的方法，非常好写，直接比较交换奇数项和偶数项。
python逆序遍历：range(n-1,-1,-1)

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

17楼

发表于 2017-1-31 05:30:01 |只看该作者

259. 3Sum Smaller 难度medium 耗时50分钟
这是一个3sum的问题。看了一个关于k-sum问题的帖子http://blog.csdn.net/whuwangyi/article/details/14104589
先讲3sum中提取一个数，然后对该数后面的数做一个2sum。中间由于是smaller，不同于传统的等号2sum问题，判断条件错了好几次，最后才ac。

【2025FALL】全站祈福已开放~~来领祈福章，求offer得offer

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

18楼

发表于 2017-1-31 05:31:08 |只看该作者

发现一个挺不错的整理算法题的网站。
https://lefttree.gitbooks.io/lee ... um/3sumSmaller.html

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

19楼

发表于 2017-1-31 09:58:06 |只看该作者

本帖最后由 bibaboo0 于 2017-2-1 03:00 编辑

289. Game of Life 难度medium
python黑魔法之ngbs = sum( 1 for a in xrange(max(0,i-1),min(i+1+1,m)) for b in xrange(max(0,j-1),min(j+1+1,n)) if (a!=i or b!=j) and (board[a]==1 or board[a]==3))
int整数可以代表好几bit的信息。

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

20楼

发表于 2017-2-1 04:10:20 |只看该作者

本帖最后由 bibaboo0 于 2017-2-1 04:12 编辑

471. Encode String with Shortest Length 难度hard 耗时两小时以上
这是一道名副其实的hard题，看答案都看半天才懂。
algo:用到了递归，动态规划。python中动态规划是用dict纪录的而不是二维矩阵。
python: 学会了很多字符串处理技巧。还有list用＋号拼接。还有min函数可以穿一个key函数进去比较list元素：memo= min([s,ans]+multi, key=len)
这题花了很久，也学了很多。

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

21楼

发表于 2017-2-1 07:28:57 |只看该作者

246. Strobogrammatic Number 难度easy 耗时10分钟
easy题果然easy哈哈，直接秒了。python的dict真方便。python大法好。

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

22楼

发表于 2017-2-1 13:34:03 |只看该作者

351. Android Unlock Patterns 难度medium 耗时2小时
花了很久刷了一道很无聊的题。。一开始思路错了，没能理解（不经过其他数字）是什么意思。
也许实际工作中遇到的题就是这么无聊吧。。

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

23楼

发表于 2017-2-2 06:22:31 |只看该作者

465. Optimal Account Balancing 难度hard 耗时2小时
这题真刷的我要跪了。一开始用naive的方法做，结果发现错了。后来才发现应该bfs。中间有各种小问题，总是得不到正确答案，比如什么时候需要深度拷贝再遍历，什么时候需要删掉一个元素－－遍历－－添加回这个元素（其实就是回溯）。很多细节问题。总算ac了。

使用道具举报

bibaboo0
UID: 3565929

中级会员

Rank: 4

声望: 50
寄托币: 779
注册时间: 2014-10-1
精华: 0
帖子: 189

24楼

发表于 2017-2-3 00:44:20 |只看该作者

406. Queue Reconstruction by Height 难度medium 耗时1小时
本来用dfs做，超时了。后来看答案发现一个特别取巧的方法。但是这个方法我临时想肯定是想不到的。。
总之学会了python的lambda function。que = sorted(people,key=lambda x: (-x[0],x[1]))

使用道具举报