网站怎么申请备案,简述制作网页时需要的环节,免费名片在线设计网站,微信外链网站开发图论51. 岛屿问题52. 腐烂的橘子53. 课程表54. 前缀树55. 全排列56. 子集57. 电话号码58. 组合总和59. 括号生成60. 单词搜索 图论
51. 岛屿问题
经典洪水问题算法
class Solution {
public:int numIslands(vectorvectorchar grid) {int nr grid.size… 图论51. 岛屿问题52. 腐烂的橘子53. 课程表54. 前缀树55. 全排列56. 子集57. 电话号码58. 组合总和59. 括号生成60. 单词搜索 图论
51. 岛屿问题
经典洪水问题算法
class Solution {
public:int numIslands(vectorvectorchar 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(vectorvectorchar 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 (j1 col grid[i][j1] 1) {dfs(grid , i , j 1);}if (i1 row grid[i1][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(vectorvectorint grid) {int min 0;int fresh 0;queuepairint, 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 (i0 i row j0 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, vectorvectorint prerequisites) {vectorint indegrees(numCourses, 0); // 存储每个课程的入度vectorvectorint adjacency(numCourses); // 存储课程的邻接表queueint 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:vectorint vis;vectorint path;void dfs(vectorvectorint ans, vectorint 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();}}vectorvectorint permute(vectorint nums) {vectorvectorint ans;vis.resize(nums.size(), 0);dfs(ans, nums, 0);return ans;}
};56. 子集
class Solution {
public:vectorint t;vectorvectorint ans;vectorvectorint subsets(vectorint 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 , vectorstring 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, i1 , comb str[j] , v);comb.pop_back();}}vectorstring letterCombinations(string digits) {// 整体思路 回溯// 我们首先看看整个digits字符串是否为空 如果为空的话直接返回一个空的vector就好// 如果不是空 这个时候我们就开始使用回溯算法来遍历数字中所有的组合了// 遍历完全厚直接返回就可以vectorstring v;if (digits.empty()){return v;}string comb; // 这个字符串用来接受最后的值// 接下来开始回溯算法 _letterCombinations(digits, 0 , comb , v);return v;}
};58. 组合总和
class Solution {
public:vectorvectorint combinationSum(vectorint candidates, int target) {vectorint state; // 状态子集sort(candidates.begin(), candidates.end()); // 对 candidates 进行排序int start 0; // 遍历起始点vectorvectorint res; // 结果列表子集列表backtrack(state, target, candidates, start, res);return res;}
private:void backtrack(vectorint state, int target, vectorint choices, int start, vectorvectorint 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(vectorstring 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:vectorstring generateParenthesis(int n) {vectorstring result;string current;backtrack(result, current, 0, 0, n);return result;}
};60. 单词搜索
class Solution {
public:bool exist(vectorvectorchar 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(vectorvectorchar 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;}
};
