LeetCode Hot100 51~60

图论

51. 岛屿问题

经典洪水问题算法

class Solution {
public:int numIslands(vector<vector<char>>& grid) {int nr = grid.size();int nc = grid[0].size();int count = 0;for (int i = 0; i < nr; i++) {for (int j = 0; j < nc; j++) {if (grid[i][j] == '1') {count++;dfs(grid , i , j);}}} return count;}void dfs(vector<vector<char>>& grid , int i , int j) {int row = grid.size();int col = grid[0].size();grid[i][j] = '0';if (i - 1 >= 0 && grid[i-1][j] == '1') {dfs(grid , i - 1 , j);}if (j-1 >= 0 && grid[i][j-1] == '1') {dfs(grid , i , j - 1);}if (j+1 < col && grid[i][j+1] == '1') {dfs(grid , i  , j + 1);}if (i+1 < row && grid[i+1][j] == '1') {dfs(grid , i + 1 , j);}}
};

52. 腐烂的橘子

广度优先遍历 队列来实现

class Solution {int dirt[4][2] = {{-1, 0} , {1 , 0} , {0 , -1} , {0 , 1}};
public:int orangesRotting(vector<vector<int>>& grid) {int min = 0;int fresh = 0;queue<pair<int, int>> que;int row = grid.size();int col = grid[0].size();for (int i = 0; i < row; i++) {for(int j = 0; j < col; j++) {if (grid[i][j] == 1) {fresh++;}if (grid[i][j] == 2) {que.push({i , j});}}}while(!que.empty()) {int n = que.size();bool rotten = false;for (int i = 0; i < n; i++) {auto x = que.front();que.pop();for (auto cur : dirt) {int i = x.first + cur[0]; // 更新x的坐标int j = x.second + cur[1]; // 更新y的坐标if (i>=0 && i < row && j>=0 && j < col && grid[i][j] == 1) {grid[i][j] = 2;que.push({i , j});fresh--;rotten = true;}}}if (rotten) {min++;}}return fresh == 0 ? min : -1;}
};

53. 课程表

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> indegrees(numCourses, 0);  // 存储每个课程的入度vector<vector<int>> adjacency(numCourses);  // 存储课程的邻接表queue<int> queue;// 生成入度数组和邻接表for (const auto& cp : prerequisites) {indegrees[cp[0]]++;adjacency[cp[1]].push_back(cp[0]);}// 将入度为 0 的课程加入队列for (int i = 0; i < numCourses; i++) {if (indegrees[i] == 0) {queue.push(i);}}// BFS 拓扑排序while (!queue.empty()) {int pre = queue.front();queue.pop();numCourses--;  // 完成一门课程，剩下的课程数量减少for (int cur : adjacency[pre]) {if (--indegrees[cur] == 0) {queue.push(cur);}}}// 如果所有课程都能完成，返回 truereturn numCourses == 0;}
};

54. 前缀树

struct Node {Node* son[26]{};bool end = false;
};class Trie {Node* root = new Node();int find(string word) {Node* cur = root;for (char c : word) {c -= 'a';if (cur->son[c] == nullptr) {return 0;}cur = cur->son[c];}return cur->end ? 2 : 1;}public:void insert(string word) {Node* cur = root;for (char c : word) {c -= 'a';if (cur->son[c] == nullptr) {cur->son[c] = new Node();}cur = cur->son[c];}cur->end = true;}bool search(string word) {return find(word) == 2;}bool startsWith(string prefix) {return find(prefix) != 0;}
};

55. 全排列

class Solution {
public:vector<int> vis;vector<int> path;void dfs(vector<vector<int>>& ans, vector<int>& nums, int x) {if (x >= nums.size()) {ans.push_back(path);return;}for (int i = 0; i < nums.size(); i++ ) {if (vis[i]) continue;vis[i]++;path.push_back(nums[i]);dfs(ans, nums, x + 1);vis[i]--;path.pop_back();}}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;vis.resize(nums.size(), 0);dfs(ans, nums, 0);return ans;}
};

56. 子集

class Solution {
public:vector<int> t;vector<vector<int>> ans;vector<vector<int>> subsets(vector<int>& nums) {int n = nums.size();for (int mask = 0; mask < (1 << n); ++mask) {t.clear();for (int i = 0; i < n; ++i) {if (mask & (1 << i)) {t.push_back(nums[i]);}}ans.push_back(t);}return ans;}
};

57. 电话号码

class Solution {string arr[10] = {"" , "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz"};
public:void _letterCombinations(string& digits, int i , string& comb , vector<string>& v){// 首先来看回溯结束的条件 是不是当i走到digits最后的时候就结束啊if (i == digits.size()){v.push_back(comb);return;}int j = 0;string str = arr[digits[i] - '0'];for (j = 0; j < str.size() ; j++ ){_letterCombinations(digits, i+1 , comb += str[j]  , v);comb.pop_back();}}vector<string> letterCombinations(string digits) {// 整体思路： 回溯：// 我们首先看看整个digits字符串是否为空 如果为空的话直接返回一个空的vector就好// 如果不是空 这个时候我们就开始使用回溯算法来遍历数字中所有的组合了// 遍历完全厚直接返回就可以vector<string> v;if (digits.empty()){return v;}string comb; // 这个字符串用来接受最后的值// 接下来开始回溯算法 _letterCombinations(digits, 0 ,  comb ,  v);return v;}
};

58. 组合总和

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> state;              // 状态（子集）sort(candidates.begin(), candidates.end()); // 对 candidates 进行排序int start = 0;                  // 遍历起始点vector<vector<int>> res;        // 结果列表（子集列表）backtrack(state, target, candidates, start, res);return res;}
private:void backtrack(vector<int> &state, int target, vector<int> &choices, int start, vector<vector<int>> &res) {// 子集和等于 target 时，记录解if (target == 0) {res.push_back(state);return;}// 遍历所有选择// 剪枝二：从 start 开始遍历，避免生成重复子集for (int i = start; i < choices.size(); i++) {// 剪枝一：若子集和超过 target ，则直接结束循环// 这是因为数组已排序，后边元素更大，子集和一定超过 targetif (target - choices[i] < 0) {break;}// 尝试：做出选择，更新 target, startstate.push_back(choices[i]);// 进行下一轮选择backtrack(state, target - choices[i], choices, i, res);// 回退：撤销选择，恢复到之前的状态state.pop_back();}}
};

59. 括号生成

class Solution {void backtrack(vector<string>& ans, string& cur, int open, int close, int n) {if (cur.size() == n * 2) {ans.push_back(cur);return;}if (open < n) {cur.push_back('(');backtrack(ans, cur, open + 1, close, n);cur.pop_back();}if (close < open) {cur.push_back(')');backtrack(ans, cur, open, close + 1, n);cur.pop_back();}}
public:vector<string> generateParenthesis(int n) {vector<string> result;string current;backtrack(result, current, 0, 0, n);return result;}
};

60. 单词搜索

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {rows = board.size();cols = board[0].size();for(int i = 0; i < rows; i++) {for(int j = 0; j < cols; j++) {if (dfs(board, word, i, j, 0)) return true;}}return false;}
private:int rows, cols;bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;if (k == word.size() - 1) return true;board[i][j] = '\0';bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);board[i][j] = word[k];return res;}
};