数组

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

理论介绍
源码分析
数据结构实现？
题目练习（按照算法思想分类）
梳理对应的 sdk 包
应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

简单介绍1，重点为4。其他不是本系列的重点。

chat

知识碎片

好，那我就帮你从 零基础 到能独立写出 LC200（甚至类似题秒杀）的知识递进路线，分成 4 个阶段，每个阶段都有明确目标、示例题和“刷题模板”。

阶段 1：认识图和遍历方式

目标：先搞懂什么是图，什么是遍历，然后学 DFS / BFS 这两把万能钥匙。

什么是图
- 图由 节点（点） + 边构成。
- 分为 无向图（双向通路）和 有向图（单向通路）。
- 二维网格可以看作一个特殊的无向图：每个格子是一个节点，和上下左右的格子相连。
DFS（深度优先搜索）
- 类似“走迷宫”：沿着一个方向一直走，走到尽头回溯换路。
- 实现方式：
  - 递归
  - 栈（stack）
BFS（广度优先搜索）
- 像“水波扩散”：先访问一圈的邻居，再访问邻居的邻居。
- 实现方式：
  - 队列（queue）

练习题（不用二维的）：

LC733. Flood Fill（简化版）
LC133. Clone Graph（只需理解 BFS / DFS 遍历图）

阶段 2：把二维数组当成图来遍历

目标：学会把二维网格看成“图”，并写出四方向遍历模板。

二维网格的遍历规则
- 每个格子 (i, j) 的邻居通常是：
```
上: (i-1, j)
下: (i+1, j)
左: (i, j-1)
右: (i, j+1)
```
- 有时还包括斜对角（八方向），但 LC200 只用四方向。
四方向遍历模板

int[][] dirs = {
   {1,0},{-1,0},{0,1},{0,-1}
};

void dfs(int i, int j, char[][] grid) {
    if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') return;
    grid[i][j] = '0'; // 标记已访问
    for (int[] d : dirs) {
        dfs(i + d[0], j + d[1], grid);
    }
}

visited 标记的两种方式
- 用额外数组 boolean[][] visited
- 直接改原数组（常见做法）

练习题：

LC733. Flood Fill（用 DFS / BFS 都做一遍）
LC463. Island Perimeter（熟悉网格判断边界）

阶段 3：连通分量的概念

目标：掌握“数有多少块连在一起的区域”这种思路。

连通分量（Connected Component）
- 如果两个节点能通过路径互相到达，它们在同一个连通分量。
- “数岛屿” = 数二维网格中的连通分量个数。
套路
- 遍历所有格子：
  - 如果遇到 未访问的陆地（1），岛屿数 +1
  - 用 DFS 或 BFS 把这一整片陆地“淹掉”，避免重复计数

伪代码：

count = 0
for i in range(行数):
    for j in range(列数):
        if grid[i][j] == '1':
            count++
            dfs(i, j, grid)

练习题：

LC200. Number of Islands（目标题）
LC695. Max Area of Island（求每块的面积，而不是数量）
LC547. Number of Provinces（邻接矩阵版）

阶段 4：进阶与类比迁移

目标：学会把这种遍历套路迁移到别的场景。

变化形式

* 求面积（LC695） * 求最大最小值（LC1020 飞地的数量）
- 多个起点 BFS（LC994 腐烂的橘子）
- 八方向（LC1254 封闭岛屿的数量）
核心思维
- “找一片” → DFS/BFS → “标记掉” → 防止重复访问
高阶优化
- 并查集（Union-Find）实现岛屿计数（在面试中加分）

leetcode 算法篇专题之图 graph 02-一步步提升图的知识能力

数组