总结20道常见题目
1. 堆排序
2. 快速排序 leetcode - 148
3. 归并排序 leetcode - 88: 合并已排序数组
4. 找出数组中第k大的数 leetcode-215
5. 找出出现次数前k名的元素leetcode-347 (heap, hash table)
6. 在数据流中，找中位数 leetcode-295 (Hard)
7. 二叉树的先序遍历 (二叉树) leetcode-144
8. 二叉树的中序遍历 (二叉树) leetcode-94
9. 二叉树的后续遍历 (二叉树) leetcode-145
10. 二叉树的层次遍历 (二叉树) queue
11. 反转二叉树 (二叉树)
12.支持max/min操作的栈 (栈) leetcode-155
13. 链表反转 (链表) leetcode-206
14. 最大子序列和 (动态规划)
15. 区间合并 (直接解法, 排序然后合并) leetcode-56
16. 找出第一个没有重复的字符 (字符串) leetcode-387
17. 删除重复的字符 (字符串) leetcode-316 (HARD)
18. 把字符串按照出现的频次排序(字符串) leetcode-451
19. 回文字检测 (字符串) leetcode-125
20. 2SUM (leetcode-1, EASY), 3SUM(leetcode-15, Medium), 4SUM(leetcode-18, Medium)
21. 子串匹配 (KMP)
22. Kill Process (leetcode-582) Queue
23. 楼梯的爬法 (leetcode-70 动态规划) 感觉也就复杂到动态规划.
24. 最长公共子串（动态规划有关）
25. 用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环；
26. 两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值
经典数据结构的概念和原理
- 后缀树 如何在语料中寻找频繁出现的字串，分析复杂度（tire树）
- 红黑树
- B树
- B+树
- 字典
- DFS BFS 迷宫的深度搜索、广度搜索
Leet code分类:
算法的代码或提示
二叉树的中序遍历：
https://github.com/jicahoo/leetcode-java/blob/master/src/main/java/com/flash/leetcode/Q94_BinaryTreeInOrderTraversal.java
def inorderTraversal(root: TreeNode): List[Int] = {
val list = new mutable.ListBuffer[Int]()
var stack = List[TreeNode]()
var curRoot = root
while (curRoot != null || stack.nonEmpty) {
while (curRoot != null) {
stack = curRoot :: stack
curRoot = curRoot.left
}
if (stack.nonEmpty) {
val topNode = stack.head
list += topNode.value
curRoot = topNode.right
stack = stack.tail
}
}
list.toList
}
支持max/min操作的栈
public void push(int x) {
StackNode topNode = stack.peek();
if (topNode == null) {
StackNode node = new StackNode(x, x);
stack.push(node);
} else {
int minVal = topNode.getMinVal();
int newMinValue = minVal;
if (x < minVal) {
newMinValue = x;
}
StackNode node = new StackNode(x, newMinValue);
stack.push(node);
}
}
最大子序列和
- 动态规划，问题转化加找出动态转移方程，以下标k为结束的最大子序列和记为Sum(k). 那么
- Sum(k) = if (A[k] < 0 ) Max(Sum(k-1)+A[K], 0) else Sum(k-1)+A[k] 。
- 那么，最大子序列和=Max( Sum(k) ) (k=1,...,n-1) 在