圖論

200.島嶼數量DFS

給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量。島嶼總是被水包圍，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成。此外，你可以假設該網格的四條邊均被水包圍。

深度優先遍歷：用一個visited數組標記所有訪問過的地方，遍歷圖，遇到第一個陸地且沒被訪問過，就用深搜遍歷此島嶼的全部陸地。

class Solution {
private:int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void dfs(vector<vector<bool>>& visit, vector<vector<char>>& grid, int x, int y){for(int i = 0; i < 4; i++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;if(!visit[nextx][nexty] && grid[nextx][nexty] == '1') {visit[nextx][nexty] = true;dfs(visit, grid, nextx, nexty);}}}
public:int numIslands(vector<vector<char>>& grid) {int n = grid.size(), m = grid[0].size();vector<vector<bool>> visit = vector<vector<bool>>(n, vector<bool>(m, false));int result = 0;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(!visit[i][j] && grid[i][j] == '1') {result++;visit[i][j] = true;dfs(visit, grid, i, j);}}}return result;}
};

994.腐爛的橘子BFS

在給定的 m x n 網格 grid 中，每個單元格可以有以下三個值之一：
值 0 代表空單元格；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子。
每分鐘，腐爛的橘子 周圍 4 個方向上相鄰 的新鮮橘子都會腐爛。
返回 直到單元格中沒有新鮮橘子為止所必須經過的最小分鐘數。如果不可能，返回 -1 。

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

207.課程表

你這個學期必須選修 numCourses 門課程，記為 0 到 numCourses - 1 。
在選修某些課程之前需要一些先修課程。 先修課程按數組 prerequisites 給出，其中 prerequisites[i] = [ai, bi] ，表示如果要學習課程 ai 則 必須 先學習課程 bi 。
例如，先修課程對 [0, 1] 表示：想要學習課程 0 ，你需要先完成課程 1 。
請你判斷是否可能完成所有課程的學習？如果可以，返回 true ；否則，返回 false 。

本題可約化為： 課程安排圖是否是 有向無環圖(DAG)。
方法一：入度表（廣度優先遍歷）
算法流程：
統計課程安排圖中每個節點的入度，生成 入度表 indegrees。
借助一個隊列 queue，將所有入度為 0 的節點入隊。
當 queue 非空時，依次將隊首節點出隊，在課程安排圖中刪除此節點 pre：
并不是真正從鄰接表中刪除此節點 pre，而是將此節點對應所有鄰接節點 cur 的入度 ?1，即 indegrees[cur] -= 1。
當入度 ?1后鄰接節點 cur 的入度為 0，說明 cur 所有的前驅節點已經被 “刪除”，此時將 cur 入隊。
在每次 pre 出隊時，執行 numCourses–；
若整個課程安排圖是有向無環圖（即可以安排），則所有節點一定都入隊并出隊過，即完成拓撲排序。換個角度說，若課程安排圖中存在環，一定有節點的入度始終不為 0。
因此，拓撲排序出隊次數等于課程個數，返回 numCourses == 0 判斷課程是否可以成功安排。

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> adjacency(numCourses);vector<int> indegrees(numCourses, 0);queue<int> q;for(const auto& pair : prerequisites) {int course = pair[0], pre = pair[1];indegrees[course]++;adjacency[pre].push_back(course);}for(int i = 0; i < indegrees.size(); i++) {if(indegrees[i] == 0) q.push(i);}while(!q.empty()){int pre = q.front(); q.pop();numCourses--;for(int i = 0; i < adjacency[pre].size(); i++) {if(--indegrees[adjacency[pre][i]] == 0)q.push(adjacency[pre][i]);}}return numCourses == 0;}
};

208.前綴樹

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:bool isEnd;Trie* next[26];
public:Trie() {isEnd = false;memset(next, 0, sizeof(next));}void insert(string word) {Trie* node = this;for(char ch : word){if(node->next[ch - 'a'] == NULL) {node->next[ch - 'a'] = new Trie();}node = node->next[ch - 'a'];}node->isEnd = true;}bool search(string word) {Trie* node = this;for(char ch : word) {node = node->next[ch - 'a'];if(node == NULL) return false;}return node->isEnd;}bool startsWith(string prefix) {Trie* node = this;for(char ch : prefix) {node = node->next[ch - 'a'];if(node == NULL) return false;}return true;}
};/*** Your Trie object will be instanti`ated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

全排列

46. 全排列

給定一個不含重復數字的數組 nums ，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtracking(vector<int> & nums, vector<bool>& used){if(path.size() == nums.size()) {result.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(used[i] == true) continue;path.push_back(nums[i]);used[i] = true;backtracking(nums, used);used[i] = false;path.pop_back();}}
public:vector<vector<int>> permute(vector<int>& nums) {path.clear();result.clear();vector<bool> used(nums.size(), false);backtracking(nums,used);return result;}
};

78.子集

給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。

子集問題、組合問題、分割問題可以抽象成樹，組合和分割是收集樹的葉子結點，而子集是找樹的所有結點。

class Solution {
public:vector<int> path;vector<vector<int>> result;void backtracking(vector<int>& nums, int startIndex)  {result.push_back(path);for(int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {backtracking(nums, 0);return result;}
};

17. 電話號碼的字母組合

給定一個僅包含數字 2-9 的字符串，返回所有它能表示的字母組合。答案可以按 任意順序 返回。

class Solution {
private:const string letterMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public:vector<string> result;string s;void backtracking(const string& digits, int index) {if(digits.size() == index) {result.push_back(s);return;}int digit = digits[index] - '0';string letter = letterMap[digit];for(int i = 0; i < letter.size(); i++){s.push_back(letter[i]);backtracking(digits, index + 1);s.pop_back();}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if(digits.size() == 0)return result;backtracking(digits, 0);return result;}
};