深度优先 leetcode 算法 广度优先 深度搜索、广度搜索及经典例题(上)

文章目录

深搜与广搜概念简介深搜与广搜的经典例题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>& 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>& 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>& 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& nums, int target) {

return dfs(nums, 0, target);

}

int dfs(vector& 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& matchsticks) {

int sum = 0;

for (auto x : matchsticks) sum += x;

int sideLen = sum / 4;

if (sideLen * 4 != sum) return false;

vector sums(4);

sort(matchsticks.begin(), matchsticks.end(), cmp);

return dfs(0, matchsticks, sums, sideLen);

}

bool dfs(int idx, vector matchsticks, vector 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& candidates, int begin, int end, int target, vector path,

vector > &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> combinationSum(vector& candidates, int target) {

vector > ans;

vector 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 dfs(TreeNode *root, TreeNode*fa, int k, int x) {

//结果数组，第一位存x节点的深度，第二位存x节点的父节点。

vector 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 left = dfs(root->left, root, k + 1, x);

vector 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 resx = dfs(root, nullptr, 0, x);

vector 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 bfs(TreeNode *root, int x) {

queue que;

vector 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 resx = bfs(root, x);

vector resy = bfs(root, y);

return resx[0] == resy[0] && resx[1] != resy[1];

}

};

好文推荐