其他
拼多多一面笔试原题，15分钟没做出来，直接挂了。。。
The following article is from 吴师兄学算法 Author 吴师兄
第一时间收到文章更新
今天来学一下拼多多社招一面的算法题。
先看题目描述。
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
输出：1
示例 2：
输入：grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
输出：3
提示：
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]的值为'0'或'1'
LeetCode 上有一些与岛屿相关的题目，这些题目通常涉及图的遍历、深度优先搜索（DFS）、广度优先搜索（BFS）等算法，这些题目的解法大同小异，甚至在代码层面都相差无几，所以只要彻底掌握一道，其它的岛屿题目都能顺利拿下。
下面这些题目，能弄懂一道就够了。
题目：200. Number of Islands
考察重点： 图的遍历，DFS/BFS 解题技巧： 使用 DFS 或 BFS 遍历岛屿，将访问过的地块标记，以避免重复计算。
考察重点： 图的遍历，DFS/BFS 解题技巧： 类似于寻找岛屿数量，但是需要记录并更新每个岛屿的面积。
考察重点： 图的遍历 解题技巧： 遍历每块陆地，计算其边界与水域相邻的边的数量。
考察重点： 图的遍历，DFS/BFS，哈希 解题技巧： 使用 DFS/BFS 遍历每个岛屿，并用哈希集合来记录不同的岛屿形状。
考察重点： 图的遍历，DFS/BFS 解题技巧： 先从边界开始遍历，标记所有能够到达边界的陆地，然后计算剩余陆地块数。
考察重点： 并查集，动态图的更新 解题技巧： 在陆地不断增加的情况下，使用并查集来动态维护岛屿数量。
考察重点： 图的遍历，DFS/BFS，连通性 解题技巧： 遍历每块陆地，计算各个岛屿的大小，然后尝试将小岛连接起来以形成更大的岛屿。
今天我们用并查集来解决。
// 岛屿数量（LeetCode 200）（并查集解法）：https://leetcode.cn/problems/number-of-islands/
class Solution {
private int rows;
private int cols;
public int numIslands(char[][] grid) {
rows = grid.length;
cols = grid[0].length;
// 水格的数量
int spaces = 0;
UnionFind unionFind = new UnionFind(rows * cols);
// 沿着每个网格的右方、下方去查找
int[][] directions = {{1, 0}, {0, 1}};
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 当前网格是水
if (grid[i][j] == '0') {
// 水格的数量增加
spaces++;
// 当前网格是陆地
} else {
// 沿着这个陆地的右方、下方这两个方向去查找
for (int[] direction : directions) {
// 新网格的 x 坐标
int newX = i + direction[0];
// 新网格的 y 坐标
int newY = j + direction[1];
// 如果新网格的坐标位于矩阵内
// 并且是陆地
if (newX < rows && newY < cols && grid[newX][newY] == '1') {
// 那么就把这两个网格连接起来
unionFind.union(getIndex(i, j), getIndex(newX, newY));
}
}
}
}
}
return unionFind.getCount() - spaces;
}
// 把这些二维网格进行编号
// 比如第 0 行第 0 列网格的编号是 0
// 比如第 0 行第 1 列网格的编号是 1
// 比如第 1 行第 1 列网格的编号是 5（一列有 5 个元素）
private int getIndex(int i, int j) {
return i * cols + j;
}
}
// 并查集
class UnionFind {
int[] roots;
int count;
public UnionFind(int n) {
// 使用一维数组用来记录每个网格的出发位置
roots = new int[n];
for (int i = 0; i < n ; i++) {
// 默认每个网格的出发位置是自己本身
roots[i] = i;
}
// 所以一开始有 n 个岛屿
count = n ;
}
// 寻找当前网格的出发位置
public int find(int i){
if( i == roots[i]) return i ;
roots[i] = find(roots[i]);
return roots[i];
}
// 连通操作，把陆地连接起来
public void union(int p, int q) {
// 寻找陆地 p 的出发位置
int pRoot = find(p);
// 寻找陆地 q 的出发位置
int qRoot = find(q);
// 如果两者的出发位置不同
// 那么需要采取操作把 p 和 q 所在的两堆网格合到一起
if (pRoot != qRoot) {
// 也就是把其中一个的最上面的出发位置挂过来就行
roots[pRoot] = qRoot;
// 与此同时，两堆陆地变成了一堆陆地
count--;
}
}
// 获取当前区间的所有连通量
public int getCount() {
// 也就是有多少陆地网格 + 水网格
return count;
}
}
我总结并录制了 100 道 LeetCode 高频算法题，涵盖了数组、链表、栈、队列、二叉树、回溯算法、动态规划等众多高频知识点，所选的题目也是非常有特征的题目，一题抵十题。