深度搜索、广度搜索及经典例题(上)
文章目录
- 深搜与广搜概念简介
- 深搜与广搜的经典例题
- Leetcode 130. 被围绕的区域：dfs记忆化搜索地图
- Leetcode 494. 目标和：dfs遍历所有情况
- Leetcode 473. 火柴拼正方形：dfs+剪枝
- Leetcode 39. 组合总和：dfs+剪枝
- Leetcode 993. 二叉树的堂兄弟节点：初涉bfs
深搜与广搜概念简介
搜索 ： 从初始状态，通过某种转化到中间状态，最终转化到终极状态的过程。
深度搜索 ：先不断从某一方向进行状态转化，直到无法转化，最后再回溯地向其他方向转化搜索。
广度搜索 ：先找到转化一步能遍历到哪些状态，然后找到转化两部能到达的状态，直到找到最终的状态。
深搜和广搜的本质：穷举遍历。深搜一般用递归实现，广搜一般用队列实现。
深搜与广搜的经典例题
Leetcode 130. 被围绕的区域：dfs记忆化搜索地图
题目链接
方法一：并查集。将边上的‘O’都和一个自定义的虚拟节点dummy相连，中间相邻的‘O’互相相连。最后遍历数组，只要其不和dummy相连，则变成‘X’.
class UnionFind{public:UnionFind(int n) {size = n;father = new int[n];treeSize = new int[n];for (int i = 0; i < n; i++) {father[i] = i;treeSize[i] = 1;}}int find(int x) {int root = x;while (root != father[root]) {root = father[root];}while (x != root) {int fx = father[x];father[x] = root;x = fx;}return root;}void merge(int a, int b) {int roota = find(a);int rootb = find(b);if (roota == rootb) return;if (treeSize[roota] < treeSize[rootb]) {father[roota] = rootb;treeSize[rootb] += treeSize[roota];}else {father[rootb] = roota;treeSize[roota] += treeSize[rootb];}}public:int *treeSize, *father, size;
};class Solution {
public:int node(int i, int j, int n) {return i * n + j;}void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();UnionFind uf(m * n + 1);int dummy = m * n;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'X') continue;if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {uf.merge(node(i, j, n), dummy);}else {if (i > 0 && board[i - 1][j] == 'O') {uf.merge(node(i - 1, j, n), node(i, j, n));}if (i < m - 1 && board[i + 1][j] == 'O') {uf.merge(node(i + 1, j, n), node(i, j, n));}if (j > 0 && board[i][j - 1] == 'O') {uf.merge(node(i, j - 1, n), node(i, j, n));}if (j < n - 1 && board[i][j + 1] == 'O') {uf.merge(node(i, j + 1, n), node(i, j, n));}}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (uf.find(node(i,j,n)) != uf.find(dummy)) {board[i][j] = 'X';}}}}
};
方法二：深度优先搜索
遍历矩阵时，将和边上的‘O’相连的所有‘O’先都变成‘#’， 然后再遍历一遍，将所有的‘O’都变成‘X’，‘#’ 都变回‘O’即可。
class Solution {
public:void dfs(vector<vector<char>>& board, int i, int j) {int m = board.size();int n = board[0].size();if (i < 0 || i >= m || j < 0 || j >= n) return;if (board[i][j] == 'X' || board[i][j] == '#') return;board[i][j] = '#';dfs(board, i + 1, j);dfs(board, i - 1, j);dfs(board, i, j + 1);dfs(board, i, j - 1);}void solve(vector<vector<char>>& board) {int m = board.size();int n = board[0].size();for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {bool isEdge = i == 0 || i == m - 1 || j == 0 || j == n - 1;if (isEdge && board[i][j] == 'O'){dfs(board, i, j);}}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == 'O') {board[i][j] = 'X';}else if (board[i][j] == '#') {board[i][j] = 'O';}}}return;}
};
Leetcode 494. 目标和：dfs遍历所有情况
题目链接
解题思路：对于n个数字，每个数字都有正负两种情况，所以一共有 2 n 2^n 2n中情况，可以用递归深搜的方法穷举所有情况。
class Solution {
public:int findTargetSumWays(vector<int>& nums, int target) {return dfs(nums, 0, target);}int dfs(vector<int>& nums, int i, int target) {if (i == nums.size()) {return target == 0 ? 1 : 0;}return dfs(nums, i + 1, target - nums[i]) + dfs(nums, i + 1, target + nums[i]);}
};
Leetcode 473. 火柴拼正方形：dfs+剪枝
题目链接
解题思路：首先如果所有火柴的长度和不是4的倍数，则不可能拼成正方形；然后可以从大到小的遍历火柴数组，分别尝试放到大小为4的边长数组中（这其中用到了深搜回溯），如果最终正好能放下则返回true, 否则返回false。
为什么要先放最长的火柴？因为放了长火柴以后可以最大程度的缩小问题规模，短火柴可以填充空缺用。
class Solution {
public://自定义排序函数，降序排序static bool cmp(const int a, const int b) {return a > b;}bool makesquare(vector<int>& matchsticks) {int sum = 0;for (auto x : matchsticks) sum += x;int sideLen = sum / 4;if (sideLen * 4 != sum) return false;vector<int> sums(4);sort(matchsticks.begin(), matchsticks.end(), cmp);return dfs(0, matchsticks, sums, sideLen); }bool dfs(int idx, vector<int> matchsticks, vector<int> sums, int sideLen) {if (idx == matchsticks.size()) {//遍历到了最后一根火柴，看四个边长是否相等。return (sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == sums[3]); }int n = matchsticks.size();int element = matchsticks[idx];for (int i = 0; i < 4; i++) {//或后面为一个优化点，如果sums[i] + element还不够预设边长sideLen,//则起码要加上最短的火柴matchsticks[n-1] 还不大于sideLen才可以//如果不加这个优化点会超时不能通过if (sums[i] + element == sideLen || sideLen >= sums[i] + element + matchsticks[n-1]) {sums[i] += element;if (dfs(idx + 1, matchsticks, sums, sideLen)){return true;}sums[i] -= element;}}return false;}
};
Leetcode 39. 组合总和：dfs+剪枝
题目链接
解题思路：首先这道题等价于组合钱的问题（有1块，2块，5块三种面额的钱，组合出来10块钱共有哪些组合方法，或者有多少种组合方法），因此可以用 动态规划 的方法来做。这里主要介绍 深度搜索 的方法。
可以依次将每一个数加到路径path中，增加的过程中减少对应target的值，如果最后target正好等于0， 则可以将当前的path加到结果ans中，否则如果target < 0则直接返回；target > 0 时继续加路径。
class Solution {
public:void dfs(vector<int>& candidates, int begin, int end, int target, vector<int> path, vector<vector<int> > &ans) {if (target == 0) {ans.push_back(path);return;}//从当前位置begin开始递归，因为每个数字能被重复使用。for (int i = begin; i <= end; i++) {//下一行为小的优化点，提前对数组从小到大排序，当前数字都能使target<0,之后的数字肯定也会if (target - candidates[i] < 0) break;path.push_back(candidates[i]);dfs(candidates, i, end, target - candidates[i], path, ans);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int> > ans;vector<int> path;sort(candidates.begin(), candidates.end());dfs(candidates, 0, candidates.size() - 1, target, path, ans);return ans;}
};
Leetcode 993. 二叉树的堂兄弟节点：初涉bfs
题目链接
解题思路：
方法一：深搜。递归遍历数组，可以找到目标节点对应的父节点和深度。然后对于两个目标节点，判断其父节点和深度是否相同。其中寻找父节点和深度的过程利用深度搜索实现。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> dfs(TreeNode *root, TreeNode*fa, int k, int x) {//结果数组，第一位存x节点的深度，第二位存x节点的父节点。vector<int> res(2);if(root == nullptr) {res[0] = -1, res[1] = -1;return res;}if (root->val == x) {res[0] = k;if (fa == nullptr) res[1] = -1;else res[1] = fa->val;return res;}vector<int> left = dfs(root->left, root, k + 1, x);vector<int> right = dfs(root->right, root, k + 1, x);if (left[0] != -1) return left;return right;}bool isCousins(TreeNode* root, int x, int y) {vector<int> resx = dfs(root, nullptr, 0, x);vector<int> resy = dfs(root, nullptr, 0, y);return resx[0] == resy[0] && resx[1] != resy[1];}
};
方法二：广搜。将深搜中dfs的功能逻辑用广搜实现。将二叉树中每个节点对应的父节点、深度都视作一个统一的结构体，依次层序遍历的过程中放入队列中，再依次从队列中获取元素，直到获取的元素等于target值（广搜的标准做法）。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/struct Node {TreeNode *cur;int depth, father;};
class Solution {
public:vector<int> bfs(TreeNode *root, int x) {queue<Node> que;vector<int> ans(2);ans[0] = -1, ans[1] = -1;que.push((Node){root, 0, -1});while (!que.empty()) {Node node = que.front();que.pop();if (node.cur->val == x) {ans[0] = node.depth;ans[1] = node.father;return ans;}else {if (node.cur->left != nullptr) {que.push((Node){node.cur->left, node.depth + 1, node.cur->val});}if (node.cur->right != nullptr) {que.push((Node){node.cur->right, node.depth + 1, node.cur->val});}}}return ans;}bool isCousins(TreeNode* root, int x, int y) {vector<int> resx = bfs(root, x);vector<int> resy = bfs(root, y);return resx[0] == resy[0] && resx[1] != resy[1];}
};
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！