6 一切皆可搜索 - 《Follow leetcode 101》

6.1 算法解释

深度优先搜索和广度优先搜索是两种最常见的优先搜索方法，它们被广泛地运用在图和树等结构中进行搜索。

6.2 深度优先搜索

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。
深度优先搜索也可以用来检测环路：记录每个遍历过的节点的父节点，若一个节点被再次遍历且父节点不同，则说明有环。我们也可以用之后会讲到的拓扑排序判断是否有环路，若最后存在入度不为零的点，则说明有环。
有时我们可能会需要对已经搜索过的节点进行标记，以防止在遍历时重复搜索某个节点，这
种做法叫做状态记录或记忆化（memoization）。

6.3 岛屿的最大面积

695. 岛屿的最大面积Mid

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
示例 1：
输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出：6 解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：
输入：grid = [[0,0,0,0,0,0,0,0]] 输出：0

int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int x = grid.size();
        int y = x == 0 ? 0 : grid[0].size();
        vector<vector<bool>> visited(x, vector<bool>(y, false));
        stack<pair<int, int>> st;
        int sum = 0, res = 0;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                visited[i][j] = true;
                if (grid[i][j] == 1) {
                    sum++;
                    st.push(make_pair(i, j));
                }
                while (!st.empty()) {
                    pair<int, int> tmp = st.top();
                    st.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = tmp.first + dx[k];
                        int ny = tmp.second + dy[k];
                        if (nx >= 0 && nx < x && ny >= 0 && ny < y 
                            && grid[nx][ny] == 1 && false == visited[nx][ny]) {
                                visited[nx][ny] = true;
                                sum++;
                                st.push(make_pair(nx, ny));
                            }
                    }
                }
                res = max(res, sum);
                sum = 0;
            }
        }
        return res;
    }
};

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int x = grid.size();
        int y = x == 0 ? 0 : grid[0].size();
        int res = 0;
        vector<vector<bool>> visited(x, vector<bool>(y, false));
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                res = max(res, dfs(grid, visited, i, j));
            }
        }
        return res;
    }
    int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (grid[x][y] == 0)
            return 0;
        visited[x][y] = true;
        int res = 1;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && visited[nx][ny] == false) {
                res += dfs(grid, visited, nx, ny);
            }
        }
        return res;
    }
};

class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int x = grid.size();
        int y = x == 0 ? 0 : grid[0].size();
        int res = 0;
        int sum = 0;
        vector<vector<bool>> visited(x, vector<bool>(y, false));
        queue<pair<int, int>> q;
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                visited[i][j] = true;
                if (grid[i][j] == 1) {
                    sum++;
                    q.push(make_pair(i, j));
                }
                while (!q.empty()) {
                    pair<int, int> tmp = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int nx = tmp.first + dx[k];
                        int ny = tmp.second + dy[k];
                        if (nx >= 0 && nx < x && ny >= 0 && ny < y && grid[nx][ny] == 1 && visited[nx][ny] == false) {
                            visited[nx][ny] = true;
                            sum++;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
                res = max(res, sum);
                sum = 0;
            }
        }
        return res;
    }
};

934. 最短的桥

难度中等242
在给定的二维二进制数组 A 中，存在两座岛。（岛是由四面相连的 1 形成的一个最大组。）
现在，我们可以将 0 变为 1，以使两座岛连接起来，变成一座岛。
返回必须翻转的 0 的最小数目。（可以保证答案至少是 1 。）

示例 1：
输入：A = [[0,1],[1,0]] 输出：1
示例 2：
输入：A = [[0,1,0],[0,0,0],[0,0,1]] 输出：2
示例 3：
输入：A = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]] 输出：1

class Solution {
    public:
        vector<int> direction{-1, 0, 1, 0, -1};
    // 主函数
    int shortestBridge(vector<vector<int>> &grid)
    {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> points; // dfs寻找第一个岛屿，并把1全部赋值为2
        bool flipped = false;
        for (int i = 0; i < m; ++i)
        {
            if (flipped)
                break;
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    dfs(points, grid, m, n, i, j);
                    flipped = true;
                    break;
                }
            }
        }
        // bfs寻找第二个岛屿，并把过程中经过的0赋值为2
        int x, y;
        int level = 0;
        while (!points.empty())
        {
            ++level;
            int n_points = points.size();
            while (n_points--)
            {
                auto [r, c] = points.front();
                points.pop();
                for (int k = 0; k < 4; ++k)
                {
                    x = r + direction[k], y = c + direction[k + 1];
                    if (x >= 0 && y >= 0 && x < m && y < n)
                    {
                        if (grid[x][y] == 2)
                        {
                            continue;
                        }
                        if (grid[x][y] == 1)
                        {
                            return level;
                        }
                        points.push({x, y});
                        grid[x][y] = 2;
                    }
                }
            }
        }
        return 0;
    }
    // 辅函数
    void dfs(queue<pair<int, int>> &points, vector<vector<int>> &grid, int m, int n, int i, int j)
    {
        if (i < 0 || j < 0 || i == m || j == n || grid[i][j] == 2)
        {
            return;
        }
        if (grid[i][j] == 0)
        {
            points.push({i, j});
            return;
        }
        grid[i][j] = 2;
        dfs(points, grid, m, n, i - 1, j);
        dfs(points, grid, m, n, i + 1, j);
        dfs(points, grid, m, n, i, j - 1);
        dfs(points, grid, m, n, i, j + 1);
    }
};

