容易忘记的知识点：

1. Integer.MAX_VALUE = 2^31-1 = 0x7fffffff = 21,47483647 > 1e9 + 7,
   Integer.MIN_VALUE = -2^31 = 0x80000000 = -2147483648
   Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
   Math.abs(Integer.MIN_VALUE) = Integer.MIN_VALUE

2. 10!=3628800 12!=479001600

3. reverse an integer时，必须考虑overflow

4. int[26] for Letters 'a'-'z'or'A'-'Z' int[128] for ASCII int[256] for Extended ASCII

5. A的ASCII码是65,a的ASCII码是97

6. int mod = (int) 1e9 + 7

7. 2 to the power of x 或 2 to the x(th) power 比如2的4次方: 2 to the power of four 或 2 to the fourth power

8. 模数module 以...为模modulo

9. 负奇数 % 2都是-1

10. 罗马数字不用横线的最大值：3999 MMMCMXCIX

11. /取高位，%取低位。

12. 如果n>>>k,那么nlogk>klogn

13. 如果整棵树只有一个根节点，根节点不能被当成叶节点。

14. https://www.geeksforgeeks.org/bfs-vs-dfs-binary-tree/

15. 二叉树BFS的空间复杂度O(w)

16. The width of a tree is the maximum width among all levels.

17. The diameter of a binary tree is the length of the longest path between any two nodes in a tree.

18. pound井号#,asterisk星号*

19. 如果要用mod（题目提醒或者必须用时），一定要及时用，哪里可能溢出就得用mod.

20. 排序稳定性：排序前后相同值的相对位置不变
    https://stackoverflow.com/questions/19336881/why-isnt-heapsort-stable

21. 想到一个问题：递归有n层，每层消耗O(n)space，总时间复杂度是多少。

22. 小转大：某个字符-'a'+'A'；大转小：某个字符-'A'+'a'

23. The stack space of recursion is proportional to the recursion depth instead of times of recursion.

24. Set或者Map中最好不要存数组，因为实际存的是数组的内存地址，不能去重，想去重必须重写hashCode和equals方法。
    而且用contains时，会返回false，因为地址不一样。可以转化为String比较。e.g. 734. Sentence Similarity
    int[] arr1={10,12,15}; int[] arr2={10,12,15};

25. map.get(key)要考虑key是否在map中存在，先检查map.containsKey(key)

26. PriorityQueue<Long> heap = new PriorityQueue<>(); // must use Long to avoid overflow

    // you can't cast Integer to Long, even though you can convert from int to long.

    heap.offer(1l); // must use 1l

27. Even though the time complexity is optimized, using higher level object instead of primitive can cost more time.
    https://leetcode.com/problems/super-ugly-number/discuss/76291/Java-three-methods-23ms-36-ms-58ms(with-heap)-performance-explained

28. [4,2,null,1,null,3]是一个left skewed tree，[4,null,2,null,1,null,3] rigiht，[4,2,null,1,null,null,null,3]不是一个valid tree.

29. subsequence和sequence不一样，subsequence不能改变原有顺序，sequence可以，比如 128. Longest Consecutive Sequence

30. 1、数组是一个Object对象，所以直接使用数组的equals()方法，实际上是使用Object类的equals()方法。
    2、Object类的equals()方法，实质上还是使用==比较对象。
    3、JDK中很多类重写了equals()方法，包括java.lang.String类和java.util.Arrays类。
    4、当比较两个字符串的时候，它使用的是String类下的equals()方法，这个方法比较的是对象值。
    5、当比较两个数组的值的时候，需要使用Arrays类中的equals()方法。
    6、代码示例：

    char a[] = new char[] { 'a', 'b', 'c' };
    char b[] = new char[] { 'a', 'b', 'c' };
    System.out.println(Arrays.equals(a, b));

思路总结：

1. 什么时候用dummynode（不用检查输入节点是否为null）：题目要求返回一个链表

2. 什么时候用heap：从一组数中取最小值或者最大值。求k最大，用最小堆；求k最小，用最大堆。

3. 什么时候用stack：括号匹配问题，“时间对”问题636

4. 什么时候用BucketSort:数字范围是0-9时，可能会用桶排序。

5. BucketSort初始化：List[]bucket=newList[nums.length+1];//很少见的写法，要记住

6. 第k小：从小到大第k个；第k大：从大到小第k个。

7. 在一组数据中找最大值和最大值出现次数，不需要排序，很多题目用到这个技巧：398的followup，621

8. 数组中子数组的数量是(n+1)n/2，即O(n^2)。所以关于子数组的问题，暴力解一般是O(n^2)。

9. 有向图请慎重使用union find，最好不要用，无向图可以
   并查集只能判断无向环，拓扑排序可判断有向环。

10. 可以用O(n^2)暴力解决的问题：
    a.搜索范围的大小，找两个index或者两个num（1. Two Sum）
    b.一个字符串中找子串，子串的个数是n^2，其实就是找两个点，起点和终点，本质和a一样
    c.一个数组中找子数组也是一个道理

11. 最长回文子串LPS：Manacher's Algorithm
    strStr: KMP string searching/matching algorithm

12. 如果输入的dict是给的HashSet而不是Array或者List，可能还会说dict非常大（比如1个亿），那么有可能是在暗示dict只是用来查询字符串是否存在，因为查询是O(1)，不能遍历，因为太耗时间。

13. 如果输入的元素无重复，很可能是在暗示可以用Hash Table.

BitManipulation:

1. n & (n - 1) == 0, n is 0 or the power of 2.

Resources:

1. ASCII: http://www.bangnishouji.com/tools/ascii.html

Experience:

1. 第一次刷这个题,想5分钟,然后看答案,第二次想10分钟,做不出来看答案,第三次不看答案,看自己前两次的解题笔记,如果还不会,说明笔记总结的不好,去改这个笔记,再参考下自己提交过的答案,第四次再不会,抽自己.这就是我的刷题顺序.

HashMapkey-valuepair总结