-
状态定义与深度优先搜索、广度优先搜索
本文的重要性
- 第一次归纳总结状态、状态空间和把问题抽象为树或图的方法
- 搜索是解决一切问题的万金油算法，众多没有多项式时间解法的问题都需要靠搜索求解
- 学会定义搜索框架，将极大地帮助你学习动态规划和图论算法
- 搜索题是训练代码能力最有效的题目类别
状态与状态空间
状态
什么是状态?
- 题面中涉及的所有数学信息
- 你在纸上人力计算时，关注的所有数据
- 一个函数访问的所有变量
例如最简单的计票问题
- 给n个名字，统计每个名字出现了多少次
你在纸上画“正”字统计的时候，关注了哪些数据?
- 名字（n个字符串)
- 统计到哪个名字了(第1
- 画的“正”字（一个用于计数的数据结构，例如Hash Map)
写成程序:
for (int i = 0; i < n; i++)
count[names[i]]++;访问的变量:
nnames- i
- count
我们只关注其中动态变化的数据，也就是 i 和 count
状态，就是程序维护的所有动态数据构成的集合
names = [“candela” , “Alice” , “Bob”, “Candela"]
状态空间 → 图
所有可能状态构成的集合就是一个问题的状态空间
把状态作为点，如果从一个状态可以到达另一个状态，就连一条边
这样就把整个状态空间抽象为了一张有向图
对问题的求解，就是对这张图的遍历计票问题的状态空间由n个状态组成
可以看作一张n个点，n-1条边的有向图
整张图是一条链，自然就可以用一维循环解决了状态的简化
在这里，当i固定以后，counts其实已经被决定了，它没有其他可能
counts对于i来说，只是一个附加信息，并不影响状态的规模
把可以由其它数据决定的信息从状态中排除，得到的最简状态决定了问题的复杂度
指数型状态空间（子集)
排列型状态空间（全排列)
搜索
搜索就是采用直接遍历整个状态空间的方式寻找答案的一类算法
根据遍历状态空间（图）方式的不同，可分为- 深度优先搜索（DFS, depth first search)
- 广度优先搜索(BFS, breadth first search)
一般来说，每个状态只遍历一次
所以当状态空间是“图”而不是“树”时，要判重（记忆化)搜索题的解题步骤:
- 纸上模拟，提取信息
- 定义状态
- 确定遍历顺序（DFS、BFS)
- 定义搜索框架
- 如果是DFS，状态作为参数，确定递归边界，注意还原现场
- 如果是BFS，状态用队列保存
- 考虑是否需要判重
- 程序实现
实战
17.电话号码的字母组合
https://leetcode.cn/problems/letter-combinations-of-a-phone-number/class Solution { public: vector<string> letterCombinations(string digits) { this->digits = digits; alphabet['2'] = "abc"; alphabet['3'] = "def"; alphabet['4'] = "ghi"; alphabet['5'] = "jkl"; alphabet['6'] = "mno"; alphabet['7'] = "pqrs"; alphabet['8'] = "tuv"; alphabet['9'] = "wxyz"; if (digits.empty()) return {}; dfs(0, ""); return ans; } private: void dfs(int index, string str) { if(index == digits.length()) { ans.push_back(str); return; } for(char ch : alphabet[digits[index]]) { dfs(index + 1, str + ch); } } string digits; vector<string> ans; unordered_map<char, string> alphabet; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
51.N皇后
https://leetcode.cn/problems/n-queens/class Solution { public: vector<vector<string>> solveNQueens(int n) { this->n = n; used = vector<bool>(n, false); dfs(0); vector<vector<string>> result; for(vector<int>& p : ans) { vector<string> pattern(n , string(n, '.')); for(int row = 0; row < n; row++){ pattern[row][p[row]] = 'Q'; } result.push_back(pattern); } return result; } private: void dfs(int row) { if(row == n) { ans.push_back(p); return ; } for(int col = 0;col < n; col++){ if(!used[col] && !usedPlus[row + col] && !usedMinus[row - col]) { p.push_back(col); used[col] = true; usedPlus[row + col] = true; usedMinus[row - col] = true; dfs(row + 1); usedMinus[row - col] = false; usedPlus[row + col] = false; used[col] = false; p.pop_back(); } } } int n; vector<int> p; vector<bool> used; unordered_map<int, bool> usedPlus; unordered_map<int, bool> usedMinus; vector<vector<int>> ans; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
200.岛屿数量
https://leetcode.cn/problems/number-of-islands/class Solution { public: int numIslands(vector<vector<char>>& grid) { m = grid.size(); n = grid[0].size(); visited = vector<vector<bool>>(m, vector<bool>(n, false)); int ans = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == '1' && !visited[i][j]){ ans++; bfs(grid, i , j); } } } return ans; } private: void bfs(vector<vector<char>>& grid, int sx, int sy) { queue<pair<int, int>> q; const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; q.push({sx, sy}); visited[sx][sy] = true; while(!q.empty()){ int x = q.front().first; int y = q.front().second; q.pop(); for(int i = 0; i < 4; i ++){ int nx = x + dx[i]; int ny = y + dy[i]; if(nx < 0 || nx >= m || ny < 0 || ny >=n ) continue; if(grid[nx][ny] != '1') continue; if(visited[nx][ny]) continue; q.push({nx, ny}); visited[nx][ny] = true; } } } int m, n; vector<vector<bool>> visited; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
130.被围绕的区域
https://leetcode.cn/problems/surrounded-regions/class Solution { public: void solve(vector<vector<char>>& board) { m = board.size(); n = board[0].size(); const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; fa = vector<int>(m * n + 1, 0); for(int i = 0; i <= m * n; i++) fa[i] = i; int outside = m*n; for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) { if (board[i][j] == 'X') continue; for(int k = 0; k < 4; k++) { int ni = i + dx[k]; int nj = j + dy[k]; if (ni < 0 || nj < 0 || ni >= m || nj >= n) { unionSet(num(i, j), outside); }else { if (board[ni][nj] == 'O') unionSet(num(i, j), num(ni, nj)); } } } for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (board[i][j] == 'O' && find(num(i, j)) != find(outside)) board[i][j] = 'X'; } private: int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } void unionSet(int x, int y) { x = find(x),y = find(y); if (x != y) fa[x] = y; } int num(int i, int j) { return i * n + j; } int m, n; vector<int> fa; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
433.最小基因变化
https://leetcode.cn/problems/minimum-genetic-mutation/
class Solution { public: // 解法2：双向bfs int minMutation(string start, string end, vector<string>& bank) { // 1：建立hashmap表，顺便去掉重复元素 unordered_map<string,int> mp; for(const auto& b:bank)mp[b]=0; // 2：排除极端情况，end不在基因库中 if(mp.count(end)==0)return -1; // 3：bfs的初始化工作 queue<string> q1({start}),q2({end});// 前向队列，后向队列 int step=0; const char table[4]={'A','C','G','T'};// 基因的字符 // 或1表示前向队列由前往后遍历，或2表示后向队列由后向前遍历，每次我们选用较小的队列进行遍历 for(mp[start]|=1,mp[end]|=2;q1.size()&&q2.size();++step)//每遍历完一次，步长+1 { bool first=q1.size()<q2.size(); queue<string> &q=first?q1:q2;// 选择较小的队列进行遍历节约时间 int flag=first?1:2;// 此次遍历的方式 for(int n=q.size();n--;q.pop()){ string temp=q.front();// 这里不要使用引用 if(mp[temp]==3)return step;// 两个队列碰头，返回步长 for(int i=0;i<temp.size();++i){ for(int j=0;j<4;++j){ string s=temp; if(s[i]==table[j])continue;// 重复字符，跳出循环，寻找下一个字符 s[i]=table[j]; if(mp.count(s)==0||mp[s]&flag)continue;// 该单词不在 map 中或该单词已经被遍历过了，跳出循环，寻找下一个单词 mp[s]|=flag;// 标记该单词已经被遍历过了 q.push(s); } } } } return -1; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
class Solution { public: int minMutation(string start, string end, vector<string>& bank) { depth[start] = 0; for(string& seq : bank) hashBank.insert(seq); if(hashBank.find(end) == hashBank.end()) return -1; queue<string> q; q.push(start); const char gene[4] = {'A', 'C', 'G', 'T'}; while(!q.empty()){ string s = q.front(); q.pop(); for(int i = 0; i < 8; i++){ for(int j = 0; j < 4; j++){ if(s[i] != gene[j]) { string ns = s; ns[i] = gene[j]; if(hashBank.find(ns) == hashBank.end()) continue; if(depth.find(ns) != depth.end()) continue; depth[ns] = depth[s] + 1; q.push(ns); if(ns == end) { return depth[ns]; } } } } } return -1; } private: unordered_set<string> hashBank; unordered_map<string, int> depth; };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
329.矩阵中的最长递增路径
https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/class Solution { public int longestIncreasingPath(int[][] matrix) { this.matrix = matrix; m = matrix.length; n = matrix[0].length; dist = new int[m][n]; dx = new int[]{-1, 0, 0, 1}; dy = new int[]{0, -1, 1, 0}; int ans = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++) { ans = Math.max(ans, dfs(i, j)); } } return ans; } int dfs(int x, int y) { if(dist[x][y] != 0) return dist[x][y]; dist[x][y] = 1; for(int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if(valid(nx, ny) && matrix[nx][ny] > matrix[x][y]) { dist[x][y] = Math.max(dist[x][y], dfs(nx, ny) + 1); } } return dist[x][y]; } int[][] matrix; int m ,n; int[] dx; int[] dy; int[][] dist; boolean valid(int i, int j){ return i >= 0 && i < m && j >=0 && j < n; } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
class Solution { public: int longestIncreasingPath(vector<vector<int>>& matrix) { m = matrix.size(); n = matrix[0].size(); to = vector<vector<int>>(m*n); deg = vector<int>(m * n, 0); dist = vector<int>(m * n, 0); const int dx[4] = {-1, 0, 0, 1}; const int dy[4] = {0, -1, 1, 0}; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ for(int k = 0; k < 4; k++){ int ni = i + dx[k]; int nj = j + dy[k]; if(valid(ni, nj) && matrix[ni][nj] > matrix[i][j]) { addEdge(num(i, j), num(ni, nj)); } } } } queue<int> q; for(int i = 0; i < m * n; i++){ if(deg[i] == 0) { q.push(i); dist[i] = 1; } } while(!q.empty()) { int x = q.front(); q.pop(); for(int y : to[x]) { deg[y]--; dist[y] = max(dist[y], dist[x] + 1); if(deg[y] == 0) q.push(y); } } int ans = 0; for(int i = 0; i < m*n; i++) ans = max(ans, dist[i]); return ans; } private: int m, n; vector<vector<int>> to; vector<int> deg; vector<int> dist; void addEdge(int u, int v) { deg[v]++; to[u].push_back(v); } int num(int i, int j) { return i*n + j; } bool valid(int i, int j){ return i >= 0 && i < m && j >=0 && j < n; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
DFS与BFS的对比
DFS更适合搜索树形状态空间
- 递归本身就会产生树的结构
- 可以用一个全局变量维护状态中较为复杂的信息（例:子集方案、排列方案)
- 不需要队列，节省空间
求“最小代价”、“最少步数”的题目，用BFS
- BFS是按层次序搜索，第k步搜完才会搜k＋1步，在任意时刻队列中至多只有两层
状态空间为有向无环图
- BFS拓扑排序/DFS记忆化搜索均可
推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习
-
相关阅读:
Qt 之 QUrlQuery使用详解
河南分销小程序开发|三级分销玩法介绍
Navicat Premium 16 安装及卸载
Oracle技术分享 oracle 19.14升级19.15
网卡的TSO卸载功能
MySQL官方文档如何查看，MySQL中文文档
怎样优雅地增删查改（六）：按任意字段关键字查询
Connor学Android - AsyncTask基本使用与源码解析
postgresql(openGauss)模糊匹配参数
验证码倒计时自定义hooks
- 原文地址：https://blog.csdn.net/qq_46118239/article/details/126766044
