编程总结

每每刷完一道题后，其思想和精妙之处没有地方记录，本篇博客用以记录刷题过程中的遇到的算法和技巧

BFS 是广度优先遍历，常借助队列来实现
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
BFS 具体说明参考《编程之美》专栏里

695. 岛屿的最大面积

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0

#define QUEUE_LEN  (101 * 101)
#define NUM_101    (101 * 101)
typedef struct Node {
	int x;
	int y;
	int depth;
} Node;
int head = 0;
int tail = 0;
int gDirection[4][2] = {{-1,0}, {0,1}, {1,0}, {0,-1}};
int bfs(int **grid, int n, int m)
{
	int row = n, col = m;
	Node queue[NUM_101];
	int head = 0, tail = 0;
	int cnt = 0;
	int result = 0;
	for (int i = 0; i < row; ++i) {
		for (int j = 0; j < col; ++j) {
			if (grid[i][j] == 1) {
				queue[tail].x = i;
				queue[tail].y = j;
				grid[i][j] = 0;
				cnt = 1;
				tail = (tail + 1) % NUM_101;
				int size = tail - head;
				while (size > 0) {
					int xx = queue[head].x;
					int yy = queue[head].y;
					head = (head + 1) % NUM_101;
					for (int i = 0; i < 4; ++i) {
						int xNext = xx + gDirection[i][0];
						int yNext = yy + gDirection[i][1];
						if (0 <= xNext && xNext < row && 0 <= yNext && yNext < col && (grid[xNext][yNext] == 1)) {
							grid[xNext][yNext] = 0;
							queue[tail].x = xNext;
							queue[tail].y = yNext;
							tail = (tail + 1) % NUM_101;
							cnt++;
							size--;
							printf("queue = %d %d \n", xNext, yNext);
						}
					}
					size = tail - head;
				}
			}
			printf("result = %d\n", result);
			result = fmax(result, cnt);
			cnt = 0;
		}
	}
	return result;
}
int maxAreaOfIsland(int **grid, int gridSize, int* gridColSize)
{
	int n = gridSize, m = gridColSize[0];
	int ans = 0;
	ans = bfs(grid, n, m);
	return ans;
}

剑指 Offer 32 - I. 从上到下打印二叉树

思路：

#define MAXLINE 2000
int *levelOrder(struct TreeNode *root, int *returnSize) {
    returnSize[0] = 0;
    // 特殊情况
    if (root == NULL) return NULL;
    int head = 0; // 相当于数组左边为尾，右边为头
    int tail = 0;
    struct TreeNode *queue[MAXLINE];
    int *res = (int *)malloc(sizeof(int) * MAXLINE);
    queue[tail++] = root;     // 根节点入队列，队尾插入
    while(head < tail) {
        struct TreeNode* tmp = (struct TreeNode*)malloc(sizeof(struct TreeNode) * MAXLINE);
        tmp = queue[head++]; // 出队列，队头删除
        res[(*returnSize)++] = tmp->val;
        if(tmp->left != NULL){
            queue[tail++] = tmp->left;
        }
        if(tmp->right != NULL){
            queue[tail++] = tmp->right;
        }
    }
    return res;
}

Open Lock

解开一个密码锁。这个密码包括四位，每一位都是1 ~ 9的数字。每次操作，你可以对任一位加上或者减去1，一个数字位可能会变成1，而当它从1再被减“1”时，它会变成“9”；此外，你也可以把相邻位的数字调换。每一个操作是一步。
你的目标是，使用最少的步数解开密码。
注意：最左边一位数字不能算是最右边一位数字的相邻位。
输入样例 1 复制
1234
2144
输出样例 1
2

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

#define MAX 10001
typedef struct {
    char *passWord;
    int patlLoss;
} Node;

Node *gQueue[MAX];
int   gFlag[MAX] = {0};
int   head = 0;
int   tail = 0;

// 交换函数，i为位置
void Swap(char *lock, int pos)
{
    char buffer;
    buffer  = lock[pos];
    lock[pos] = lock[pos + 1];
    lock[pos + 1] = buffer;
}

// 非交换式的密码BFS搜索
void NoExchangeSearch(int i, Node *node, int dirFlag)
{
    char buffer = node->passWord[i];
    char changeBuffer;
    if (dirFlag) {
        changeBuffer = buffer == '1' ? '9' : buffer - 1;
    } else {
        changeBuffer = buffer == '9' ? '1' : buffer + 1;
    }
    char *p = (char *)malloc(5 * sizeof(char));
    strcpy(p, node->passWord);
    p[i] = changeBuffer;
    int num = atoi(p);
    if (gFlag[num]) {
        free(p);
        return;
    }
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->passWord = p;
    newNode->patlLoss = node->patlLoss + 1;
    gFlag[num] = 1;
    tail++;
    gQueue[tail] = newNode;
}

