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

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

共勉！



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

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

举一个自己comment代码，加深理解的例子：
在无评论版 3.2 binary search ST.java中，在无Comment的代码后添加自己的理解，不会让自己一目十行的看，而是进行了思考。会发现int i = rank(key)这里的i会出现异常，所以要加入i < n这样的约束；也会发现keys[i].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. 
    
15.         int lo = 0, hi = n-1;
    
16.         while (lo <= hi) {
    
17.             int mid = lo + (hi - lo) / 2;
    
18.             int cmp = key.compareTo(keys[mid]);
    
19.             if      (cmp < 0) hi = mid - 1;
    
20.             else if (cmp > 0) lo = mid + 1;
    
21.             else return mid;
    
22.         }
    
23.         return lo;
    
24.     }

复制代码

举一个小例子，算法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. }

复制代码

2017.7.13新增：新增 无注释 Non-Comment 版本无注释版，方便复习。复习时，自己主动给关键部分写注释，再对照原来的注释，看看是否真正理解。
2017.7.13新增：新增 的批量去除Java注释的工具批量删除Java注释工具

支持lz！！

谢谢楼主，用来刷题的好东西，收了！

davidlee8086 发表于 2017-7-12 03:55
支持lz！！

谢谢！加油！

老爷子的这门课是门很不错的入门课，即讲了算法的部分，又帮助你学Java，我记得当时的assignment也都很有意思

pyemma1991 发表于 2017-7-13 14:26
老爷子的这门课是门很不错的入门课，即讲了算法的部分，又帮助你学Java，我记得当时的assignment也都很有意 ...

是哒，assignment很有实际应用的赶脚