【算法】DFS、BFS、floodfill、记忆化搜索
目录
1、DFS
面试题 08.06. 汉诺塔问题
- 面试题 08.06. 汉诺塔问题
要将a柱上n个的盘子借助b柱放到c柱上，应该先将a柱上的n-1个盘子借助c放到b上，然后再将b柱上的n-1个盘子借助a柱放到c柱上，以此往复。
class Solution {
public:void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {dfs(A, B, C, A.size());}void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n){if (n == 1){c.push_back(a.back());a.pop_back();return;}dfs(a, c, b, n - 1); // a柱上的n-1个盘子借助c柱放到b柱上c.push_back(a.back());a.pop_back();dfs(b, a, c, n - 1);}
};
合并两个有序链表
- 合并两个有序链表
重复子问题：合并两个有序列表。
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {if (list1 == nullptr) return list2;if (list2 == nullptr) return list1;if (list1->val <= list2->val){list1->next = mergeTwoLists(list1->next, list2);return list1;} else{list2->next = mergeTwoLists(list1, list2->next);return list2;} }
};
反转链表
- 反转链表
单链表可以看作一棵树。
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* newhead = reverseList(head->next);head->next->next = head;head->next = nullptr;return newhead;}
};
两两交换链表中的节点
- 两两交换链表中的节点
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) return head;ListNode* newhead = swapPairs(head->next->next);ListNode* ret = head->next;head->next->next = head;head->next = newhead;return ret;}
};
Pow(x, n)
- Pow(x, n)
当n过大时，我们可以先算x的n/2次方，依此递归，然后相乘。
另外对负数取正可能会超出int范围，所以要强转成long类型。
class Solution {
public:double myPow(double x, int n) {return n < 0 ? 1.0 / pow(x, -(long)n) : pow(x, n);}double pow(double x, long n){if (n == 0) return 1;double num = pow(x, n / 2);return n % 2 == 0 ? num * num : num * num * x;}
};
计算布尔二叉树的值
- 计算布尔二叉树的值
很明显是对二叉树的后序遍历。
class Solution {
public:bool evaluateTree(TreeNode* root) {if (root->val == 1) return 1;if (root->val == 0) return 0;bool left = evaluateTree(root->left);bool right = evaluateTree(root->right);return root->val == 2 ? left | right : left & right;}
};
求根节点到叶节点数字之和
- 求根节点到叶节点数字之和
dfs前序遍历：前序遍历按照根节点、左子树、右子树的顺序遍历二叉树的所有节点，通常用于子节点的状态依赖于父节点状态的题。
class Solution {
public:int sumNumbers(TreeNode* root) {return dfs(root, 0);}int dfs(TreeNode* root, int prevsum){prevsum = prevsum * 10 + root->val; if (root->left == nullptr && root->right == nullptr) return prevsum;int ret = 0;if (root->left) ret += dfs(root->left, prevsum);if (root->right) ret += dfs(root->right, prevsum);return ret;}
};
二叉树剪枝
- 二叉树剪枝
dfs后序遍历：后序遍历按照左子树、右子树、根节点的顺序遍历二叉树的所有节点，通常用于父节点的状态依赖于子节点状态的题目。
class Solution {
public:TreeNode* pruneTree(TreeNode* root) {if (root == nullptr) return nullptr;root->left = pruneTree(root->left);root->right = pruneTree(root->right);if (root->left == nullptr && root->right == nullptr && root->val == 0){return nullptr;}return root;}
};
验证二叉搜索树
- 验证二叉搜索树
二叉搜索树的中序遍历的结果一定是一个严格递增的序列。
可以初始化一个无穷小的全区变量用来记录中序遍历过程中的前驱结点，那么就可以在中序遍历的过程中，先判断是否和前驱结点构成递增序列，然后修改前驱结点为当前结点，传入下一层的递归中。
- 在递归问题中有时可以使用全局变量，从而减少参数的传递；
- 根据条件增加剪枝操作，降低时间复杂度。
class Solution {long prev = LONG_MIN;
public:bool isValidBST(TreeNode* root) {if (root == nullptr) return true;bool left = isValidBST(root->left);if (!left) return false; // 剪枝bool cur = false;if (root->val > prev) cur = true;if (!cur) return false; // 剪枝prev = root->val;bool right = isValidBST(root->right);return left && cur && right;}
};
二叉搜索树中第 K 小的元素
- 二叉搜索树中第 K 小的元素
中序遍历二叉搜索树，找到第k个数即可。
- 在递归问题中使用全局变量可以减少参数的传递。
class Solution {int ret, count;
public:int kthSmallest(TreeNode* root, int k) {count = k;dfs(root);return ret;}void dfs(TreeNode* root){if (root == nullptr) return;dfs(root->left);if (--count == 0) ret = root->val;dfs(root->right);}
};
二叉树的所有路径
- 二叉树的所有路径
回溯问题中往往需要我们恢复现场，例如使用全局变量等。如果参数是局部变量，利用传值传参会在不同的栈帧中拷贝各自的数据，因此不会改变参数，也就不需要我们手动恢复现场了。
class Solution {vector<string> ret;
public:vector<string> binaryTreePaths(TreeNode* root) {string path;dfs(root, path);return ret;}void dfs(TreeNode* root, string path){path += to_string(root->val);if (root->left == nullptr && root->right == nullptr) {ret.push_back(path);return;}path += "->";if (root->left) dfs(root->left, path);if (root->right) dfs(root->right, path);}
};
2、BFS
通常利用队列
first in first out的特点，统计出每层的q.size()以遍历每一层。
N 叉树的层序遍历
- N 叉树的层序遍历
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<Node*> q;q.push(root);while (!q.empty()){vector<int> tmp;int size = q.size();while (size--){tmp.push_back(q.front()->val);for (auto e : q.front()->children){q.push(e);}q.pop(); // 利用父节点把子节点全部插入队列后再删除父节点}ret.push_back(tmp);}return ret;}
};
二叉树的锯齿形层序遍历
- 二叉树的锯齿形层序遍历
遇到二叉树的题一定注意判断有没有左右子节点，不然很容易对空节点解引用。
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>> ret;if (root == nullptr) return ret;queue<TreeNode*> q;q.push(root);int flag = 1;while (!q.empty()){int size = q.size();vector<int> tmp;while (size--){auto t = q.front();tmp.push_back(t->val);if (t->left) q.push(t->left);if (t->right) q.push(t->right);q.pop();}flag *= -1;if (flag > 0) reverse(tmp.begin(), tmp.end());ret.push_back(tmp);}return ret;}
};
二叉树最大宽度
- 二叉树最大宽度
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {vector<pair<TreeNode*, unsigned int>> q; q.push_back({root, 1});unsigned int ret = 0;while (!q.empty()){auto &[x1, y1] = q.front();auto &[x2, y2] = q.back();ret = max(ret, y2 - y1 + 1);vector<pair<TreeNode*, unsigned int>> tmp;for (auto &[a, b] : q){if (a->left) tmp.push_back({a->left, 2 * b});if (a->right) tmp.push_back({a->right, 2 * b + 1});}q = tmp;}return ret;}
};
在每个树行中找最大值
- 在每个树行中找最大值
class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;if (root == nullptr) return ret;queue<TreeNode*> q;q.push(root);while (!q.empty()){int sz = q.size(), m = INT_MIN;while (sz--){auto t = q.front();q.pop();m = max(m, t->val);if (t->left) q.push(t->left);if (t->right) q.push(t->right);}ret.push_back(m);} return ret;}
};
BFS解决最短路问题
迷宫中离入口最近的出口
- 迷宫中离入口最近的出口
class Solution {
public:int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};bool used[101][101] = {};int m = maze.size(), n = maze[0].size(), step = 0;queue<pair<int, int>> q;int row = entrance[0], col = entrance[1];q.push({row, col});used[row][col] = true;while (q.size()){step++; // 向外扩展一层int sz = q.size();while (sz--) {auto [a, b] = q.front();q.pop();for (int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i];if (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == '.' && !used[x][y]){if (x == 0 || x == m - 1 || y == 0 || y == n - 1) return step;used[x][y] = true;q.push({x, y});}}}}return -1;}
};
最小基因变化
- 最小基因变化
class Solution {
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> hash(bank.begin(), bank.end());unordered_set<string> used;const string str = "ACGT";if (startGene == endGene) return 0;if (!hash.count(endGene)) return -1;queue<string> q;q.push(startGene);used.insert(startGene);int step = 0;while (q.size()){step++;int sz = q.size();while (sz--){string s = q.front();q.pop();for (int i = 0; i < 8; i++){string tmp = s;for (int j = 0; j < 4; j++){tmp[i] = str[j];if (tmp == endGene) return step;if (hash.count(tmp) && !used.count(tmp)){used.insert(tmp);q.push(tmp);}}}}}return -1;}
};
3、多源BFS
腐烂的苹果
- 腐烂的苹果
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};queue<pair<int, int>> q;int m, n, ret = 0;bool vis[1001][1001] = {};
public:int rotApple(vector<vector<int> >& grid) {m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if(grid[i][j] == 2) q.push({i, j});while (!q.empty()){int sz = q.size();ret++;while (sz--){auto [a, b] = q.front();q.pop();for (int k = 0; k < 4; k++){int x = a + dx[k], y = b + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1){vis[x][y] = true;q.push({x, y});}}}}for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 1 && !vis[i][j]) return -1;return ret - 1;}
};
4、floodfill
图像渲染
- 图像渲染
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};int col, target, m, n;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if (image[sr][sc] == color) return image;m = image.size(), n = image[0].size();col = color;target = image[sr][sc];dfs(image, sr, sc);return image;}void dfs(vector<vector<int>>& image, int i, int j){image[i][j] = col;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && target == image[x][y]){dfs(image, x, y);}}}
};
岛屿数量
- 岛屿数量
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};bool used[301][301] = {};int m, n, ret = 0;
public:int numIslands(vector<vector<char>>& grid) {m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == '1'){ret++;dfs(grid, i, j);}return ret;}void dfs(vector<vector<char>>& grid, int i, int j){grid[i][j] = '0';for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1'){dfs(grid, x, y);}}}
};
岛屿的最大面积
- 岛屿的最大面积
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};bool used[51][51] = {};int m, n, area, ret = 0;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == 1 && !used[i][j]){area = 0;used[i][j] = true;dfs(grid, i, j);ret = max(ret, area);}return ret;}void dfs(vector<vector<int>>& grid, int i, int j){area++;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] && !used[x][y]){used[x][y] = true;dfs(grid, x, y);}}}
};
被围绕的区域
- 被围绕的区域
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};bool used[201][201] = {};int m, n;
public:void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (i == 0 || i == m - 1 || j == 0 || j == n - 1)if (board[i][j] == 'O')dfs(board, i, j);for (int i = 1; i < m - 1; i++)for (int j = 1; j < n - 1; j++)if (board[i][j] == 'O' && !used[i][j])board[i][j] = 'X';return;}void dfs(vector<vector<char>>& board, int i, int j){used[i][j] = true;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' && !used[x][y]){dfs(board, x, y);}}}
};
太平洋大西洋水流问题
- 太平洋大西洋水流问题
class Solution {vector<vector<int>> ret;int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};int m, n;
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {bool used1[201][201] = {}, used2[201][201] = {};m = heights.size(), n = heights[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){if ((i == 0 || j == 0) && !used1[i][j]) dfs(heights, i, j, used1);if ((i == m - 1 || j == n - 1) && !used2[i][j]) dfs(heights, i, j, used2); }for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (used1[i][j] && used2[i][j])ret.push_back({i, j});return ret;}void dfs(vector<vector<int>>& grid, int i, int j, bool used[][201]){used[i][j] = true;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x < 0 || x >= m || y < 0 || y >= n || used[x][y] || grid[i][j] > grid[x][y]) continue;dfs(grid, x, y, used);}}
};
扫雷游戏
- 扫雷游戏
class Solution {int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1};int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};int m, n;
public:vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {int r = click[0], c = click[1];if (board[r][c] == 'M'){board[r][c] = 'X';return board;}m = board.size(), n = board[0].size();dfs(board, r, c);return board;}void dfs(vector<vector<char>>& board, int r, int c){int count = 0;for (int k = 0; k < 8; k++){int x = r + dx[k], y = c + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') count++;}if (count > 0) board[r][c] = count + '0';else{board[r][c] = 'B';for (int k = 0; k < 8; k++){int x = r + dx[k], y = c + dy[k];if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}}
};
衣橱整理
- 衣橱整理
class Solution {int dx[2] = {0, 1}, dy[2] = {1, 0};bool used[101][101] = {};int m, n, cnt, ret = 0;
public:int wardrobeFinishing(int _m, int _n, int _cnt) {m = _m, n = _n, cnt = _cnt;dfs(0, 0);return ret;}void dfs(int i, int j){ret++;used[i][j] = true;for (int k = 0; k < 2; k++){int x = i + dx[k], y = j + dy[k];if (x < 0 || x >= m || y < 0 || y >= n || !check(x, y) || used[x][y]) continue;dfs(x, y);}}bool check(int x, int y){int tmp = 0;while (x){tmp += x % 10;x /= 10;}while (y){tmp += y % 10;y /= 10;}return tmp <= cnt;}
};
5、记忆化搜索
一些题在dfs的时候会有很多重复的工作，如果在这个过程中能将这些结果记录下来，下次dfs的时候先去查找一下先前是否已经搜索过，这会节省很多不必要的时间。
斐波那契数
- 斐波那契数
class Solution {int memo[31];
public:int fib(int n) {memset(memo, -1, sizeof memo);return dfs(n);}int dfs(int n){if (memo[n] != -1) return memo[n]; // 剪枝if (n == 0 || n == 1) {memo[n] = n;return n;}memo[n] = dfs(n - 1) + dfs(n - 2);return memo[n];}
};
不同路径
- 不同路径
class Solution {int memo[101][101];
public:int uniquePaths(int m, int n) {memset(memo, -1, sizeof memo);return dfs(m, n);}int dfs(int m, int n){if (memo[m][n] != -1) return memo[m][n]; // 剪枝if (m == 1 || n == 1){memo[m][n] = 1;return 1;}memo[m][n] = dfs(m - 1, n) + dfs(m, n - 1);return memo[m][n];}
};
最长递增子序列
- 最长递增子序列
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> memo(n);int ret = 1;for (int i = 0; i < n; i++)ret = max(ret, dfs(nums, n, i, memo));return ret;}int dfs(vector<int>& nums, int n, int pos, vector<int>& memo){if (memo[pos] != 0) return memo[pos]; // 剪枝int ret = 1;for (int i = pos + 1; i < n; i++)if (nums[i] > nums[pos])ret = max(ret, dfs(nums, n, i, memo) + 1);memo[pos] = ret;return ret;}
};
猜数字大小 II
- 猜数字大小 II
class Solution {int memo[201][201];
public:int getMoneyAmount(int n) {return dfs(1, n); // dfs帮我们返回这个区间中能让我们胜利的最小值}int dfs(int left, int right){if (left >= right) return 0;if (memo[left][right] != 0) return memo[left][right];int ret = INT_MAX;for (int head = left; head <= right; head++) // 每个数都作为头节点尝试一遍{int x = dfs(left, head - 1);int y = dfs(head + 1, right);ret = min(ret, head + max(x, y));}memo[left][right] = ret;return ret;}
};
矩阵中的最长递增路径
- 矩阵中的最长递增路径
class Solution {int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};int memo[201][201] = {};int m, n, ret = 0;
public:int longestIncreasingPath(vector<vector<int>>& matrix) {m = matrix.size(), n = matrix[0].size();for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)ret = max(ret, dfs(matrix, i, j));return ret;}int dfs(vector<vector<int>>& matrix, int i, int j){if (memo[i][j] != 0) return memo[i][j]; // 剪枝int ret = 1;for (int k = 0; k < 4; k++){int x = i + dx[k], y = j + dy[k];if (x < 0 || x >= m || y < 0 || y >= n || matrix[i][j] >= matrix[x][y])continue;ret = max(ret, dfs(matrix, x, y) + 1);}memo[i][j] = ret;return ret;}
};
本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
