leetcode––为求职为生的编程网站
前言
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的路径可能是
x；
left + x;
right + x;
fat + x;
left + x + right;
left + x + fat;
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](https://leetcode.com/problems/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，数据只是为了验证想法是否合理。
做题的重点是**题目分析、想法实现、复杂度分析**，这也是面试中希望面试者能展现出来的。