一、搜索二維矩陣

編寫一個高效的算法來搜索?m?x?n?矩陣?matrix?中的一個目標(biāo)值?target?。該矩陣具有以下特性：

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

可以使用 從右上角開始搜索 的方法來有效地找到目標(biāo)值。

1. 選擇起始位置： 從矩陣的右上角開始。假設(shè)我們當(dāng)前的位置是 matrix[0][n-1]，其中 n 是列數(shù)。
2. 逐步搜索：
   • 如果當(dāng)前元素等于目標(biāo)值，返回 true。
   • 如果當(dāng)前元素大于目標(biāo)值，說明目標(biāo)值可能出現(xiàn)在當(dāng)前元素的左邊，因此我們向左移動一列。
   • 如果當(dāng)前元素小于目標(biāo)值，說明目標(biāo)值可能出現(xiàn)在當(dāng)前元素的下方，因此我們向下移動一行。
3. 結(jié)束條件： 如果超出了矩陣的邊界，說明沒有找到目標(biāo)值，返回 false。

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {if (matrix.empty() || matrix[0].empty()) return false;int m = matrix.size();     // 行數(shù)int n = matrix[0].size();  // 列數(shù)// 從右上角開始int row = 0;int col = n - 1;while (row < m && col >= 0) {if (matrix[row][col] == target) {return true;  // 找到目標(biāo)值} else if (matrix[row][col] > target) {col--;  // 當(dāng)前元素大于目標(biāo)值，向左移動} else {row++;  // 當(dāng)前元素小于目標(biāo)值，向下移動}}return false;  // 沒有找到目標(biāo)值}
};

• 初始位置：從矩陣的右上角 matrix[0][n-1] 開始。
• 移動規(guī)則：
  • 如果當(dāng)前元素等于目標(biāo)值，則返回 true。
  • 如果當(dāng)前元素大于目標(biāo)值，則移動到左邊一列。
  • 如果當(dāng)前元素小于目標(biāo)值，則移動到下方一行。
• 邊界條件：當(dāng)行數(shù)或列數(shù)超出范圍時，結(jié)束搜索。

二、島嶼數(shù)量

給你一個由?'1'（陸地）和?'0'（水）組成的的二維網(wǎng)格，請你計算網(wǎng)格中島嶼的數(shù)量。

島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。

此外，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。

• DFS 遍歷：從每個尚未訪問的陸地單元格開始，使用 DFS 遍歷其所有相鄰的陸地單元格，將它們標(biāo)記為已訪問。每次發(fā)現(xiàn)一個新的未被訪問的陸地，就說明發(fā)現(xiàn)了一個新的島嶼。

• 標(biāo)記訪問：為了避免重復(fù)計算同一個島嶼，需要在遍歷過程中將已經(jīng)訪問過的陸地標(biāo)記為水（'0'），這樣就不會再次訪問到它。

• 島嶼計數(shù)：每當(dāng)我們從一個未訪問的陸地開始 DFS 時，島嶼數(shù)加一。

• 對于每一個格子，如果它是陸地 ('1') 且未被訪問，則從該格子開始進(jìn)行 DFS，將與之相連的所有陸地格子標(biāo)記為已訪問，并將島嶼數(shù)量加一。
• 遍歷所有格子，最終得到島嶼的數(shù)量。
• 對于一個陸地格子（'1'），遞歸地向上下左右四個方向擴(kuò)展，找到與它相連的所有陸地并將其標(biāo)記為水（'0'）。
• 這樣做的目的是確保每個島嶼的陸地只被計數(shù)一次。

class Solution {
public:void dfs(vector<vector<char>>& grid, int i, int j) {// 邊界條件：如果當(dāng)前格子越界或已經(jīng)是水（'0'），則返回if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == '0') {return;}// 將當(dāng)前陸地格子標(biāo)記為水，表示已訪問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;// 遍歷整個網(wǎng)格for (int i = 0; i < grid.size(); ++i) {for (int j = 0; j < grid[0].size(); ++j) {// 找到一個未訪問的陸地，啟動 DFSif (grid[i][j] == '1') {numIslands++;  // 發(fā)現(xiàn)新的島嶼dfs(grid, i, j);  // 使用 DFS 標(biāo)記整個島嶼}}}return numIslands;}
};

• DFS 函數(shù)：dfs 用來遞歸訪問與當(dāng)前格子相連的所有陸地格子，并將它們標(biāo)記為水（'0'）。

