本文的重要性
- 第一次归纳总结状态、状态空间和把问题抽象为树或图的方法
- 搜索是解决一切问题的万金油算法,众多没有多项式时间解法的问题都需要靠搜索求解
- 学会定义搜索框架,将极大地帮助你学习动态规划和图论算法
- 搜索题是训练代码能力最有效的题目类别
状态与状态空间
状态
什么是状态?
- 题面中涉及的所有数学信息
- 你在纸上人力计算时,关注的所有数据
- 一个函数访问的所有变量
例如最简单的计票问题
- 给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; };
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; };
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; };
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; };
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; } };
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; };
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; } }
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; } };
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等技术内容,立即学习