【算法】DFS、BFS、floodfill、记忆化搜索、BFS拓扑排序

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

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

单词接龙

• 单词接龙

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> hash(wordList.begin(), wordList.end());
        unordered_set<string> used;
        queue<string> q;
        if (!hash.count(endWord)) return 0;
        q.push(beginWord);
        used.insert(beginWord);
        int ret = 1; // 最初beginWord也算一个单词
        while (q.size())
        {
            ret++;
            int sz = q.size();
            while (sz--)
            {
                string str = q.front();
                q.pop();
                for (int i = 0; i < beginWord.size(); i++)
                {
                    string tmp(str);
                    for (char ch = 'a'; ch <= 'z'; ch++)
                    {
                        tmp[i] = ch;
                        if (tmp == endWord) return ret;
                        if (hash.count(tmp) && !used.count(tmp))
                        {
                            used.insert(tmp);
                            q.push(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

为高尔夫比赛砍树

• 为高尔夫比赛砍树

class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    int m, n, ret = 0;
public:
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size(), n = forest[0].size();
        map<int, pair<int, int>> hash;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (forest[i][j] > 1)
                    hash[forest[i][j]] = {i, j};
        int bx = 0, by = 0;
        for (auto &[a, b] : hash)
        {
            int step = bfs(forest, bx, by, b.first, b.second);
            if (step == -1) return -1;
            ret += step;
            bx = b.first;
            by = b.second;
        }
        return ret;
    }
    int bfs(vector<vector<int>>& forest, int bx, int by, int ex, int ey)
    {
        if (bx == ex && by == ey) return 0;
        int ret = 0;
        queue<pair<int, int>> q;
        bool used[51][51] = {};
        q.push({bx, by});
        used[bx][by] = true;
        while (q.size())
        {
            ret++;
            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 == ex && y == ey) return ret;
                    if (x >= 0 && x < m && y >= 0 && y < n && forest[x][y] && !used[x][y])
                    {
                        used[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        return -1;
    }
};

class Solution {
    int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
    int m, n, ret = 0;
public:
    int cutOffTree(vector<vector<int>>& f) {
        m = f.size(), n = f[0].size();
        vector<pair<int, int>> trees;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (f[i][j] > 1) 
                    trees.push_back({i, j});
        sort(trees.begin(), trees.end(), 
            [&f](const pair<int, int>& p1, const pair<int, int>& p2)
            { return f[p1.first][p1.second] < f[p2.first][p2.second];});
        
        int bx = 0, by = 0;
        for (auto [a, b] : trees)
        {
            int step = bfs(f, bx, by, a, b);
            if (step == -1) return -1;
            ret += step;
            bx = a, by = b;
        }
        return ret;
    }
    int bfs(vector<vector<int>>& f, int bx, int by, int ex, int ey)
    {
        // 处理边界情况
        if (bx == ex && by == ey) return 0;
        queue<pair<int, int>> q;
        bool used[51][51] = {};
        q.push({bx, by});
        used[bx][by] = true;
        int ret = 0;
        while (q.size())
        {
            ret++;
            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 == ex && y == ey) return ret;
                    if (x < 0 || x >= m || y < 0 || y >= n || !f[x][y] || used[x][y])
                        continue;
                    used[x][y] = true;
                    q.push({x, y});
                }
            }
        }
        return -1;
    }
};

4、多源BFS

01 矩阵

• 01 矩阵

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> ret(m, vector<int>(n, -1));
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (mat[i][j] == 0)
                {
                    q.push({i, j});
                    ret[i][j] = 0;
                }
        while (q.size())
        {
            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 && ret[x][y] == -1)
                {
                    ret[x][y] = ret[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return ret;
    }
};

飞地的数量

• 飞地的数量

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        bool used[501][501] = {};
        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 (grid[i][j] == 1) 
                    {
                        q.push({i, j});
                        used[i][j] = true;
                    }
        while (q.size())
        {
            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 && grid[x][y] && !used[x][y])
                {
                    used[x][y] = true;
                    q.push({x, y});
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] && !used[i][j])
                    ret++;
        return ret;
    }
};

