总结

general
遇到问题将算法模块化，可以假设一些方法已经给出或者之后再编写，可以加快找出主体思路的速度，减少浪费时间在细节上

*先想test case

-----------------------------------------------------------------------
tree

https://www.topcoder.com/community/data-science/data-science-tutorials/an-introduction-to-binary-search-and-red-black-trees/



#遇到prefix，stream of strings等，上tries

#（写法）递归时，在返回所需要的极值，传入pointer同时计算partial的值（如height，path sum）
例子：
LC #124 Binary Tree Maximum Path Sum
GeeksforGeeks: Diameter of a Binary Tree
# 另一种写法，返回的是partial的值，参数中pass by reference一个极值

#(写法) bfs，用一个queue和size来区分每一层，例子：level order traversal等等 #1 bst
遇到bst题目先考class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        int n = costs.size();
        if (n == 0) return 0;
        int dp0 = costs[0][0];
        int dp1 = costs[0][1];
        int dp2 = costs[0][2];
        
        for (int i = 1; i < n; i++) {
            int t0 = dp0, t1 = dp1, t2 = dp2;
            dp0 = costs[i][0] + min(t1,t2);
            dp1 = costs[i][1] + min(t2,t0);
            dp2 = costs[i][2] + min(t1,t0);
        }

        return min(min(dp0,dp1),dp2);
    }
};虑in place遍历方法：pre - in - post（#94，#144，#145，#105，#106）
注：#94跟#173的单stack写法

dfs寻找路径，可以用一个大小为树的高度的vector跟int level表示当前高度

-----------------------------------------------------------------------
string
palindrome(LC: #5, #9, #125, #131, #132, #214), 可以预先用DP检测palindrome存值

-----------------------------------------------------------------------
dp
from Tara: 局部最优解关键词：最大，最小，至少，至多

从recursion引出dp

string类的，先从小的test case下手，如(ab,b) 
例题：LC #115,distinct subsequence

矩阵类（见矩阵词条）

多层dp，paint house

-----------------------------------------------------------------------
array
直接上：双指针和hashmap
-----------------------------------------------------------------------
subsets / combination
此类问题有2种解题思路（LC #90，#77，#39， #40）
假如有集合{1，2，3，4，5}
#1 传统combination
递归: 第一层递归，每次取{}空集合，各插入一元素。第二层递归，此时集合内含有一个元素，每次插入index大于它的元素
第一层{1},{2}, {3}, {4}, {5}
第二层{1, 2}, {1,3},{1,4}, {1,5},{2, 3}, {2,4},{2,5},{3,4}.....
第三层{1,2,3},{1,2,4},{1,2,5},{1,3,4},{1,3,5}.....{2,3,4},{2,3,5}......
.....

遍历：看LC #90 Subsets代码

#2 类似bitmap
集合内的每个元素都有2种情况--被包括在集合或不被包括在集合
递归：见Google interview questions #2，第2题

遍历：
subsets的总个数为 2^原集合的大小，设一个loop大小为总个数，把每一个从0 到 总个数 - 1（看做二进制）的数作为bit mask，来跟原集合对应
看LC #90 Subsets代码
-----------------------------------------------------------------------
math
#1加减法, LC #2，#66，#67， 
#1 各种类型与integer的暂时互相转化
#2 carry可以用来当sum用
#3 loop的终止条件配合loop内的判断
#4 dummy node

--------------------------------------------------------------------
矩阵
矩阵路径：如果只能往下和往右走的话，用recursion或者dp (LC #130, #200)
如果增加其他方向，Dijkstra和普通的BFS都可以适用 (Google interview questions #3, 后几题) (Google interview questions #2, 第5题follow up)


矩阵中找最大的sub矩阵：
LC：#85 Maximal Rectangle, #221 Maximal Square, Google interview #6 倒数第2道，http://www.geeksforgeeks.org/dynamic-programming-set-27-max-sum-rectangle-in-a-2d-matrix/

------------------------------------------------------------------------
Linked List
快慢指针的使用：
如下循环结束后，slow将指向中点（奇数个）或指向后半部分的起点（偶数个）

ListNode *slow = head, *fast = head;
while (fast != NULL) {
    fast = fast->next;
    if (fast != NULL) {
        fast = fast->next;
        slow = slow->next;
    }
}

-------------------------------------------------------------------------
点跟线段，坐标
sort x或y
closest pair of points(code 见coursera 第一章)

找median
example: 见google interview #5 第1,2部分 的oil pipe，朋友矩阵

------------------------------------------------------------------
随机性的题（待写）
general，高中概率论：某个值最终被选中的概率 = 当前被选中的概率 * 之前没被选中的概率

扑克牌http://www.geeksforgeeks.org/shuffle-a-given-array/

用ran(5)生成ran(7): 二维数组
{[1,2,3,4,5],
  [6,7,1,2,3],
  [4,5,6,7,1],
  [2,3,4,5,6],
  [7,0,0,0,0]}

Reservoir sampling: Google interview questions #4 倒数第2题
https://en.wikipedia.org/wiki/Reservoir_sampling
http://www.geeksforgeeks.org/reservoir-sampling/

-------------------------------------------------------------
Sorting
Merge sort: count inversions, LC # 148，#88，#23，#21
radix sort/count sort/bucket sort: LC #164

------------------------------------------------------------------
游戏算法
https://www.topcoder.com/community/data-science/data-science-tutorials/%20algorithm-games/
定理：

• All terminal positions are losing.
• If a player is able to move to a losing position then he is in a winning position.
• If a player is able to move only to the winning positions then he is in a losing position.

第一个例子：The Game of Nim
当所有piles的size xor之后如果是0的话，当前为losing position，因为输的条件是0，从0开始第一步肯定会让xor的值变成非0。
如果当前xor为非0，则从最左侧的1的个数为奇开始，改变当前的pile，可使xor变成0

------------------------------------------------------------
Binary search
(写法)
while (left <= right) {
    ....
}
if target is not found, after the search, "left" is always the index where target should be inserted. and "right" equals to "left - 1"
LC #35, #74, #240

----------------------------------------
Divide and conquer
切两半，需要的值可能在任意一边，或者是横跨两边。
example：closest pair of points， lc #53 maximum subarray,

-------------------------------------------------------
Recursion
(写法)对于求各种集合的题（如permutation，combination，求所有path），sub-set可以用pass by reference来代替，减少递归时的空间，LC #113 Path Sum II

---------------------------------------------------
Graph
bfs： 例题：person找血缘关系，第2部分第8题

Union find: 代码，google interview #7 第一部分第1题
http://blog.csdn.net/dm_vincent/article/details/7655764
The input is a sequence of pairs of integers, where each integer represents an object of some type and we are to interpret the pair p q as meaning p is connected to q. We assume that "is connected to" is an equivalence relation:
case study:
http://algs4.cs.princeton.edu/15uf/

-----------------------------------
Interval的题
排序，merge或者split，见google#6，飞哥的题。LC的那几道

------------------------------------------
sliding window的题
当发现至少一个window符合要求时，以后的操作都要维护、保持这个window的合法性
例子： LC #3 Longest Substring Without Repeating Characters, #76 Minimum Window Substring 等等

--------------------------------------------------
Longest sub-string/sequence 类
考虑DP，lintcode上有一套