Leetcode: 总结
general
遇到问题将算法模块化，可以假设一些方法已经给出或者之后再编写，可以加快找出主体思路的速度，减少浪费时间在细节上
*先想test case
-----------------------------------------------------------------------
tree
#遇到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题目先考虑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
矩阵类（见矩阵词条）
-----------------------------------------------------------------------
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将指向中点（奇数个）或指向后半部分的起点（偶数个）
-------------------------------------------------------------------------
点跟线段，坐标
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/
定理：
第一个例子：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上有一套
Read full article from Leetcode: 总结
general
遇到问题将算法模块化，可以假设一些方法已经给出或者之后再编写，可以加快找出主体思路的速度，减少浪费时间在细节上
*先想test case
-----------------------------------------------------------------------
tree
#遇到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题目先考虑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
矩阵类（见矩阵词条）
-----------------------------------------------------------------------
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将指向中点（奇数个）或指向后半部分的起点（偶数个）
1
2
3
4
5
6
7
8
| 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上有一套
Read full article from Leetcode: 总结
