LeetCode Hot 100：图论

LeetCode Hot 100：图论

200. 岛屿数量

思路 1：深度优先搜索

class Solution {
private:const int dx[4] = {-1, 0, 1, 0};const int dy[4] = {0, 1, 0, -1};public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())return 0;int m = grid.size(), n = m ? grid[0].size() : 0;function<void(int, int)> dfs = [&](int x, int y) -> void {if (x < 0 || x >= m || y < 0 || y >= n)return;if (grid[x][y] == '0')return;grid[x][y] = '0';for (int i = 0; i < 4; i++) {int r = x + dx[i], c = y + dy[i];dfs(r, c);}};int ans = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)if (grid[i][j] == '1') {ans++;dfs(i, j);}return ans;}
};

思路 2：广度优先搜索

class Solution {
public:int numIslands(vector<vector<char>>& grid) {if (grid.empty())return 0;int m = grid.size(), n = m ? grid[0].size() : 0;int islands = 0;for (int r = 0; r < m; r++)for (int c = 0; c < n; c++)if (grid[r][c] == '1') {islands++;grid[r][c] = '0';queue<pair<int, int>> neighbors;neighbors.push({r, c});while (!neighbors.empty()) {auto rc = neighbors.front();neighbors.pop();int row = rc.first, col = rc.second;if (row - 1 >= 0 && grid[row - 1][col] == '1') {neighbors.push({row - 1, col});grid[row - 1][col] = '0';}if (row + 1 < m && grid[row + 1][col] == '1') {neighbors.push({row + 1, col});grid[row + 1][col] = '0';}if (col - 1 >= 0 && grid[row][col - 1] == '1') {neighbors.push({row, col - 1});grid[row][col - 1] = '0';}if (col + 1 < n && grid[row][col + 1] == '1') {neighbors.push({row, col + 1});grid[row][col + 1] = '0';}}}return islands;}
};

994. 腐烂的橘子

思路 1：广度优先搜索

class Solution {
private:const int dx[4] = {0, 0, 1, -1};const int dy[4] = {1, -1, 0, 0};public:int orangesRotting(vector<vector<int>>& grid) {int m = grid.size(), n = m ? grid[0].size() : 0;queue<pair<int, int>> q;int fresh = 0;for (int i = 0; i < m; i++)for (int j = 0; j < n; j++) {if (grid[i][j] == 1)fresh++;else if (grid[i][j] == 2)q.push({i, j});}if (fresh == 0)return 0;else if (q.empty())return -1;int time = 0;while (fresh > 0 && !q.empty()) {int size = q.size();for (int i = 0; i < size; i++) {auto [x, y] = q.front();q.pop();for (int i = 0; i < 4; i++) {int r = x + dx[i], c = y + dy[i];if (r >= 0 && r < m && c >= 0 && c < n)if (grid[r][c] == 1) {fresh--;grid[r][c] = 2;q.push({r, c});}}}time++;}return fresh > 0 ? -1 : time;}
};

207. 课程表

思路 1：拓扑排序

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> graph(numCourses, vector<int>()); // 邻接矩阵vector<int> inDegree(numCourses, 0);                  // 入度数组for (vector<int>& prerequisity : prerequisites) {int from = prerequisity[1];int to = prerequisity[0];graph[from].push_back(to);inDegree[to]++;}queue<int> q;// 把入度为0的节点（即没有前置课程要求）放在队列中for (int i = 0; i < inDegree.size(); i++)if (inDegree[i] == 0)q.push(i);while (!q.empty()) {int u = q.front();q.pop();for (int& v : graph[u]) {inDegree[v]--;if (inDegree[v] == 0)q.push(v);}}for (int& in : inDegree)if (in)return false;return true;}
};

208. 实现 Trie (前缀树)

思路 1：字典树

class TrieNode {
public:TrieNode* childNode[26];bool isEnd;TrieNode() : isEnd(false) {for (int i = 0; i < 26; i++)childNode[i] = nullptr;}
};class Trie {
private:TrieNode* root;public:Trie() : root(new TrieNode()) {}// 向字典树插入一个词void insert(string word) {TrieNode* node = root;for (char& c : word) {if (node->childNode[c - 'a'] == nullptr)node->childNode[c - 'a'] = new TrieNode();node = node->childNode[c - 'a'];}node->isEnd = true;}// 判断字典树里是否有一个词bool search(string word) {TrieNode* node = root;for (char& c : word) {if (node == nullptr)break;node = node->childNode[c - 'a'];}return node ? node->isEnd : false;}// 判断字典树是否有一个以词开始的前缀bool startsWith(string prefix) {TrieNode* node = root;for (char& c : prefix) {if (node == nullptr)break;node = node->childNode[c - 'a'];}return node != nullptr;}
};/*** 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);*/