什么时候使用BFS:

• 图的遍历
  • 分层的图的遍历（简单图的最短路径）
  • 通过一个点，找到图的所有的点，这个用DFS和BFS都可以，如果是图的话，用DFS，很可能导致递归深度太深。
  • 拓扑排序
• 最短路径
• 简单图的最短路径(简单图：每条边长度都是1，并且没有方向)

BFS题

BinaryTree Level Order Traversal

• lintcode中binary Tree的testCase:https://www.lintcode.com/help/binary-tree-representation/
• 非python一般用linkedList来做queue
• 可以用lintcode里面queue的题目来对queue做一下专门练习

Binary Tree Serialization

图上的宽度优先搜索

什么时候使用DFS:

- 当题目目的是找到问题的<b>所有方案</b>的时候用DFS(subsets)
- 深搜只要搜索就行了,只需要存储当前路径（栈），宽搜是需要保存状态的

递归三要素：

- 递归的定义：接收什么参数，返回什么值 …

面试

面试一般的问题：

• KMP算法(字符串匹配)，但是一般面试就是使用两重循环就可以解决，不会直接考比较复杂的算法。一般先用简单方式解决之后才会看是否会扩展
• 自己的算法经验不应该写在resume里面，因为会加大面试官对题目的考察难度
• 面试的时候，要注意自己的coding style，另外就是变量命名不要a/b/x/y等
• 注意参数检查,input是否是None?array长度是否是0?
• 与面试班可以讨论，不要自己在那里写代码

面试考察的基本功

• 程序风格（缩进、括号、变量名）
• Coding习惯（异常检查、边界处理）
• 沟通（让面试官立刻明白你的意图）
• 测试（主动些出合理的TestCase）(比如有可能输入有两个空字符串等等)

如何刷题：

• 总结和归类相似问题
• 找出适合同一类型的题目模板

题目

排列组合问题题目

给一个结合如[1,2,3]，找出所有的非降序排列
如S = [1,2,3]，则返回 …

Description

Given two integers n and k. Return all possible combinations of k numbers out of 1, 2, ... , n.

Example

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Example 2:

Input: n = 4, k = 1
Output: [[1],[2 …

Description

Give a string, you can choose to split the string after one character or two adjacent characters, and make the string to be composed of only one character or two characters. Output all possible results.

Example

Example1

Input: "123"
Output: [["1","2","3"],["12","3"],["1","23"]]

Example1

Input …