首页 > 代码库 > 我要好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. 综合

走迷宫问题