前言
leetcode是一个在线编程网站，题目源于各大公司的面试、有各种解法、多语言和在线测试支持；
我们扫一眼leetcode上的Company：Google、Uber、Facebook、Twitter、Amazon、Microsft、Apple、Yahoo；
leetcode的题更贴近实际工作，在实现想法的过程中，我也尽可能按照实际应用的角度出发。
关键词：题目解析、时间复杂度、空间复杂度、代码量、其他解法的优劣；
网站传送门
正文
4.Median of Two Sorted Arrays
题目大意：
两个有有序数组，找到两个数组合并后的中位数。
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
题目解析：
每次从两个数组中找到一个最小的，直到中间即可；
为了实现方便，把取下一个的操作用函数封装起来；
复杂度解析：
1、时间复杂度
O(N+M) N、M是两个数组的长度；
2、空间复杂度
O(1)；
3、代码量
从两个数组返回最小值，并指向下一个可以用函数getNext封装；
其他解法：
直接合并两个数组，然后排序，取中位数；
优劣：代码量更小，但时间较长。
23. Merge k Sorted Lists
题目大意：
给出k个有序的链表，把k个链表合并一个有序链表。
题目解析：
轮询，每次从链表中取出最小的一个值；
时间复杂度O（N*M）N是所有节点的数量和，M是链表数量；
收获一枚TLE;
增加一个优先队列的优化，每次取出一个值的时候，把上一个值添加到优先队列里；
时间复杂度O(N*LogM)。
在priority_queue中结构体指针的比较函数卡顿了很久，不需要引用。
其实除了struct cmp的方式，还可以定义bool operator <。
其他解法：
每次只合并两个链表；（这样就不用每次轮询判断M条链）
然后用归并，这样也能极快的合并完k条链。
44. Wildcard Matching
题目大意：
输入一个串s和一个匹配串p，问是否匹配。
匹配串中包括两种特殊字符：
1、？ 匹配单个字符；
2、* 通配符；
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
题目解析：
？的匹配非常简单；
* 的匹配较为复杂，匹配多个长度的字符串，甚至是长度为0的字符串。
考虑通过搜索来实现这个匹配方案。
匹配的状态有两个：s串当前的匹配位置，p串当前的匹配位置；
遇到？时，直接跳到下一个位置；
遇到*时，枚举下一个可能的位置，只要有一个返回yes，即可；
收获一枚TLE，原因在于样例有多个*，搜索在遇到*的时候会多项式级别( O(N!) )增加耗时。
改用动态规划：
dp[i][j] 表示s串前i个字符和p串前j个字符是否匹配；
转移时根据当前字符串，分别遍历前面的结果；
时间复杂度为O(N^2*M)，N为原串的长度，M为匹配串长度；
空间复杂度为O(N*M)。
更可以优化的地方：dp[i][j]求解中只用到dp[k][j-1]的结果，那么可以用滚动数组来优化，空间复杂度可以降为O(M);
最elegant的做法：贪心。
虽然时间复杂度同样是O(N*M)，但是空间复杂度降到O(1)。
当匹配失败的时候，不需要从原来的位置匹配，只需从最近的一个星号开始匹配。
124. Binary Tree Maximum Path Sum
题目大意：
给出一颗二叉树，每个节点有权值；
求出权值和最大的路径，输出路径的权值和。
例如，给出这样一棵树：
1
/ \
2 3
输出6。
题目解析：
对于一个节点x，假设两个儿子为left[x]、right[x]，父亲节点为fat[x];
那么对于x，包含x的路径可能是
1、 x；
2、 left + x;
3、 right + x;
4、 fat + x;
5、 left + x + right;
6、 left + x + fat;
7、 right + x + fat;
为了实现方便，可以对left、right、fat、0、0排序，取前两个和x合并即可；
提示：
left + x = left + x + 0;
right + x = right + x + 0;
x = 0 + x + 0;
时间复杂度O(N)，空间复杂度O(N);
其他解法：
都需要遍历树，而遍历树的复杂度不会低于O(N);
126. Word Ladder II
题目大意：
给出beginWord和endWord，以及一个字符字典wordlist。
从beginWord变成endWord，要求：
1、每次只能变一个单词；
2、每次变出来的单词必须在wordList列表；
所有单词同等长度，都是小写；
找出所有的变化次数最少的序列。
Example
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
Return
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
题目解析：
beginWord、wordlist、endWord两两连边（根据是否可变），用BFS求出最短路径；
需要记录最短路的路径，求出答案后用dfs遍历所有可能的答案。
收获一枚TLE：
建图用的是O(N^2)，导致边数较多。
当前做法的时间复杂度：
建图是O(N^2)，bfs是O(N^2)，dfs不确定，视答案多少而定。
加了一个简单的优化：
在比较两个字符串是否可以转换时，如果不同数量大于1，立即返回；
还可能加的优化：基数排序。这样可以极快的判断x、y是否可以trans；
其他做法：
枚举每个字符串下一步修改的可能字符，（len*26种可能），然后用set可以O(logN)来判断是否存在key；确实更快。
总结
leetcode上做题的人非常非常多，稍微热门一点的题目都是10w+的Accepted。
目的不是Accepted，数据只是为了验证想法是否合理。
做题的重点是题目分析、想法实现、复杂度分析，这也是面试中希望面试者能展现出来的。
