首页 > 代码库 > 我要好offer之 搜索算法大总结
我要好offer之 搜索算法大总结
1. 二分搜索
详见笔者博文:二分搜索的那些事儿,非常全面
2. 矩阵二分搜索
(1) 矩阵每行递增,且下一行第一个元素大于上一个最后一个元素
(2) 矩阵每行递增,且每列也递增
3. DFS 深度优先搜索
适用场景:
(1) 输入数据:如果是 递归数据结构(如单链表、二叉树),则一定可以使用DFS
(2) 求解目标:必须走到最深处(例如二叉树,必须走到叶子节点)才能得到一个解,这种情况一般适合用DFS
思考步骤:
(1) DFS最常见的3个问题:求可行解的总数、求任一个可行解、求所有可行解
(a) 如果是 求可行解总数,则不需要 数组path[] 来存储 搜索路径
(b) 如果是 求可行解本身,则需要一个 数组path[] 来存储 搜索路径序列
DFS在搜索过程中 始终只有一条搜索路径,一直搜索到绝境再回溯继续搜索,因此只需要一个数组就可以了
BFS需要存储 扩展过程中的搜索路径,在没有找到答案之前 所有路径都不能放弃
(2) 只要求任一可行解? 要求所有可行解?
如果只需要一个可行解,找到一个即可返回
如果要求所有可行解,找到一个可行解之后,必须继续扩展,直到遍历完
BFS一般只要求一个解,如果用BFS要求所有解,就需要扩展到所有叶子节点,相当于在内存中有指数级的存储空间
(3) 如何表示状态?
一个状态需要存储哪些必要的信息,才能够正确的扩展到下一步状态.
DFS一般使用函数参数的方法,因为DFS一般有递归操作,扩展下一状态只需要修改 递归函数的函数参数即可
BFS一般使用struct结构体存储所有信息,struct里的字段与DFS中的函数参数字段一一对应
(4) 如何扩展状态?
对于二叉树:扩展左子树、右子树
对于图、矩阵:题目告知,比如 只能向右或向下走, 比如 上下左右四个方向均可扩展
(5) 如何判重?
(a) 是否需要判重?
如果 状态转换图是 一棵树,则不需要判重,树的所有子树均分离,不存在重叠子问题,因此二叉树的所有DFS都不需要判重
如果 状态转换图是 DAG(有向无环图),则需要判重,因此 所有的BFS都需要判重
(b) 怎样判重?
(6) 搜索的终止条件是什么?
终止条件是 不能继续扩展的末端结点
对于树:叶子节点
对于图:出度为0的节点
(7) 收敛条件是什么?
为了判断是否到达收敛条件,DFS一般需要在递归函数接口里 用一个参数记录当前状态(cur变量) 或者 距离目标还有多远(gap变量)
如果是 求一个解,直接返回这个解,即path路径数组
如果是 求所有解,则把 这个解path数组复制到 解集合中 (一般利用 c++ vector中的push_back函数,push时采用的是copy构造函数)
(8) 如何加速?
(a) 剪枝:图的DFS中需要挖掘各种信息,包括搜索边界、值大小关系等
(b) 缓存:状态转换图是DAG ==> 存在重叠子问题 ==> 字问题的解会被重复利用
如果输入结构是 二叉树,不存在重叠子问题,不需要缓存
一般使用c++11的 std::unordered_map来缓存,或者使用一个二维数组 std::vector<std::vector<int>>
DFS模板:
数据结构为树(二叉树)的DFS模板(不需要判重和缓存):
/** DFS模板 * @param[in] input :对于二叉树一般为root指针,对于图一般是输入矩阵即二维数组 * @param[in] path:当前搜索路径,也是中间结果,一般为一维vector * @param[in] cur or gap:标记当前位置或距离目标的距离 * @param[out] result:存放最终结果,一般是二维vector,每一维为path数组 */ void dfs(type input, std::vector<int>& path, int cur or gap, std::vector<std::vector<int>>& result) { if (数据非法) return; // 终止条件,对于二叉树即input为空,对于图即 搜索边界越界 if (cur == input.size() or gap == 0) { // 收敛条件 result.push_back(path); } // 执行所有扩展路径 path.push_back(); // 执行动作,修改path // 扩展动作一般有多个,对于二叉树就是 input->left和input->right,对于图可能就是 y-1,y+1,x-1,x+1(上下左右) dfs(input, path, cur + 1 or gap - 1, result); path.pop_back(); // 恢复path}
例题: 二叉树路径和问题
数据结构为图的DFS模板(需要判重):
/** DFS模板 * @param[in] input :对于二叉树一般为root指针,对于图一般是输入矩阵即二维数组 * @param[in] path:当前搜索路径,也是中间结果,一般为一维vector * @param[in] cur or gap:标记当前位置或距离目标的距离 * @param[in] visited:用于判重的二维数组 * @param[out] result:存放最终结果,一般是二维vector,每一维为path数组 */ void dfs(type input, std::vector<int>& path, int cur or gap, std::vector<std::vector<bool>> visited, std::vector<std::vector<int>>& result) { if (数据非法) return; // 终止条件,对于二叉树即input为空,对于图即 搜索边界越界 if (cur == input.size() or gap == 0) { // 收敛条件 result.push_back(path); } if(visited[x][y] == true) return; // 判重 // 执行所有扩展路径 visited[x][y] = true; path.push_back(); // 执行动作,修改path // 扩展动作一般有多个,对于二叉树就是 input->left和input->right,对于图就是 y-1,y+1,x-1,x+1(上下左右) dfs(input, path, cur + 1 or gap - 1, visited, result); path.pop(); // 恢复path visited[x][y] = false;}
例题:在字符矩阵中查找单词
矩阵右下走的路径总数(可能有障碍)
4. BFS 广度优先搜索
适用场景:求最短搜索路径
/** BFS模板 * param[in] state_t:状态,如整数、字符串、数组等 * param[in] start:起点 * parma[in] grid:输入矩阵数据 * return 从起点到目标状态的一条最短路径 */ std::vector<state_t> bfs(state_t start, std::vector<std::vector<int>>& grid) { std::queue<state_t> que; // 队列 std::unordered_set<state_t> visited; // 判重,也可以直接使用 二维vector bool found = false; que.push(start); visited.insert(start); while (!que.empty()) { state_t state = que.front(); que.pop(); if (state为目标状态) { found = true; break; } // 扩展状态,对于二叉树即左右子树,对于图可能就是上下左右四个方向 std::vector<state_t> stateVec = state_extend(state); // 扩展状态必须考虑 搜索边界越界时的剪枝 和 visited的判重 for (auto iter = stateVec.begin(); iter != stateVec.end(); ++iter) { state_t curState = *iter; if (curState为目标状态) { found = true; break; } // curState不满足目标状态,则入队 que.push(curState); visited.insert(start); } } if (found) { return generate vector<state_t>; } else { return vector<state_t>(); }}
例题:二叉树层次遍历
5. 综合
走迷宫问题