【算法】DFS、Floodfill、记忆化搜索

_小羊_

发布于 2025-03-29 09:45:31

6600

代码可运行

文章被收录于专栏：C++C++

运行总次数：0

代码可运行

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、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;
    }
};

3、记忆化搜索

一些题在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;
    }
};

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-03-28，如有侵权请联系 cloudcommunity@tencent.com 删除

int