20天 hot 100 速通计划-day11

图论

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] 的值为 '0' 或 '1'

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
       //剪枝：空网格直接返回
        if (!grid.size()) return 0;
      //获取行列数
        int rows = grid.size();
        int cols = grid[0].size();

      //初始化岛屿数
        int count = 0;
      
      //遍历所有格子
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
              //如果遇到陆地（'1'），则进行深度优先搜索（DFS）
              //将其和其相邻的陆地全部标记为已访问（将'1'改成'0'），同时将岛屿数量加一
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
private:
  //深度优先搜索（DFS）作用：将其和其相邻的陆地全部标记为已访问（将'1'改成'0'）
  //参返分析：输入待遍历的表格和当前所在行列
  //终止条件：
  // 结构终止：当前行列超出边界
  // 业务终止：遇见水
  //单层逻辑：将当前格子设为水，表示已访问
    void dfs(vector<vector<char>>& grid, int row, int col) {
        int rows = grid.size();
        int cols = grid[0].size();
        if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == '0') {
            return;
        }
      //将当前格子设为水，表示已访问
        grid[row][col] = '0';
      //递归处理上下左右
        dfs(grid, row - 1, col);
        dfs(grid, row + 1, col);
        dfs(grid, row, col - 1);
        dfs(grid, row, col + 1);
    }
};

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。

示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] 仅为 0、1 或 2

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
      //获取行列
        int rows = grid.size();
        int cols = grid[0].size();
      //初始化腐烂所需天数
        int days = 0;
        
      //定义四个方向向量，用于表示上下左右四个方向（纯技巧）
      //四个方向向量 {dirX, dirY} 表示了在二维平面中四个方向的移动
      //其中 dirX 表示在 x 轴上的移动，dirY 表示在 y 轴上的移动。
      //例如：
      //{-1, 0} 表示向上移动一格,{1, 0} 表示向下移动一格
      //{0, -1} 表示向左移动一格,{0, 1} 表示向右移动一格
        vector<int> dirX = {-1, 0, 1, 0};
        vector<int> dirY = {0, -1, 0, 1};
        
      //初始化队列，遍历所有格子，将所有腐烂的橘子加入队列
        queue<pair<int, int>> rottenQueue;
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(grid[i][j] == 2) {
                    rottenQueue.push({i, j});
                }
            }
        }
        
				//形似层序遍历
        while(!rottenQueue.empty()) {
            int size = rottenQueue.size();
            
            for(int i = 0; i < size; i++) {
                pair<int, int> point = rottenQueue.front();
                rottenQueue.pop();
                
              //获取烂橘子坐标
                int x = point.first, y = point.second;
                
                // 腐烂周围的新鲜橘子，引入 dirX 和 dirY 以后，就能用一个 for 循环表示四种移动
                for(int j = 0; j < 4; j++) {
                    int newX = x + dirX[j];
                    int newY = y + dirY[j];
                    
                    // 若周围的位置合法且为新鲜橘子，则标记为腐烂橘子，并将其加入队列
                    if(newX >= 0 && newX < rows && newY >= 0 && newY < cols 
                       && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        rottenQueue.push({newX, newY});
                    }
                }
            }
            
            if(!rottenQueue.empty()) {  // 还有新的腐烂橘子，增加一天
                days++;
            }
        }
        
        // 检查是否还有新鲜橘子
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        
        return days;
    }
};

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

本质上就是拓扑排序判断是否成环，用深度优先搜索（DFS）来实现拓扑排序，纯技巧，可作为原子操作

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 构建图的邻接表表示
        vector<vector<int>> graph(numCourses);
        for (auto& p : prerequisites) {
            graph[p[0]].push_back(p[1]);
        }
        
        // 记录每个节点的访问状态
        vector<int> visited(numCourses, 0);
        
        // 对每个节点进行深度优先搜索
        for (int i = 0; i < numCourses; ++i) {
            if (!dfs(graph, visited, i)) {
                return false;
            }
        }
        
        return true;
    }
    
    bool dfs(vector<vector<int>>& graph, vector<int>& visited, int cur) {
        // 如果当前节点已被访问，说明存在环，返回 false
        if (visited[cur] == 1) {
            return false;
        }
        // 如果当前节点已被其他节点访问，无需重复搜索，直接返回 true
        if (visited[cur] == -1) {
            return true;
        }
        
        // 设置当前节点为已访问
        visited[cur] = 1;
        
        // 搜索当前节点的邻居节点
        for (int neighbor : graph[cur]) {
            if (!dfs(graph, visited, neighbor)) {
                return false;
            }
        }
        
        // 回溯，将当前节点设置为已访问其他节点
        visited[cur] = -1;
        
        return true;
    }
};

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

提示：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数 总计 不超过 3 * 104 次

类似于 LRU，纯技巧构造数据结构

