【LeetCode】力扣刷题热题100道（31-35题）附源码 搜索二维矩阵 岛屿数量 腐烂的橙子 课程表 实现 Trie (前缀树)（C++）

一、搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

可以使用 从右上角开始搜索 的方法来有效地找到目标值。

1. 选择起始位置： 从矩阵的右上角开始。假设我们当前的位置是 matrix[0][n-1]，其中 n 是列数。
2. 逐步搜索：
   • 如果当前元素等于目标值，返回 true。
   • 如果当前元素大于目标值，说明目标值可能出现在当前元素的左边，因此我们向左移动一列。
   • 如果当前元素小于目标值，说明目标值可能出现在当前元素的下方，因此我们向下移动一行。
3. 结束条件： 如果超出了矩阵的边界，说明没有找到目标值，返回 false。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix[0].empty()) return false;int m = matrix.size();     // 行数int n = matrix[0].size();  // 列数// 从右上角开始int row = 0;int col = n - 1;while (row < m && col >= 0) {if (matrix[row][col] == target) {return true;  // 找到目标值} else if (matrix[row][col] > target) {col--;  // 当前元素大于目标值，向左移动} else {row++;  // 当前元素小于目标值，向下移动}}return false;  // 没有找到目标值}
};

• 初始位置：从矩阵的右上角 matrix[0][n-1] 开始。
• 移动规则：
  • 如果当前元素等于目标值，则返回 true。
  • 如果当前元素大于目标值，则移动到左边一列。
  • 如果当前元素小于目标值，则移动到下方一行。
• 边界条件：当行数或列数超出范围时，结束搜索。

二、岛屿数量

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

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

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

• DFS 遍历：从每个尚未访问的陆地单元格开始，使用 DFS 遍历其所有相邻的陆地单元格，将它们标记为已访问。每次发现一个新的未被访问的陆地，就说明发现了一个新的岛屿。

• 标记访问：为了避免重复计算同一个岛屿，需要在遍历过程中将已经访问过的陆地标记为水（'0'），这样就不会再次访问到它。

• 岛屿计数：每当我们从一个未访问的陆地开始 DFS 时，岛屿数加一。

• 对于每一个格子，如果它是陆地 ('1') 且未被访问，则从该格子开始进行 DFS，将与之相连的所有陆地格子标记为已访问，并将岛屿数量加一。
• 遍历所有格子，最终得到岛屿的数量。
• 对于一个陆地格子（'1'），递归地向上下左右四个方向扩展，找到与它相连的所有陆地并将其标记为水（'0'）。
• 这样做的目的是确保每个岛屿的陆地只被计数一次。

class Solution {
public:void dfs(vector<vector<char>>& grid, int i, int j) {// 边界条件：如果当前格子越界或已经是水（'0'），则返回if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {return;}// 将当前陆地格子标记为水，表示已访问grid[i][j] = '0';// 递归四个方向dfs(grid, i + 1, j);  // 向下dfs(grid, i - 1, j);  // 向上dfs(grid, i, j + 1);  // 向右dfs(grid, i, j - 1);  // 向左}int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;int numIslands = 0;// 遍历整个网格for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {// 找到一个未访问的陆地，启动 DFSif (grid[i][j] == '1') {numIslands++;  // 发现新的岛屿dfs(grid, i, j);  // 使用 DFS 标记整个岛屿}}}return numIslands;}
};

• DFS 函数：dfs 用来递归访问与当前格子相连的所有陆地格子，并将它们标记为水（'0'）。

  • 参数 i, j 表示当前正在处理的格子坐标。
  • 在函数内部，首先检查是否越界或是否已经是水（'0'），如果是则直接返回。
  • 然后标记当前格子为水，并递归检查四个方向（上下左右）。

• 主函数：numIslands 遍历整个二维网格，发现每个未访问的陆地时，调用 dfs 来标记所有相连的陆地，从而确保每个岛屿只计算一次。

• 边界条件：如果网格为空，直接返回 0。

三、腐烂的橙子

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

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

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

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

 

class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();// 记录腐烂的橘子的位置queue<pair<int, int>> rotten;int freshCount = 0;  // 记录新鲜橘子的数量// 初始化队列和新鲜橘子数量for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 2) {rotten.push({i, j});} else if (grid[i][j] == 1) {freshCount++;}}}// 如果没有新鲜橘子，直接返回 0if (freshCount == 0) return 0;// 四个方向vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};int minutes = 0;// 开始 BFSwhile (!rotten.empty()) {int size = rotten.size();bool rottedThisRound = false;  // 记录这一轮是否有橘子腐烂for (int i = 0; i < size; ++i) {auto [x, y] = rotten.front();rotten.pop();// 四个方向扩展for (auto& dir : directions) {int nx = x + dir.first;int ny = y + dir.second;// 如果新位置在网格内且是新鲜橘子if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {grid[nx][ny] = 2;  // 将新鲜橘子腐烂rotten.push({nx, ny});  // 加入队列freshCount--;  // 减少新鲜橘子的数量rottedThisRound = true;}}}// 如果这一轮有橘子腐烂，时间增加if (rottedThisRound) {minutes++;}}// 如果还有新鲜橘子，返回 -1return freshCount == 0 ? minutes : -1;}
};

