图论算法属于量大管饱，模板硬套
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例一
输入：
grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
auto dfs = [&](this auto&& dfs, int i, int j){
if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1'){
return;
}
grid[i][j] ='2';
dfs(i-1, j);
dfs(i+1, j);
dfs(i, j-1);
dfs(i, j+1);
};
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;
}
};
994. 腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
bool cnt_two = false, cnt_one = false;
queue<pair<int, int>> q;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 2){
q.push({i, j});
cnt_two = true;
}
if(grid[i][j] == 1){
cnt_one = true;
}
}
}
if(cnt_one == false){
return 0;
}
int ans = -1;
int dirs[4][2] = { {0, -1}, {0, 1}, {1, 0}, {-1, 0} };
while(!q.empty()){
int s = q.size();
ans++;
for(int i = 0; i < s; i++){
pair<int, int> p = q.front();
q.pop();
for(int k = 0; k < 4; k++){
int x = p.first + dirs[k][0], y = p.second + dirs[k][1];
if(x < m && x >= 0 && y >= 0 && y < n && grid[x][y] == 1){
grid[x][y] = 2;
q.push({x, y});
}
}
}
}
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == 1){
return -1;
}
}
}
return ans;
}
};
这题要一次A出来难度不小，主要是有特殊情况要特判，非常抽象了
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& nums) {
int n = nums.size();
unordered_map<int, vector<int>> umap;
vector<int> pre(numCourses, 0);
for(int i = 0; i < n; i++){
umap[nums[i][1]].push_back(nums[i][0]);
pre[nums[i][0]]++;
}
queue<int> q;
for(int i = 0; i < numCourses; i++){
if(pre[i] == 0) {
q.push(i);
}
}
while(!q.empty()){
int p = q.front();
q.pop();
for(auto t : umap[p]){
if(--pre[t] == 0){
q.push(t);
}
}
}
for(int i = 0; i < numCourses; i++){
if(pre[i] != 0) {
return false;
}
}
return true;
}
};
这个题要做两件事：
- 建图。这个建图是边（头到尾的方式）
- 记录零入度的节点到队列
433. 最小基因变化
BFS算法 设计方式就是设计一个哈希表和哈希集合，前者关联基因string和变化次数，后者则是记录bank，参考单词划分那道题，两重循环。
class Solution {
public:
int minMutation(string startGene, string endGene, vector<string>& bank) {
vector<char> c = {'A', 'C', 'T', 'G'};
unordered_set<string> uset(bank.begin(), bank.end());
if(uset.find(endGene) == uset.end()) return -1;
unordered_map<string, int> umap;
queue<string> q;
q.push(startGene);
umap[startGene] = 0;
if(uset.find(startGene) != uset.end()) uset.erase(startGene);
while(!q.empty()){
string p = q.front(); q.pop();
for(int i = 0; i < 8; i++){
string s = p;
for(auto t : c){
if(s[i] != t){
s[i] = t;
if(s == endGene) return umap[p] + 1;
if(uset.find(s) != uset.end() && umap.find(s) == umap.end()){
umap[s] = umap[p] + 1;
uset.erase(s);
q.push(s);
}
}
}
}
}
return -1;
}
};
