拼多多一面笔试原题,15分钟没做出来,直接挂了。。。

2023-12-15 13:55:51 浏览数 (1)

大家好,我是吴师兄。今天来学一下拼多多社招一面的算法题。

先看题目描述。

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

示例 1:

代码语言:javascript复制
输入:grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出:1

示例 2:

代码语言:javascript复制
输入:grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出:3

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] 的值为 '0''1'

LeetCode 上有一些与岛屿相关的题目,这些题目通常涉及图的遍历、深度优先搜索(DFS)、广度优先搜索(BFS)等算法,这些题目的解法大同小异,甚至在代码层面都相差无几,所以只要彻底掌握一道,其它的岛屿题目都能顺利拿下

下面这些题目,能弄懂一道就够了。

  1. 题目:200. Number of Islands
    • 考察重点: 图的遍历,DFS/BFS
    • 解题技巧: 使用 DFS 或 BFS 遍历岛屿,将访问过的地块标记,以避免重复计算。
  2. 题目:695. Max Area of Island
    • 考察重点: 图的遍历,DFS/BFS
    • 解题技巧: 类似于寻找岛屿数量,但是需要记录并更新每个岛屿的面积。
  3. 题目:463. Island Perimeter
    • 考察重点: 图的遍历
    • 解题技巧: 遍历每块陆地,计算其边界与水域相邻的边的数量。
  4. 题目:694. Number of Distinct Islands
    • 考察重点: 图的遍历,DFS/BFS,哈希
    • 解题技巧: 使用 DFS/BFS 遍历每个岛屿,并用哈希集合来记录不同的岛屿形状。
  5. 题目:1020. Number of Enclaves
    • 考察重点: 图的遍历,DFS/BFS
    • 解题技巧: 先从边界开始遍历,标记所有能够到达边界的陆地,然后计算剩余陆地块数。
  6. 题目:305. Number of Islands II
    • 考察重点: 并查集,动态图的更新
    • 解题技巧: 在陆地不断增加的情况下,使用并查集来动态维护岛屿数量。
  7. 题目:827. Making A Large Island
    • 考察重点: 图的遍历,DFS/BFS,连通性
    • 解题技巧: 遍历每块陆地,计算各个岛屿的大小,然后尝试将小岛连接起来以形成更大的岛屿。

今天我们用并查集来解决。

代码语言:javascript复制
// 岛屿数量(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 高频算法题,涵盖了数组、链表、栈、队列、二叉树、回溯算法、动态规划等众多高频知识点,所选的题目也是非常有特征的题目,一题抵十题。

0 人点赞