  • 參數(shù) i, j 表示當(dāng)前正在處理的格子坐標(biāo)。
  • 在函數(shù)內(nèi)部，首先檢查是否越界或是否已經(jīng)是水（'0'），如果是則直接返回。
  • 然后標(biāo)記當(dāng)前格子為水，并遞歸檢查四個方向（上下左右）。

• 主函數(shù)：numIslands 遍歷整個二維網(wǎng)格，發(fā)現(xiàn)每個未訪問的陸地時，調(diào)用 dfs 來標(biāo)記所有相連的陸地，從而確保每個島嶼只計算一次。

• 邊界條件：如果網(wǎng)格為空，直接返回 0。

三、腐爛的橙子

在給定的?m x n?網(wǎng)格?grid?中，每個單元格可以有以下三個值之一：

• 值?0?代表空單元格；
• 值?1?代表新鮮橘子；
• 值?2?代表腐爛的橘子。

每分鐘，腐爛的橘子?周圍?4 個方向上相鄰?的新鮮橘子都會腐爛。

返回?直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)。如果不可能，返回?-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;  // 記錄新鮮橘子的數(shù)量// 初始化隊列和新鮮橘子數(shù)量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();// 四個方向擴(kuò)展for (auto& dir : directions) {int nx = x + dir.first;int ny = y + dir.second;// 如果新位置在網(wǎng)格內(nèi)且是新鮮橘子if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {grid[nx][ny] = 2;  // 將新鮮橘子腐爛rotten.push({nx, ny});  // 加入隊列freshCount--;  // 減少新鮮橘子的數(shù)量rottedThisRound = true;}}}// 如果這一輪有橘子腐爛，時間增加if (rottedThisRound) {minutes++;}}// 如果還有新鮮橘子，返回 -1return freshCount == 0 ? minutes : -1;}
};

• 初始化：
  • 我們先遍歷網(wǎng)格，找到所有腐爛的橘子，并將其加入隊列。同時，我們統(tǒng)計新鮮橘子的數(shù)量。
• BFS 過程：
  • 我們從腐爛的橘子開始，逐層擴(kuò)展，檢查每個腐爛橘子周圍的四個方向。
  • 如果發(fā)現(xiàn)相鄰位置是新鮮橘子（值為 1），我們就把它變成腐爛的橘子（值改為 2），并將其加入隊列，繼續(xù)擴(kuò)展。
  • 每次擴(kuò)展都意味著時間增加一分鐘。
• 結(jié)束條件：
  • 如果在 BFS 完成后還有新鮮橘子（freshCount > 0），說明不能完全腐爛所有橘子，返回 -1。
  • 否則，返回所需的分鐘數(shù)。

四、課程表

你這個學(xué)期必須選修?numCourses?門課程，記為?0?到?numCourses - 1?。

在選修某些課程之前需要一些先修課程。 先修課程按數(shù)組?prerequisites?給出，其中?prerequisites[i] = [ai, bi]?，表示如果要學(xué)習(xí)課程?ai?則?必須?先學(xué)習(xí)課程??bi?。

• 例如，先修課程對?[0, 1]?表示：想要學(xué)習(xí)課程?0?，你需要先完成課程?1?。

請你判斷是否可能完成所有課程的學(xué)習(xí)？如果可以，返回?true?；否則，返回?false?。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegree(numCourses, 0);  // 記錄每個課程的入度vector<vector<int>> graph(numCourses);  // 鄰接表表示圖// 構(gòu)建圖和入度數(shù)組for (const auto& prereq : prerequisites) {int course = prereq[0];  // 需要學(xué)習(xí)的課程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;  // 記錄已修課程的數(shù)量while (!q.empty()) {int course = q.front();q.pop();count++;// 對當(dāng)前課程的所有后續(xù)課程（即它的鄰接課程）進(jìn)行處理for (int nextCourse : graph[course]) {indegree[nextCourse]--;  // 當(dāng)前課程修完，減去下一個課程的入度if (indegree[nextCourse] == 0) {q.push(nextCourse);  // 如果下一個課程的入度為 0，加入隊列}}}// 如果修完的課程數(shù)量等于總課程數(shù)，則可以完成所有課程return count == numCourses;}
};

• 構(gòu)建圖和入度數(shù)組：
  • 我們首先創(chuàng)建一個 graph 數(shù)組來存儲圖的鄰接表，并創(chuàng)建一個 indegree 數(shù)組來記錄每個課程的入度（即每個課程有多少先修課程）。
  • 然后，我們根據(jù) prerequisites 數(shù)組來構(gòu)建圖，并更新每個課程的入度。
• 拓?fù)渑判?/strong>：
  • 我們初始化一個隊列 q，將所有入度為 0 的課程加入隊列。
  • 逐個從隊列中取出課程，修完后，將它的鄰接課程的入度減 1。如果某個鄰接課程的入度變?yōu)?0，則將它加入隊列。
• 判斷是否完成所有課程：
  • 最后，我們檢查已修的課程數(shù)量 count 是否等于總課程數(shù) numCourses。如果相等，說明沒有環(huán)路，返回 true；否則，返回 false。

class Trie {
private:struct TrieNode {unordered_map<char, TrieNode*> children;bool isWord;TrieNode() : isWord(false) {}};TrieNode* root;public:// 構(gòu)造函數(shù)，初始化 Trie 樹Trie() {root = new TrieNode();}// 向 Trie 插入一個字符串void insert(string word) {TrieNode* node = root;for (char c : word) {// 如果當(dāng)前字符的子節(jié)點不存在，則創(chuàng)建一個新的節(jié)點if (node->children.find(c) == node->children.end()) {node->children[c] = new TrieNode();}node = node->children[c];}// 標(biāo)記字符串結(jié)束的節(jié)點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;  // 如果有字符沒有找到對應(yīng)節(jié)點，返回 false}node = node->children[c];}// 如果到達(dá)字符串結(jié)尾并且是一個完整的單詞，返回 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;  // 如果有字符沒有找到對應(yīng)節(jié)點，返回 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);*/