目錄

1? 200. 島嶼數(shù)量

2? 994. 腐爛的橘子

2.1? 智障遍歷法

2.2? 仿層序遍歷法

---

菜鳥(niǎo)做題，語(yǔ)言是 C++

1? 200. 島嶼數(shù)量

解題思路：

1. 遍歷二維數(shù)組，尋找 “1”（若找到則島嶼數(shù)量 +1）
2. 尋找與當(dāng)前 “1” 直接或間接連接在一起的 “1”
3. 將這些 “1” 置為 “0”，再尋找下一個(gè) “1”

思路說(shuō)明圖：

如步驟 1 所示，我們找到 “1”（紅框內(nèi)部），它可以作為一個(gè)島嶼的開(kāi)頭。接下來(lái)，我們尋找與這個(gè) “1” 直接或間接連接在一起的 “1”，如步驟 2 所示。這一坨 “1”（紅框內(nèi)部）構(gòu)成一個(gè)島嶼。

直接連接 是指上下左右四個(gè)方向，斜對(duì)角方向的不算。

除此之外，為了避免我們下一次尋找 “1” 時(shí)，把這座島嶼內(nèi)部的 “1” 視為下一個(gè)島嶼的開(kāi)頭，我們要將這些 “1” 置為 “0” 。

我們是對(duì)整個(gè)二維數(shù)組進(jìn)行遍歷的，若不在遍歷完一座島嶼后將 “1” 置為 “0”，那么這座島嶼除開(kāi)頭之外的 “1” 會(huì)被誤認(rèn)為是下一座島嶼的開(kāi)頭。

具體代碼：

① Find “1”：在二維數(shù)組中尋找 “1”，作為島嶼的開(kāi)頭。

for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == '1') {++count;helper(grid, i, j);}}
}

nr 是二維數(shù)組的行數(shù)，nc 是二維數(shù)組的列數(shù)。一旦找到 “1” 就 ++count，即認(rèn)為找到了一座新的島嶼。同時(shí)，使用 helper 函數(shù)去尋找與當(dāng)前 “1” 直接或間接連接在一起的 “1” 。

② Find Island：尋找與當(dāng)前 “1” 直接或間接連接在一起的 “1”，它們構(gòu)成一座島嶼。

void helper(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
}

這四個(gè) if 其實(shí)就是做上下左右四個(gè)方向的邊界判斷，同時(shí)判斷當(dāng)前 “1” 的鄰居是不是 “1” 。若找到相鄰的 “1”，那么再遞歸尋找與相鄰的 “1” 直接或間接連接在一起的 “1” 。

class Solution {
public:void helper(vector<vector<char>>& grid, int r, int c) {int nr = grid.size();int nc = grid[0].size();grid[r][c] = '0';if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);}int numIslands(vector<vector<char>>& grid) {int nr = grid.size();if (nr == 0) return 0;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;helper(grid, i, j);}}}return count;}
};

2? 994. 腐爛的橘子

與? 200. 島嶼數(shù)量? 像又不像，區(qū)別在于是否有時(shí)間觀念

2.1? 智障遍歷法

解題思路：

1. 每個(gè)時(shí)刻都遍歷二維數(shù)組，尋找腐爛的橘子（2）
2. 對(duì)位于腐爛的橘子（2）四周的新鮮橘子（1）進(jìn)行污染
3. 直到所有新鮮橘子都被污染，或者無(wú)法繼續(xù)污染

具體代碼：

① 尋找腐爛的橘子（2），與 200 題的代碼幾乎一樣。

for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}
}

② 對(duì)位于腐爛的橘子（2）四周的新鮮橘子（1）進(jìn)行污染。

void helper(vector<vector<int>>& grid, int r, int c) {if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
}

③ 判斷是否所有的新鮮橘子（1）都被污染。

bool isRotted(vector<vector<int>>& grid) {for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) return false;}}return true;
}

④ 判斷是否無(wú)法繼續(xù)污染：在進(jìn)行新一輪污染之前，先把上一輪的污染結(jié)果 grid 存入 temp 中，如果這一輪污染后有 temp == grid，則說(shuō)明已經(jīng)無(wú)法繼續(xù)污染了。

vector<vector<int>> temp = grid;
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}
}
if (temp == grid) return -1;

這樣做還有一個(gè)好處，就是可以通過(guò) if (temp[i][j] == 2) 來(lái)尋找腐爛的橘子，避免在這一輪中新腐爛的橘子參與到污染中。

class Solution {
public:int nr, nc;void helper(vector<vector<int>>& grid, int r, int c) {if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;}bool isRotted(vector<vector<int>>& grid) {for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) return false;}}return true;}int orangesRotting(vector<vector<int>>& grid) {nr = grid.size();nc = grid[0].size();int count = 0;while (!isRotted(grid)) {vector<vector<int>> temp = grid;for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (temp[i][j] == 2)helper(grid, i, j);}}if (temp == grid) return -1;++count;if (isRotted(grid)) return count;}return count;}
};

