层次遍历算法总结
C语言的层次遍历总结篇
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 < gridSize; i++){
for(int j = 0; j < gridColSize[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 < gridSize && 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.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 < gridColSize[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 < boardSize; i++){
for(int j = 0; j < boardColSize[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 < boardSize && 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.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 < boardColSize[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 < boardSize; i++) {
for (int j = 0; j < boardColSize[0]; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'm') {
board[i][j] = 'O';
}
}
}
return;
}
130. 被围绕的区域并查集算法
并查集算法
#include <stdio.h>
#include <stdlib.h>
#define VERTICES 6
void initialise(int parent[], int rank[]){
int i;
for(i = 0; i < VERTICES; i++){
parent[i] = -1;
rank[i] = 0;
}
}
int find_root(int x, int parent[]){
int x_root = x;
while(parent[x_root] != -1){
x_root = parent[x_root];
}
return x_root;
}
int union_vertices(int x, int y, int parent[], int rank[]){
int x_root = find_root(x, parent);
int y_root = find_root(y, parent);
if(x_root == y_root){
return 0;
} else {
if(rank[x_root] > rank[y_root]){
parent[y_root] = x_root;
}else if(rank[y_root] > rank[x_root]){
parent[y_root] = x_root;
}else {
parent[x_root] = y_root;
rank[y_root]++;
}
return 1;
}
}
int main(){
int parent[VERTICES] = {0};
int rank[VERTICES] = {0};
int edges[5][2] = {
{0,1}, {1,2}, {1,3},
{3,4}, {2,5}
};
initialise(parent,rank);
int i;
for(i = 0; i < 5; i++){
int x = edges[i][0];
int y = edges[i][1];
if(union_vertices(x,y,parent,rank) == 0){
printf("Cycle detected!
");
exit(0);
}
}
printf("No cycles found.
");
return 0;
}
