【牛客刷题】笔记2
目录
1、单词搜索
2、岛屿数量
2.1 DFS
2.2 BFS
3、腐烂的橘子
1、单词搜索
单词搜索_牛客题霸_牛客网 (nowcoder.com)
这道题我们就是先遍历数组board，若遇到了与word[0]相等的字符，则以这个字符为起点进行搜索，搜索可以是dfs，也可以是bfs，在这里我们使用的是dfs。
class Solution {
public:
int m, n;
bool vis[101][101] = {0}; // vis用来标记某一位置是否已经被搜索过了，0表示没有，1表示有
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
bool dfs(vector<string>& board, int i, int j, string& word, int pos)
{
if(pos == word.size() - 1) return true;
vis[i][j] = true;
for(int k = 0;k < 4;k++)
{
int a = i + dx[k], b = j + dy[k];
if(a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && board[a][b] == word[pos + 1])
{
if(dfs(board, a, b, word, pos + 1)) return true;
}
}
vis[i][j] = false; // 恢复现场
return false;
}
bool exist(vector<string>& board, string word) {
m = board.size(), n = board[0].size();
for(int i = 0;i < m;i++)
for(int j = 0;j < n;j++)
if(board[i][j] == word[0])
if(dfs(board, i, j, word, 0)) return true;
return false;
}
};2、岛屿数量
200. 岛屿数量 - 力扣（LeetCode）
2.1 DFS
我们需要先遍历二维数组，当遇到字符1时，就将ans++，并将1所在的整个岛屿都变成0，都变成0后就继续刚刚的遍历二维数组，重复上面的操作，直到将二维数组遍历完，ans就是岛屿数量。
遇到1时，将整个岛屿变成0的操作，就可以使用DFS。从遇到1的地点开始，进行DFS，直到将整个岛屿都变成了0结束
class Solution {
private:
// DFS
int n, m;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
void dfs(vector<vector<char>>& grid, int x, int y){
// 若位置不合法或者是'0'，就返回
if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '0') return ;
grid[x][y] = '0'; // 将当前位置变成'0'
for(int i = 0;i < 4;i ++) // 搜索当前位置的上下左右4个位置
dfs(grid, x + dx[i], y + dy[i]);
}
public:
int numIslands(vector<vector<char>>& grid) {
n = grid.size(), m = grid[0].size();
int sum = 0;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(grid[i][j] == '1')
{
sum ++;
dfs(grid, i, j);
}
return sum;
}
};2.2 BFS
与DFS前面步骤是类似的。我们需要先遍历二维数组，当遇到字符1时，就将ans++，并将1所在的整个岛屿都变成0，都变成0后就继续刚刚的遍历二维数组，重复上面的操作，直到将二维数组遍历完，ans就是岛屿数量。
遇到1时，将整个岛屿变成0的操作，就可以使用BFS。从遇到1的地点开始，进行DFS，直到将整个岛屿都变成了0结束
class Solution {
private:
// BFS
int n, m;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void bfs(vector<vector<char>>& grid, int x, int y){
queue<pair<int, int>> q;
q.push({x, y});
while(!q.empty())
{
int currentRow = q.front().first, currentCol = q.front().second;
q.pop();
grid[currentRow][currentCol] = '0'; // 标记为已访问
for(int k = 0; k < 4; k++)
{
int i = currentRow + dx[k], j = currentCol + dy[k];
if(i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == '1') q.push({i, j});
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0; // 检查边界条件
n = grid.size(), m = grid[0].size();
int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(grid[i][j] == '1')
{
sum++;
bfs(grid, i, j);
}
return sum;
}
};此时就会发现逻辑全对，但是却超时了。这是因为我们在从队列中取出一个点时才标记已访问，这样会导致重复加入，应该在放入队列时就标记已访问。
若取出时才标记已访问，会发现下标为[1][1]的点会被下标为[0][1]、[1][0]的点都放入一次队列。
class Solution {
private:
// BFS
int n, m;
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
void bfs(vector<vector<char>>& grid, int x, int y){
queue<pair<int, int>> q;
q.push({x, y});
grid[x][y] = '0'; // 放入时就标记
while(!q.empty())
{
int currentRow = q.front().first, currentCol = q.front().second;
q.pop();
for(int k = 0; k < 4; k++)
{
int i = currentRow + dx[k], j = currentCol + dy[k];
if(i >= 0 && i < n && j >= 0 && j < m && grid[i][j] == '1')
{
q.push({i, j});
grid[i][j] = '0';
}
}
}
}
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty() || grid[0].empty()) return 0; // 检查边界条件
n = grid.size(), m = grid[0].size();
int sum = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(grid[i][j] == '1')
{
sum++;
bfs(grid, i, j);
}
return sum;
}
};
3、腐烂的橘子
994. 腐烂的橘子 - 力扣（LeetCode）
这道题看似与岛屿数量是有点类似的。我们可以先遍历二维数组，当遇到值为2的结点时，就以此结点为起点，进行搜索。注意：这道题的搜索就好使用BFS，因为橘子腐烂的传递是向四个方向进行传递的。这样子的思路是会有问题的，因为一个区域内可能不止有一个腐烂的橘子，这些橘子是会一起向四周扩散的。所以，使用多源BFS。
正确的做法是：我们先遍历原数组，值为2的结点都放入队列，我们一次处理队列中的所有元素
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int n = grid.size(), m = grid[0].size(), sum = 0;
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
queue<pair<int, int>> q;
for(int i = 0;i < n;i ++)
for(int j = 0;j < m;j ++)
if(grid[i][j] == 2) q.push({i, j});
while(!q.empty())
{
vector<pair<int, int>> v;
while(!q.empty())
{
v.push_back({q.front().first, q.front().second});
q.pop();
}
// 标记最后一步是否有执行,因为当全扩散完后，还会再循环一次，导致sum多加一次，所以有一个标记，当没有向队列中放入时，sum就不会++
bool flag = false;
for(int k = 0;k < v.size();k++)
{
for(int i = 0; i < 4; i++)
{
int a = v[k].first + dx[i], b = v[k].second + dy[i];
if(a >= 0 && a < n && b >= 0 && b < m && grid[a][b] == 1)
{
q.push({a, b});
grid[a][b] = 2;
flag = true;
}
}
}
if(flag) sum ++;
}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(grid[i][j] == 1) return -1; // 若还有1，表示有些位置一定不会腐烂
return sum;
}
};