// 交换式的密码BFS搜索
void ExchangeSearch(int pos, Node *node)
{
    char *p = (char *)malloc(5 * sizeof(char));
    strcpy(p, node->passWord);
    Swap(p, pos);                              // 交换位置
    int num = atoi(p);                         // ATOI Str2Int
    if (gFlag[num]) {
        free(p);
        return;
    }
    Node *newNodeEx = (Node *)malloc(sizeof(Node));
    newNodeEx->passWord = p;
    newNodeEx->patlLoss = node->patlLoss + 1;
    gFlag[num] = 1;
    tail++;
    gQueue[tail] = newNodeEx;
}

int main()
{
    char initPassword[5];
    char rightPassword[5];
    scanf("%s", initPassword);
    scanf("%s", rightPassword);
    // 特殊场景补充判断
    if (strcmp(initPassword, rightPassword) == 0) {
        printf("0");
        return 0;
    }
    Node *initNode = (Node *)malloc(sizeof(Node));
    initNode->passWord = initPassword;
    initNode->patlLoss = 0;
    gQueue[tail] = initNode;
    int tmpHead = 0;
    int endFlag = 0;
    while (head <= tail) {
        Node *node = gQueue[head++]; // 出队
        Node *tmpNode = (Node *)malloc(sizeof(Node));
        while ((tmpNode != NULL) && (tmpHead <= tail)) {
            tmpNode = gQueue[tmpHead];
            if (strcmp(rightPassword, tmpNode->passWord) == 0) {
                printf("%d", tmpNode->patlLoss);
                endFlag = 1;
                break;
            }
            tmpHead++;
        }
        if (endFlag == 1) {
            break;
        }
        for (int i = 0; i < 4; i++) {
            NoExchangeSearch(i, node, 1); // 进行递减方向
            NoExchangeSearch(i, node, 0); // 进行递增方向
        }
        for (int i = 0; i < 3; i++) {     // 进行位置交换
            ExchangeSearch(i, node);
        }
    }
    return 0;
}

Dota

输入样例 1 复制
4
0000
0000
0000
0000
输出样例 1
3

//主要考点：广度优先搜索  注意：走过的点可以重复走，如果重新经过该点需要的步骤更少
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100001
#define MAX_STEP 999999
#define ROW 51
#define COL 51
typedef struct Node {
    int x;
    int y;
    int step;
} Node;
int main()
{
    int N;
    scanf("%d", &N);
    char map[ROW][COL];
    int  visited[ROW][COL] = {0};
    int  minstep = MAX_STEP;
    int  step;
    const int stepX[8] = {0,  0, 2, -2, 1, -1, -2,  2};
    const int stepY[8] = {1, -1, 2, -2, 0,  0,  2, -2}; // 可以移动8个方向
    Node queue[MAX_SIZE];
    int  head = 0, tail = 0;
    int  nextX, nextY;

    for (int i = 0; i < N; i++) {
        scanf("%s", &map[i]);
    }
    memset(visited, 0, sizeof(int)*ROW*COL);
    queue[tail].x = 0;
    queue[tail].y = 0;
    queue[tail++].step = 0; // 首元素入队
    visited[0][0] = 1;
    while (tail != head) {  // 当队列不为空循环
        for (int k = 0; k < 8; k++) {
            nextX = queue[head].x + stepX[k];
            nextY = queue[head].y + stepY[k];
            // 越界处理
            if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) {
                continue;
            }
            // 障碍处理
            if (map[nextX][nextY] == '1') { // ‘1’表示障碍，遇到障碍返回
                continue;
            }
            step = queue[head].step + 1;    // 计算消耗的步数
            if (map[nextX][nextY] == '2') { // ‘2’表示陷阱，减速step++
                step++;
            }
            // 入队条件：对于已经来过的地方，时间更短的入队；如果没有来过，直接入队
            if (step < visited[nextX][nextY] || visited[nextX][nextY] == 0) {
                queue[tail].x = nextX;
                queue[tail].y = nextY;
                queue[tail++].step = step;
                visited[nextX][nextY] = step;
            }
            // 如果已经到达终点 仍需继续搜索 记录此时需要的步骤
            if ((nextX == N - 1) && (nextY == N - 1)) { 
                minstep = (minstep > step ? step : minstep);
                break;
            }
        }
        head++; // 出队，继续向8个方向遍历.
    }
    if (MAX_STEP == minstep) {
        printf("Impossible");
    } else {
        printf("%d",minstep);
    }
    return 0;
}

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
路径途经的所有单元格的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