class TrieNode {
public:
    bool is_end;  // 标记当前节点是否是一个单词的结尾
    TrieNode* children[26];  // 存放所有可能的字母子节点
    
    TrieNode() {
        is_end = false;  // 默认不是单词结尾
        for (int i = 0; i < 26; ++i) {
            children[i] = nullptr;  // 初始化子节点为空指针
        }
    }
};

class Trie {
public:
    TrieNode* root;  // 根节点
    
    Trie() {
        root = new TrieNode();  // 创建一个空的trie树，只有一个根节点
    }
    
    void insert(string word) {
        TrieNode* node = root;  // 从根节点开始
        for (int i = 0; i < word.length(); ++i) {  // 遍历单词的每个字母
            int index = word[i] - 'a';  // 计算字母的索引（a-z对应0-25）
            if (node->children[index] == nullptr) {  // 如果子节点为空，表示以当前字母开头的单词还没有加入trie树
                node->children[index] = new TrieNode();  // 创建一个新的子节点
            }
            node = node->children[index];  // 继续进入下一个字母的子节点
        }
        node->is_end = true;  // 将最后一个字母所在节点标记为单词结尾
    }
    
    bool search(string word) {
        TrieNode* node = root;  // 从根节点开始
        for (int i = 0; i < word.length(); ++i) {  // 遍历单词的每个字母
            int index = word[i] - 'a';  // 计算字母的索引（a-z对应0-25）
            if (node->children[index] == nullptr) {  // 如果子节点为空，表示以当前字母开头的单词不存在
                return false;
            }
            node = node->children[index];  // 继续进入下一个字母的子节点
        }
        return node->is_end;  // 判断最后一个字母所在节点是否是一个单词的结尾
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;  // 从根节点开始
        for (int i = 0; i < prefix.length(); ++i) {  // 遍历前缀的每个字母
            int index = prefix[i] - 'a';  // 计算字母的索引（a-z对应0-25）
            if (node->children[index] == nullptr) {  // 如果子节点为空，表示以当前字母开头的单词不存在
                return false;
            }
            node = node->children[index];  // 继续进入下一个字母的子节点
        }
        return true;  // 前缀匹配成功
    }
};

回溯

46. 全排列

给定一个不含重复数字的数组 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]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

回溯三部曲

回溯法可解决问题都可抽象为树，回溯的本质是优雅地枚举

• for 循环：横向遍历可以做出的选择
• 递归：纵向遍历，表示做出选择后的状态转移

1. 参返分析：回溯返回值一般为 void，带放回，引入标记已选择元素的 used 数组作参数，同时需要将元素集合作参数
2. 终止条件：如果路径的长度等于数组的长度，说明已经找到一个符合条件的结果
3. 遍历过程：带放回，故每层都从 0 开始搜索，需要引入 used 数组作为已选择标记。回溯每一个位置可以选择的数字
   • 递归
     1. 如果该数字已经被使用过，继续查找下一个数字
     2. 如果该数字未被使用过，标记该数字已经使用过，将该数字加入路径中
   • 回溯
     1. 将数字移出路径
     2. 将数字的访问标记去除

class Solution {
public:
  //存放符合条件的所有结果的集合
    vector<vector<int>> res;
  //存放符合条件的单一结果
    vector<int> path;
    void backtrack(vector<int>& nums, vector<bool>& used){
        // 如果路径的长度等于数组的长度，说明已经找到一个符合条件的结果，将其加入结果集合中
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }
        // 回溯每一个位置可以选择的数字
        for(int i = 0; i < nums.size(); i++){
            // 如果该数字已经被使用过，继续查找下一个数字
            if(used[i]) continue;
            // 标记该数字已经使用过
            used[i]=true;
            // 将该数字加入路径中
            path.push_back(nums[i]);
            // 开始对剩下的数字进行回溯
            backtrack(nums, used);
            // 回溯完之后，需要将该数字从路径中移除，并取消标记
            path.pop_back();
            used[i]=false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        // 初始化所有数字的使用情况，默认为false表示未使用过
        vector<bool> used(nums.size(), false);
        // 开始回溯
        backtrack(nums, used);
        return res;
    }
};

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Scala编程语言day1
• 2024-1-13 DAY4
• 算法学习Day26组合总和、分割回文串
• 11-函数进阶-参数类型
• 7 - for循环while循环 1+2+...+100和
• 【GDKOI 2024 TG Day2】染色（set） 题解
• D25XB100-ASEMI家用电器整流桥D25XB100
• 2024-1-12 DAY3
• UCB Data100：数据科学的原理和技巧：第十一章到第十五章

hot 100 day 11hot 100 day 11 hot 100 day 03 hot 100 day 18 hot 100 day 10 hot 100 day 09 hot 100 day 15 hot 100 day 04 hot 100 day 08 hot 100 day 14 hot 100 day 06