LintCode

1.Rectangle Overlap

【consider exceptions】 1. x2太左了、太右了； 2. y2太上了、太下了

2.Longest Palindrome

【Hashset】

 一边装一边丢;
 count + 2 ;
 if(size != 0) ,count+1

3.Maximum Subtree

【设置全局变量TreeNode result 和Int max】

需要helper是因为原函数返回TreeNode，需要helper返回int，
为什么一定要返回int ？ 这就是helper最后不能直接返回max，
而是root.val + right + left 的原因----->
因为我们全部扫了一遍，即使这个root不是最优值，我们也在往上面扫，所以往上传的是当前root的sum。 

5.Decode Way

f[n]=f[n-1](条件s[n]!=0) + f[n-2](条件是s[n-1]与s[n]组成的数字在10-26之间)

6.K Closest Points

【PriorityQueue】

    globalOrigin = origin;
    PriorityQueue<Point> queue = new PriorityQueue<Point>(k, new Comparator<Point>() {
        public int compare(Point a, Point b) {
            //注意这里的globalorigin。如果用origin的话会报错：
            //local variable origin is accessed from within inner class; needs to be declared final
            //origin是个本地变量，被内建class访问时，需要在外面declare？
            int diff = getDistance(b, globalOrigin) - getDistance(a, globalOrigin);
            if(diff == 0) {
                diff = b.x - a.x;
            }
            if (diff == 0) {
                diff = b.y - a.y;
            }
            return diff;
        }
    });

7.Copy List with Random Pointer

8.Window Sum

1. 求某一段和： s[j] - s[k -1] 
2. 求S[i] ： s[i] = s[i - 1] + a[i] 
3. 节省空间
法1. 链表保存sum
法2. 数组滚动

9. Check Word Abbreviation

情况1.出现数字 while里面套while，计算num
情况2.未出现数字 if (s[++] ！= a[++])

10. Words Abbreviation

所有string 的 prefix initial is 1，
use Hashmap to count repeated 
use while to scan ans[] 很多很多遍，
each time, check ans[i] in map whether count > 1 
never mind the old string in map, Because  we scan the ans[] ,not map.
注意挪动的是prefix，所以每次传入缩写函数的是dict而不是ans。

11 Mirror Numbers

1.使用Map存储pair
2.用int[256] 来代替map存储char，节省空间！

12 Sliding Window

idea : 1. use queue
sum = sum + val - queue.pop()
2. use sum[100000] instead of queue
sum[n~n+size] = sum[n+size] - sum[n]
id ++
3. use scroll: use mod to get id,
actual_id = id % (size + 1);
Eg: size = 3, id : 0,1,2,3,4,5 
actual_id : 0 , 1, 2, 3 ,0,
(here we initial sum = [size + 1])
so that sum[actual_id] = sum[actual_id  - 1] + val
still : sum[n~n+size] = sum[n+size] - sum[n]

13. Edit Distance

if( == ) {( i,j ) = (i - 1, j - 1)}
else{ (i, j) =  min[ (i - 1,j) ,(i , j - 1), (i - 1, j-1)  ] }

14. Edit Distance2

if(n > m){ return isOneEditDistance(t, s);}

15. Roman to Integer

1. except : 4 ,9, 40 ,90, 400, 900 ,others are all : left > right --->left+right
2. if left < right : right - left
3. use dict/map to store dictionary------> use switch instead
4. avoid discuss the last one:  
  every for-loop 

16.Integer to Roman

  四个list就搞定了

17 Strings Serialization

  不适用StringBuilder的话，会time exceed 

String 字符串常量
StringBuffer 字符串变量（线程安全）
StringBuilder 字符串变量（非线程安全）
简要的说， String 类型和 StringBuffer 类型的主要性能区别其实在于 String 是不可变的对象, 因此在每次对 String 类型进行改变的时候其实都等同于生成了一个新的 String 对象，然后将指针指向新的 String 对象，所以经常改变内容的字符串最好不要用 String ，因为每次生成对象都会对系统性能产生影响，特别当内存中无引用对象多了以后， JVM 的 GC 就会开始工作，那速度是一定会相当慢的。
而如果是使用 StringBuffer 类则结果就不一样了，每次结果都会对 StringBuffer 对象本身进行操作，而不是生成新的对象，再改变对象引用。所以在一般情况下我们推荐使用 StringBuffer

先说一下集合的故事，HashTable是线程安全的，很多方法都是synchronized方法，而HashMap不是线程安全的，但其在单线程程序中的性能比HashTable要高。
StringBuffer和StringBuilder类的区别也是如此，他们的原理和操作基本相同，区别在于StringBufferd支持并发操作，线性安全的，适 合多线程中使用。StringBuilder不支持并发操作，线性不安全的，不适合多线程中使用。新引入的StringBuilder类不是线程安全的，但其在单线程中的性能比StringBuffer高。

18 Read Character from file

buffer 有多少读多少/读完了再清空