46. 全排列

难度中等1964
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> item;

    vector<vector<int>> permute(vector<int>& nums) {
        if(nums.size() < 1) return res;
        vector<bool> visited(nums.size(),false);
        dfs(visited,nums);
        return res;
    }

    void dfs(vector<bool>& visited,vector<int>& nums) {
        if(item.size() == nums.size()) {
            res.push_back(item);
            return;
        }

        for(int i = 0 ; i < nums.size() ; i++) {
            if(visited[i])
                continue;
            item.push_back(nums[i]);
            visited[i] = true;
            dfs(visited,nums);
            item.pop_back();
            visited[i] = false;
        }
    }
};

17. 电话号码的字母组合

难度中等1863
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23” 输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：
输入：digits = “” 输出：[]
示例 3：
输入：digits = “2” 输出：[“a”,”b”,”c”]

class Solution {
public:
    vector<string> board = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    string item;

    vector<string> letterCombinations(string digits) {
        if (digits.length() == 0)
            return res;

        dfs(digits, 0);
        return res;
    }

    void dfs(const string& digits, int index)
    {
        // 1、截止条件
        if (index == digits.size())
        {
            res.push_back(item);
            return;
        }

        int num = digits[index] - '0';
        // 2、遍历候选节点
        for (int i = 0; i < board[num].length(); i++)
        {
            item.push_back(board[num][i]);
            dfs(digits, index + 1);
            item.pop_back();
        }

    }
};

22. 括号生成

难度中等2588
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3 输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：
输入：n = 1 输出：[“()”]

class Solution {
public:
    vector<string> res;
    string item;
    vector<string> generateParenthesis(int n) {   
        backtrace(n, n);
        return res;
    }

    void backtrace(int l, int r) {
        if (l == 0 && r == 0) {
            res.push_back(item);
            return;
        }

        if (l > r) {
            return;
        }

        if (l > 0) {
            item.push_back('(');
            backtrace(l - 1, r);
            item.pop_back();
        }

        if (r > 0) {
            item.push_back(')');
            backtrace(l , r - 1);
            item.pop_back();
        }
    }
};

77. 组合

难度中等956
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> item;
    vector<vector<int>> combine(int n, int k) {
        backtrace(1, n, k);
        return res;
    }

    void backtrace(int index, int n, int k) {
        if (item.size() == k) {
            res.push_back(item);
            return;
        }

        for (int i = index; i <= n; i++) {
            item.push_back(i);
            backtrace(i + 1, n, k);
            item.pop_back();
        }
    }
};

class Solution {
public:
    vector<vector<int>> res;
    vector<int> item;
    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }

    void backtracking(int n, int k, int startIndex) {
        if (item.size() == k) {
            res.push_back(item);
            return;
        }
        //剪枝
        for (int i = startIndex; i <= n - k + 1 + item.size(); i++) {
            item.push_back(i);
            backtracking(n, k, i + 1);
            item.pop_back();
        }
    }
};

79. 单词搜索

难度中等1278

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED” 输出：true

示例 2：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE” 输出：true
示例 3：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB” 输出：false

class Solution {
public:
    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (word[0] == board[i][j]) {
                    if (dfs(board, visited, word, i, j, 0))
                        return true;
                }
            }
        }

        return false;
    }

    bool dfs(vector<vector<char>>& board, vector<vector<bool>>& visited, string& word, int row, int col, int index) {
        if (index == word.length())
            return true;

        if (row < 0 || col < 0 || row >= board.size() || col >= board[0].size())
            return false;

        if (visited[row][col])
            return false;

        if (board[row][col] != word[index])
            return false;

        visited[row][col] = true;
        for (int i = 0; i < 4; i++) {
            int nx = dx[i] + row;
            int ny = dy[i] + col;
            if (dfs(board, visited, word, nx, ny, index + 1))
                return true;
        }
        visited[row][col] = false;
        return false;
    }
};

39. 组合总和

难度中等1927
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []

class Solution {
public:
    vector<vector<int>> res;
    vector<int> item;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }

    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum > target) return;
        if (sum == target) {
            res.push_back(item);
            return;
        }

        for (int i = startIndex; i < candidates.size(); i++) {
            item.push_back(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            item.pop_back();
        }
    }
};