2.2? 仿層序遍歷法

參考官方題解進(jìn)行了升級(jí)，仿二叉樹(shù)的層序遍歷，不用像 2.1 那樣每次都進(jìn)行全部遍歷

核心思想：將屬于同一時(shí)刻的腐爛橘子視為屬于同一層。

上圖畫(huà)出了橘子逐步腐爛的 5 個(gè)時(shí)刻，每個(gè)時(shí)刻中打紅叉的腐爛橘子屬于同一層，打灰叉的腐爛橘子屬于上一層。

解題思路：

• 將屬于同一時(shí)刻的腐爛橘子送入隊(duì)列中
• 出隊(duì)并遍歷屬于同一時(shí)刻的腐爛橘子
• 對(duì)四周的新鮮橘子進(jìn)行污染并送入隊(duì)列中

思路說(shuō)明圖：

對(duì)于時(shí)刻 1，讓腐爛的橘子入隊(duì)；對(duì)于時(shí)刻 2，隊(duì)列中的腐爛橘子出隊(duì)，讓它們對(duì)四周的新鮮橘子進(jìn)行污染，最后將新被污染的橘子入隊(duì)。以此類推。

在一輪污染中，如果有橘子被污染，則計(jì)時(shí)器 +1，同時(shí)判斷新鮮橘子是否被污染完畢；如果沒(méi)有橘子被污染，則跳出循環(huán)，同時(shí)判斷新鮮橘子是否被污染完畢。若沒(méi)有橘子被污染且新鮮橘子沒(méi)有被污染完畢，則表明無(wú)法污染所有新鮮橘子。

具體代碼：

① 初始化：

• 計(jì)數(shù)新鮮橘子的數(shù)量，即 freshCount + 1
• 記錄腐爛橘子的位置，即將橫縱坐標(biāo)送入隊(duì)列中

int freshCount = 0;
queue<pair<int, int>> q;
for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) {++freshCount;} else if (grid[i][j] == 2) {q.push(make_pair(i, j));}}
}

nr 是 grid 的行數(shù)，nc 是 grid 的列數(shù)。

② 循環(huán)結(jié)構(gòu)和二叉樹(shù)的層序遍歷一模一樣：

• 獲取當(dāng)前層中腐爛橘子的個(gè)數(shù)
• 遍歷當(dāng)前層中的腐爛橘子

while (!q.empty()) {int currentSize = q.size();for (int i = 0; i < currentSize; ++i) {pair<int, int> pos = q.front();q.pop();// 對(duì)橘子進(jìn)行污染}
}

③ 針對(duì)每個(gè)腐爛橘子，對(duì)其四周進(jìn)行污染：

• 判斷上/下/左/右位置是否越界，若越界則跳過(guò)該位置
• 若該位置上的是新鮮橘子，則進(jìn)行污染并將其入隊(duì)
• 同時(shí)將污染標(biāo)志置為 true，新鮮橘子數(shù)量 - 1

for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)continue;if (grid[x][y] == 1) {hasPolluted = true;--freshCount;grid[x][y] = 2;q.push(make_pair(x, y));}if (freshCount == 0) break;
}

hasPolluted 用于表明當(dāng)前層中是否至少有一個(gè)腐爛橘子造成了污染，如果沒(méi)有造成污染，那么就要考慮是否無(wú)法污染所有新鮮橘子了。

class Solution {
public:int dir_x[4] = {0, 1, 0, -1};int dir_y[4] = {1, 0, -1, 0};int orangesRotting(vector<vector<int>>& grid) {int nr = grid.size();if (nr == 0) return 0;int nc = grid[0].size();int freshCount = 0;queue<pair<int, int>> q;for (int i = 0; i < nr; ++i) {for (int j = 0; j < nc; ++j) {if (grid[i][j] == 1) {++freshCount;} else if (grid[i][j] == 2) {q.push(make_pair(i, j));}}}int timeCount = 0;int hasPolluted = false;while (!q.empty()) {int currentSize = q.size();for (int i = 0; i < currentSize; ++i) {pair<int, int> pos = q.front();q.pop();for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)continue;if (grid[x][y] == 1) {hasPolluted = true;--freshCount;grid[x][y] = 2;q.push(make_pair(x, y));}if (freshCount == 0) break;}}if (hasPolluted) ++timeCount;hasPolluted = false;}return freshCount == 0 ? timeCount : -1;}
};

技能點(diǎn)：使用循環(huán)結(jié)構(gòu)來(lái)測(cè)試上/下/左/右四個(gè)方位。

int dir_x[4] = {0, 1, 0, -1};
int dir_y[4] = {1, 0, -1, 0};for (int i = 0; i < 4; ++i) {int x = pos.first + dir_x[i];int y = pos.second + dir_y[i];if (x < 0|| x >= nr || y < 0|| y >= nc)// ...
}

并且用逆否命題來(lái)作為判斷條件，就不需要寫(xiě)很多 && 了！