const int INF = 0x3f3f3f3f;
typedef struct Pair {
    int first;
    int second;
} Pair;
int shortestPathBinaryMatrix(int **grid, int gridSize, int *gridColSize)
{
    if (grid[0][0] == 1) {
        return -1;
    }
    int n = gridSize;
    int dist[n][n];
    Pair queue[n * n];
    int head = 0, tail = 0;
    memset(dist, 0x3f, sizeof(dist));
    queue[tail].first = 0; // 根节点入队列
    queue[tail].second = 0;
    tail++;
    dist[0][0] = 1;
    while (head != tail) {
        int x = queue[head].first;
        int y = queue[head].second;
        head++; // 出队列
        if (x == n - 1 && y == n - 1) {
            return dist[x][y];
        }
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (x + dx < 0 || x + dx >= n || y + dy < 0 || y + dy >= n) { // 越界
                    continue;
                }
                if (grid[x + dx][y + dy] == 1 || dist[x + dx][y + dy] <= dist[x][y] + 1) { // 单元格值不为 0 或已被访问
                    continue;
                }
                dist[x + dx][y + dy] = dist[x][y] + 1;
                // 符合条件的节点入队列
                queue[tail].first  = x + dx;
                queue[tail].second = y + dy;
                tail++;
            }
        }
    }
    return -1;
}

1162. 地图分析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

#define MAX_NODE_NUM 10000
typedef struct {
    int x;
    int y;
}node;
int dir[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int maxDistance(int **grid, int gridSize, int *gridColSize)
{
    node queueList[MAX_NODE_NUM];
    int head = 0;
    int tail = 0;
    // 将所有的陆地都加入队列中 -- 多源BFS
    for (int i = 0; i < gridSize; i++) {
        for (int j = 0; j < gridColSize[0]; j++) {
            if (grid[i][j] == 1) {
                queueList[tail].x = i;
                queueList[tail].y = j;
                tail++;
            }
        }
    }
    int  maxDis = -1;
    bool isHasOcean = false;
    while (head < tail) {
        int size = tail - head;
        for (int i = 0; i < size; i++) {
            node temp = queueList[head++];
            for (int j = 0; j < 4; j++) {
                int tempX = temp.x + dir[j][0];
                int tempY = temp.y + dir[j][1];
                if (tempX < 0 || tempX >= gridSize || tempY < 0 || tempY >= gridColSize[0]) {
                    continue;
                }
                // 如果该坐标的值不为0，说明他已经被遍历了，不需要重复遍历
                if (grid[tempX][tempY] != 0) {
                    continue;
                }
                // 用于记录图中是否有海洋，如果没有就不需要遍历了。
                isHasOcean = true;
                grid[tempX][tempY] = grid[temp.x][temp.y] + 1;
                queueList[tail].x = tempX;
                queueList[tail].y = tempY;
                tail++;
            }
            // 这里如果当前值的是2，那么这个点的位置离原始的陆地"1"的距离为 2 - 1
            maxDis = grid[temp.x][temp.y] - 1;
        }
    }
    if (maxDis == -1 || isHasOcean == false) {
        return -1;
    }
    return maxDis;
}

3243. 新增道路查询后的最短距离 I

给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
示例 1：
输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：

新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。

#include <stdlib.h>
#include <string.h>
// 定义队列操作
int queue[505];
int head, tail;
void push(int x) {
    queue[tail++] = x;
}
int pop() {
    int x = queue[head];
    head++;
    return x;
}
int empty() {
    return head >= tail;
}
int *shortestDistanceAfterQueries(int n, int **queries, int queriesSize, int *queriesColSize, int *returnSize)
{
    memset(queue, 0, sizeof(queue));
    head = tail = 0;
    // 初始化邻接表
    int graph[505][505];
    int graphSize[505] = {0};
    for (int i = 1; i < n; ++i) {
        // 添加边 i-1 -> i
        int u = i - 1;
        graph[u][graphSize[u]++] = i;
    }
    int *res = (int *)malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    for (int q = 0; q < queriesSize; ++q) {
        int u = queries[q][0];
        int v = queries[q][1];
        graph[u][graphSize[u]++] = v;
        // BFS
        int dist[505]; // 存最短路 dist[i]表示 0到i的最短路
        memset(dist, -1, sizeof(dist)); // 1e18 正无穷
        dist[0] = 0;
        head = tail = 0;
        push(0);
        while (!empty()) {
            int x = pop();
            if (x == n - 1) {
                break;
            }
            for (int i = 0; i < graphSize[x]; ++i) {
                int nxt = graph[x][i];
                if (dist[nxt] == -1) {
                    dist[nxt] = dist[x] + 1;
                    push(nxt);
                }
            }
        }
        res[q] = dist[n-1];
    }
    return res;
}