【通知】7月22,工业界资深数据科学家教你破解各大公司面试!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 706|回复: 17
收起左侧

重点算法Algorithms 4th edition

[复制链接] |试试Instant~ |关注本帖
mxc19912008 发表于 2017-7-12 03:23:32 | 显示全部楼层 |阅读模式

[Coursera]Algorithms, Part I&II Princeton University #1 - 2017-07-11@Princeton

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
本帖最后由 mxc19912008 于 2017-7-12 09:41 编辑

LZ转专业,最近在上普林斯顿的算法公开课,同时想尝试刷题。可是发现即使做了每周的assignment,再去刷题手也很生,刷的很慢,忘得很快。

所以就想,algorithms 4th edition这本书有没有一些重点和典型的算法可以花心思研习,掌握了重点,再举一反三去刷题就会好一些。
然而全书955页,收录了386个算法,简直太多,对于我们转专业刷题准备明年summer intern的同学,既要学算法,又要刷题,还得准备projects,可能仔细的学完不太可能。
所以在该书的booksite上面整理出来44个coursera公开课Robert Sedgewick老爹爹仔细讲了的算法,有很细致的注释,放到了github上。
闲暇时间弄了一个mini的安卓app,收录了这44个算法,支持代码高亮,主题替换,代码放大等等,供随时复习。

Github链接:Github Key Algorithms
Mini安卓app下载链接:mini的安卓app
Alg-app.png
共勉!



补充内容 (2017-7-14 02:21):
2017.7.13新增:新增 无注释 Non-Comment 版本,方便复习。复习时,自己主动给关键部分写注释,再对照原来的注释,看看是否真正理解。
2017.7.13新增:新增 的批量去除Java注释的工具

评分

3

查看全部评分

2011051305 发表于 2017-7-12 04:15:01 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
刷题都是假的 这个才有用!!
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-12 04:25:05 | 显示全部楼层
关注一亩三分地微博:
Warald
2011051305 发表于 2017-7-12 04:15
刷题都是假的 这个才有用!!

哈哈哈,希望有些帮助!
回复 支持 反对

使用道具 举报

flyoasis 发表于 2017-7-12 04:50:07 | 显示全部楼层
LZ很赞啊。。。。真是有心人
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-12 05:24:29 | 显示全部楼层
flyoasis 发表于 2017-7-12 04:50
LZ很赞啊。。。。真是有心人

谢谢!实在是刷题刷的太痛苦了,哈哈
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-13 06:04:25 | 显示全部楼层
本帖最后由 mxc19912008 于 2017-7-13 08:33 编辑

举一个小例子,算法3.3 binary search tree中关于tree height的代码:
  1. /**
  2.      * Returns the height of the BST (for debugging).
  3.      *
  4.      * Return the height of the BST (a 1-node tree has height 0)
  5.      */
  6.     public int height() {
  7.         return height(root);
  8.     }
  9.     private int height(Node x) {
  10.         if (x == null) return -1;
  11.         return 1 + Math.max(height(x.left), height(x.right));
  12.     }
复制代码
在leetcode里面,104题 Maximum Depth of Binary Tree,记熟和理解以上code就可以bug-free的提交了
  1. /**
  2. * Definition for a binary tree node.
  3. * public class TreeNode {
  4. *     int val;
  5. *     TreeNode left;
  6. *     TreeNode right;
  7. *     TreeNode(int x) { val = x; }
  8. * }
  9. */
  10. public class Solution {
  11.     public int maxDepth(TreeNode root) {
  12.         if (root == null) return 0;
  13.         return 1 + Math.max(root.left, root.right);
  14.     }
  15. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 7 天前 | 显示全部楼层
2017.7.13新增:新增 无注释 Non-Comment 版本无注释版,方便复习。复习时,自己主动给关键部分写注释,再对照原来的注释,看看是否真正理解。
2017.7.13新增:新增 的批量去除Java注释的工具批量删除Java注释工具
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 5 天前 | 显示全部楼层
举一个自己comment代码,加深理解的例子:
无评论版 3.2 binary search ST.java中,在无Comment的代码后添加自己的理解,不会让自己一目十行的看,而是进行了思考。会发现int i = rank(key)这里的i会出现异常,所以要加入i < n这样的约束;也会发现keys.compareTo(key) == 0这样的约束。提升自己写出bug free代码的能力。
  1. public Value get(Key key) {
  2.         if (key == null) throw new IllegalArgumentException("argument to get() is null");
  3.         if (isEmpty()) return null;//不能用linkedlist里面 first==null的办法了
  4.         int i = rank(key); //rank是用到了binary search,不用再从头开始O(n)寻找了
  5.         if (i < n && keys[i].compareTo(key) == 0) return vals[i];//当只有1个key的时候(n=1,i=0),
  6.         //而且查找的key比这个key大,rank就会输出1,所以要用i < n来约束,这也是一个corner case.
  7.         //例如输入c,查找d的rank就会输出1.已经测试过。
  8.         //同时,这个key也可能不在array里,所以要进行keys[i].compareTo(key) == 0的比较
  9.         //(rank返回的是1.key在array里,key的位置;2.key不在array里,如果插入key,key的位置)
  10.         return null;
  11.     }
  12.     public int rank(Key key) {
  13.         if (key == null) throw new IllegalArgumentException("argument to rank() is null");

  14.         int lo = 0, hi = n-1;
  15.         while (lo <= hi) {
  16.             int mid = lo + (hi - lo) / 2;
  17.             int cmp = key.compareTo(keys[mid]);
  18.             if      (cmp < 0) hi = mid - 1;
  19.             else if (cmp > 0) lo = mid + 1;
  20.             else return mid;
  21.         }
  22.         return lo;
  23.     }
复制代码
回复 支持 反对

使用道具 举报

大赞!!!!感谢楼主的分享!
回复 支持 反对

使用道具 举报

凡尘忆梦 发表于 4 天前 | 显示全部楼层
谢谢楼主 好东西! 想问问有没有ios的 2333~
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 4 天前 | 显示全部楼层
请叫我热情老八 发表于 2017-7-16 11:54
大赞!!!!感谢楼主的分享!

感谢支持!
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 4 天前 | 显示全部楼层
凡尘忆梦 发表于 2017-7-17 17:21
谢谢楼主 好东西! 想问问有没有ios的 2333~

感谢支持!iOS还在自学中,放出来我就告诉你哈,感谢感谢!
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 4 天前 | 显示全部楼层
回复 支持 反对

使用道具 举报

XiaonanD 发表于 3 天前 | 显示全部楼层
谢谢楼主!赞!
回复 支持 反对

使用道具 举报

Licentiouschief 发表于 3 天前 | 显示全部楼层
謝謝樓主分享!!!
回复 支持 反对

使用道具 举报

cathyers 发表于 前天 04:39 | 显示全部楼层
很有用的东西,谢谢楼主分享
回复 支持 反对

使用道具 举报

jaygs0203 发表于 昨天 01:20 | 显示全部楼层
很好的文章,感谢楼主分享。
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-21 11:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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