地图中的最高点

• 地图中的最高点

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        int m = isWater.size(), n = isWater[0].size();
        queue<pair<int, int>> q;
        vector<vector<int>> ret(m, vector<int>(n, -1));
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (isWater[i][j] == 1)
                {
                    q.push({i, j});
                    ret[i][j] = 0;
                }
        while (q.size())
        {
            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 && ret[x][y] == -1)
                {
                    ret[x][y] = ret[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return ret;
    }
};

地图分析

• 地图分析

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        int n = grid.size();
        queue<pair<int, int>> q;
        bool used[101][101] = {};
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1)
                    q.push({i, j});
        if (q.size() == n * n || q.size() == 0) return -1;
        int ret = -1;
        while (q.size())
        {
            ret++;
            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 < n && y >= 0 && y < n && !grid[x][y] && !used[x][y])
                    {
                        used[x][y] = true;
                        q.push({x, y});
                    }
                }
            }
        }
        return ret;
    }
};

腐烂的苹果

• 腐烂的苹果

class Solution {
public:
    int rotApple(vector<vector<int> >& grid) {
        int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 2)
                    q.push({i, j});
        int min = -1;
        while (q.size())
        {
            min++;
            int sz = q.size();
            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 && grid[x][y] == 1)
                    {
                        grid[x][y] = 2;
                        q.push({x, y});
                    }
                }
            }
        }
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) 
                    return -1;
        return min;
    }
};

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

6、记忆化搜索

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

7、BFS解决拓扑排序

| 拓扑排序简单介绍：

• 拓扑排序是对有向无环图（DAG）的顶点进行排序的一种算法，它可以将图中的顶点按照一定的顺序排列，使得对于图中的任意一条有向边(u, v)，顶点u在排序中的位置都在顶点v之前；
• 拓扑排序的基本思想是选择入度为 0 的顶点，并将其输出，然后删除该顶点及其所有出边，重复这个过程，直到所有顶点都被输出或者图中存在环（如果存在环，则无法进行拓扑排序）；
• 简单总结就是找到做事情的先后顺序，并且拓扑排序的结果可能不是唯一的。

| 主要应用场景：

• 检测有向图中的环：若有向图能够进行拓扑排序，那么它必然是无环的；反之，若无法完成拓扑排序，就表明图中存在环；
• 确定任务执行顺序：对于有依赖关系的任务集合，拓扑排序可以给出一个合理的执行顺序，保证在执行某个任务之前，其所有前置任务都已完成；
• 计算最短路径：在有向无环图（DAG）中，拓扑排序可以用于高效地计算单源最短路径。通过按照拓扑排序的顺序依次处理顶点，可以保证在计算某个顶点的最短路径时，其所有前驱顶点的最短路径已经计算完成。

课程表

• 课程表

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges; // 邻接表存图
        vector<int> in(numCourses); // 记录每一个点的入度
        queue<int> q;
        // 1.建图
        for (auto &e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        // 2.将所有入度为0的点加入到队列中
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);
        // 3.BFS
        while (q.size())
        {
            int t = q.front();
            q.pop();
            for (auto e : edges[t])
            {
                in[e]--;
                if (in[e] == 0)
                    q.push(e);
            }
        }
        for (auto e : in)
            if (e) return false;
        return true;
    }
};

课程表 II

• 课程表 II

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> edges(numCourses);
        vector<int> in(numCourses), ret;
        queue<int> q;
        for (auto &e : prerequisites)
        {
            int a = e[0], b = e[1];
            edges[b].push_back(a);
            in[a]++;
        }
        for (int i = 0; i < numCourses; i++)
            if (in[i] == 0)
                q.push(i);
        while (q.size())
        {
            int t = q.front();
            ret.push_back(t);
            q.pop();
            for (int e : edges[t])
            {
                if (--in[e] == 0)
                    q.push(e);
            }
        }
        if (ret.size() == numCourses) return ret;
        else return {};
    }
};

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