算法模块总结
2021-01-25 07:14
标签：初始 题目 span 入队 返回 tar problem free pen 层次遍历算法总结 被围绕的区域 算法模块总结 标签：初始 题目 span 入队 返回 tar problem free pen 原文地址：https://www.cnblogs.com/maleyang/p/12862218.htmlC语言的层次遍历总结篇
1、先定义一个队列的结构体
typedef struct {
int x;
int y;
} Node;
int numIslands(char** grid, int gridSize, int* gridColSize){
2、鲁棒性、判断输入参数
if(grid == NULL || gridSize 0 || gridColSize[0] 0){
return 0;
}
3、根据输入参数、返回值的需要定义
int landsNums = 0;
4、模拟队列，队列初始化
Node* queue = (Node*)malloc(sizeof(Node)*gridSize*gridColSize[0]);
memset(queue, 0, sizeof(Node)*gridSize*gridColSize[0]);
5、存储临时变量作为当前值
Node cur;
6、根据当前选择列表进行层次遍历算法
for(int i = 0; i ){
for(int j = 0; j 0]; j++){
if(grid[i][j] == ‘1‘){
grid[i][j] = ‘0‘;
7、对于选择列表的每个节点都进行层次遍历，则需要头指针和尾指针初始化
int front = 0;
queue[front].x = i;
queue[front++].y = j;
8、取出当前队列的节点，并将其子节点入队列
while(front != 0){
cur = queue[--front];
if(cur.x - 1 >= 0 && grid[cur.x-1][cur.y] == ‘1‘){
grid[cur.x-1][cur.y] = ‘0‘;
queue[front].x = cur.x-1;
queue[front++].y = cur.y;
}
if (cur.x + 1 1][cur.y] == ‘1‘) {
grid[cur.x + 1][cur.y] = ‘0‘;
queue[front].x = cur.x + 1;
queue[front++].y = cur.y;
}
if (cur.y - 1 >= 0 && grid[cur.x][cur.y - 1] == ‘1‘) {
grid[cur.x][cur.y - 1] = ‘0‘;
queue[front].x = cur.x;
queue[front++].y = cur.y - 1;
}
if (cur.y + 1 0] && grid[cur.x][cur.y + 1] == ‘1‘) {
grid[cur.x][cur.y + 1] = ‘0‘;
queue[front].x = cur.x;
queue[front++].y = cur.y + 1;
}
}
9、当前题目的需求进行处理
landsNums++;
}
}
}
free(queue);
return landsNums;
}
130. 被围绕的区域
https://leetcode-cn.com/problems/surrounded-regions/
typedef struct {
int x;
int y;
} Node;
void solve(char** board, int boardSize, int* boardColSize){
if(board == NULL || boardSize 0 || boardColSize[0] 0){
return ;
}
Node* queue = (Node*)malloc(sizeof(Node)*boardSize*boardColSize[0]);
memset(queue, 0, sizeof(Node)*boardSize*boardColSize[0]);
Node cur;
for(int i = 0; i ){
for(int j = 0; j 0]; j++){
if((i==0 || i == boardSize-1 || j == 0 || j ==boardColSize[0]-1) && board[i][j] == ‘O‘){
int front = 0;
int rear = 0;
queue[front].x = i;
queue[front++].y = j;
while(front != 0){
cur = queue[--front];
if(cur.x - 1 >= 0 && board[cur.x-1][cur.y] == ‘O‘){
board[cur.x-1][cur.y] = ‘m‘;
queue[front].x = cur.x-1;
queue[front++].y = cur.y;
}
if (cur.x + 1 1][cur.y] == ‘O‘) {
board[cur.x + 1][cur.y] = ‘m‘;
queue[front].x = cur.x + 1;
queue[front++].y = cur.y;
}
if (cur.y - 1 >= 0 && board[cur.x][cur.y - 1] == ‘O‘) {
board[cur.x][cur.y - 1] = ‘m‘;
queue[front].x = cur.x;
queue[front++].y = cur.y - 1;
}
if (cur.y + 1 0] && board[cur.x][cur.y + 1] == ‘O‘) {
board[cur.x][cur.y + 1] = ‘m‘;
queue[front].x = cur.x;
queue[front++].y = cur.y + 1;
}
}
board[i][j] = ‘m‘;
}
}
}
// 遍历矩阵，把O全部改写成X，A全部改写成O
for (int i = 0; i ) {
for (int j = 0; j 0]; j++) {
if (board[i][j] == ‘O‘) {
board[i][j] = ‘X‘;
} else if (board[i][j] == ‘m‘) {
board[i][j] = ‘O‘;
}
}
}
return;
}
上一篇：Python获取阿拉丁统计信息
下一篇：线程安全