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


一亩三分地论坛

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

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

[Leetcode] 重点算法-刷题必备Algorithms 4th edition

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

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

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

x
本帖最后由 mxc19912008 于 2017-7-12 05:46 编辑

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

Algorithms apk

Algorithms apk


共勉!



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

评分

4

查看全部评分

Xin1993 发表于 2017-7-12 04:16:42 | 显示全部楼层
关注一亩三分地微博:
Warald
我也是转专业,可以加一下微信交流一下吗,我的微信是893557669
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-12 04:27:25 | 显示全部楼层
Xin1993 发表于 2017-7-12 04:16
我也是转专业,可以加一下微信交流一下吗,我的微信是893557669

已加啦!
回复 支持 反对

使用道具 举报

wrxys 发表于 2017-7-12 18:16:10 | 显示全部楼层
谢谢楼主,用来刷题的好东西,收了!
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-13 05:35:09 | 显示全部楼层

谢谢!加油!
回复 支持 反对

使用道具 举报

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

举一个小例子,算法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. }
复制代码
回复 支持 反对

使用道具 举报

pyemma1991 发表于 2017-7-13 14:26:02 | 显示全部楼层
老爷子的这门课是门很不错的入门课,即讲了算法的部分,又帮助你学Java,我记得当时的assignment也都很有意思
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-13 21:51:56 | 显示全部楼层
pyemma1991 发表于 2017-7-13 14:26
老爷子的这门课是门很不错的入门课,即讲了算法的部分,又帮助你学Java,我记得当时的assignment也都很有意 ...

是哒,assignment很有实际应用的赶脚
回复 支持 反对

使用道具 举报

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

使用道具 举报

lingyics 发表于 2017-7-14 03:42:59 | 显示全部楼层
这个很棒,谢谢楼主
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 6 天前 | 显示全部楼层
举一个自己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.     }
复制代码
回复 支持 反对

使用道具 举报

eudemon 发表于 5 天前 | 显示全部楼层
很不错。不过有ios 的版本不?
回复 支持 反对

使用道具 举报

newgod2500 发表于 5 天前 | 显示全部楼层
谢谢楼主。Github已星+大米已加!iOS 用户期待一下
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 5 天前 | 显示全部楼层
newgod2500 发表于 2017-7-17 10:04
谢谢楼主。Github已星+大米已加!iOS 用户期待一下

感谢感谢!iOS自学中,等iOS出来我私信你哈!
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 5 天前 | 显示全部楼层
eudemon 发表于 2017-7-17 09:24
很不错。不过有ios 的版本不?

感谢支持!iOS还在自学中,等iOS出来我私信你哈!
回复 支持 反对

使用道具 举报

loading2016 发表于 6 分钟前 | 显示全部楼层
楼主您好!同转专业,可以加微信交流么..谢谢!   loading150
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-22 19:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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