• 初始化：
  • 我们先遍历网格，找到所有腐烂的橘子，并将其加入队列。同时，我们统计新鲜橘子的数量。
• BFS 过程：
  • 我们从腐烂的橘子开始，逐层扩展，检查每个腐烂橘子周围的四个方向。
  • 如果发现相邻位置是新鲜橘子（值为 1），我们就把它变成腐烂的橘子（值改为 2），并将其加入队列，继续扩展。
  • 每次扩展都意味着时间增加一分钟。
• 结束条件：
  • 如果在 BFS 完成后还有新鲜橘子（freshCount > 0），说明不能完全腐烂所有橘子，返回 -1。
  • 否则，返回所需的分钟数。

四、课程表

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

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

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

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

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegree(numCourses, 0);  // 记录每个课程的入度vector<vector<int>> graph(numCourses);  // 邻接表表示图// 构建图和入度数组for (const auto& prereq : prerequisites) {int course = prereq[0];  // 需要学习的课程int pre = prereq[1];     // 先修课程graph[pre].push_back(course);  // 将 course 加入 pre 的邻接表indegree[course]++;  // course 的入度加 1}// 使用队列存储入度为 0 的课程queue<int> q;for (int i = 0; i < numCourses; ++i) {if (indegree[i] == 0) {q.push(i);  // 将入度为 0 的课程加入队列}}int count = 0;  // 记录已修课程的数量while (!q.empty()) {int course = q.front();q.pop();count++;// 对当前课程的所有后续课程（即它的邻接课程）进行处理for (int nextCourse : graph[course]) {indegree[nextCourse]--;  // 当前课程修完，减去下一个课程的入度if (indegree[nextCourse] == 0) {q.push(nextCourse);  // 如果下一个课程的入度为 0，加入队列}}}// 如果修完的课程数量等于总课程数，则可以完成所有课程return count == numCourses;}
};

• 构建图和入度数组：
  • 我们首先创建一个 graph 数组来存储图的邻接表，并创建一个 indegree 数组来记录每个课程的入度（即每个课程有多少先修课程）。
  • 然后，我们根据 prerequisites 数组来构建图，并更新每个课程的入度。
• 拓扑排序：
  • 我们初始化一个队列 q，将所有入度为 0 的课程加入队列。
  • 逐个从队列中取出课程，修完后，将它的邻接课程的入度减 1。如果某个邻接课程的入度变为 0，则将它加入队列。
• 判断是否完成所有课程：
  • 最后，我们检查已修的课程数量 count 是否等于总课程数 numCourses。如果相等，说明没有环路，返回 true；否则，返回 false。

五、实现 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 。

class Trie {
private:struct TrieNode {unordered_map<char, TrieNode*> children;bool isWord;TrieNode() : isWord(false) {}};TrieNode* root;public:// 构造函数，初始化 Trie 树Trie() {root = new TrieNode();}// 向 Trie 插入一个字符串void insert(string word) {TrieNode* node = root;for (char c : word) {// 如果当前字符的子节点不存在，则创建一个新的节点if (node->children.find(c) == node->children.end()) {node->children[c] = new TrieNode();}node = node->children[c];}// 标记字符串结束的节点node->isWord = true;}// 查找字符串是否存在于 Trie 中bool search(string word) {TrieNode* node = root;for (char c : word) {if (node->children.find(c) == node->children.end()) {return false;  // 如果有字符没有找到对应节点，返回 false}node = node->children[c];}// 如果到达字符串结尾并且是一个完整的单词，返回 truereturn node->isWord;}// 检查是否有任何单词以 prefix 为前缀bool startsWith(string prefix) {TrieNode* node = root;for (char c : prefix) {if (node->children.find(c) == node->children.end()) {return false;  // 如果有字符没有找到对应节点，返回 false}node = node->children[c];}// 如果遍历完整个前缀，说明 Trie 中有以 prefix 为前缀的单词return true;}
};/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

• TrieNode 结构体：每个 TrieNode 代表一个树节点，包含：

  • children：一个哈希表，键是字符，值是指向子节点的指针。这个哈希表用于存储当前节点的所有子节点。
  • isWord：一个布尔值，标记当前节点是否为一个单词的结束。

• Trie 构造函数：创建一个空的根节点 root。

• insert(word)：

  • 从根节点开始，逐个字符遍历 word。
  • 如果某个字符的子节点不存在，则创建一个新的子节点。
  • 最后，将最后一个字符的 isWord 标记为 true，表示这是一个完整的单词。

• search(word)：

  • 从根节点开始，逐个字符遍历 word。
  • 如果在任何字符位置找不到对应的子节点，则返回 false。
  • 如果遍历结束并且当前节点的 isWord 为 true，说明找到了该单词，返回 true。

• startsWith(prefix)：

  • 从根节点开始，逐个字符遍历 prefix。
  • 如果在某个字符位置找不到对应的子节点，则返回 false。
  • 如果能够遍历完前缀的所有字符，说明存在以该前缀为开始的单词，返回 true。