推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

[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注释的工具

补充内容 (2017-8-20 06:22):
最新版本见www.riversmall.com

评分

7

查看全部评分

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

使用道具 举报

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

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

使用道具 举报

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

举一个小例子,算法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(maxDepth(root.left),  maxDepth(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 发表于 2017-7-16 00:21:07 | 显示全部楼层
举一个自己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 发表于 2017-7-17 09:24:13 | 显示全部楼层
很不错。不过有ios 的版本不?
回复 支持 反对

使用道具 举报

newgod2500 发表于 2017-7-17 10:04:41 | 显示全部楼层
谢谢楼主。Github已星+大米已加!iOS 用户期待一下
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

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

使用道具 举报

xnliu67 发表于 2017-7-26 23:52:59 | 显示全部楼层
支持lz,但是举的小例子好像有点问题。。
leetcode那段的line 13
  1. return 1 + Math.max(root.left, root.right);
复制代码
应该改为
  1. return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
复制代码
回复 支持 反对

使用道具 举报

 楼主| mxc19912008 发表于 2017-7-31 03:04:14 | 显示全部楼层
本帖最后由 mxc19912008 于 2017-7-31 03:05 编辑
xnliu67 发表于 2017-7-26 23:52
支持lz,但是举的小例子好像有点问题。。
leetcode那段的line 13应该改为

感谢回复,最近有些忙。你说的是对的,递归算法忘写了method名字,已改,谢谢提醒!
回复 支持 反对

使用道具 举报

头像被屏蔽
carlvane110 发表于 2017-8-2 04:30:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复 支持 反对

使用道具 举报

codebyte 发表于 2017-8-8 20:51:31 | 显示全部楼层
安卓已root,提示安装失败,找不到签名证书,请尝试重新安装.  可能是什么原因呢? 有空自己编译apk再试试,谢谢楼主分享!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-22 13:37

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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