Google 面试题：岛屿的个数 II

zzzrf：给定 n, m, 分别代表一个二维矩阵的行数和列数, 并给定一个大小为 k 的二元数组 A. 初始二维矩阵全 0. 二元数组 A 内的 k 个元素代表 k 次操作, 设第 i 个元素为 (A[i].x, A[i].y), 表示把二维矩阵中下标为 A[i].x 行 A[i].y 列的元素由海洋变为岛屿. 问在每次操作之后, 二维矩阵中岛屿的数量. 你需要返回一个大小为 k 的数组.

• 设定 0 表示海洋, 1 代表岛屿, 并且上下左右相邻的 1 为同一个岛屿.

点此做题

样例 1:

输入: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
输出: [1,1,2,2]

解释: 
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011

样例 2:

输入: n = 3, m = 3, A = [[0,0],[0,1],[2,2],[2,1]]
输出: [1,1,2,2]

方法一：暴力做法

• 每次操作后做一遍 bfs
• 枚举之前未访问过的岛屿，岛屿数量加一
• 压入队列中开始 bfs
• 从 bfs 的队列中取出队首，上下左右四个方向扩展那些没有访问过的岛屿，扩展之后压入队列中
• 重复执行第四步，一直到队列为空
• 这样从一个岛屿出发，搜索了它能到的所有岛屿，这些岛屿将合并成一个大岛屿
• 重新回到第二步

方法二：并查集维护

并查集是指用集合里的一个元素来当这个集合的代表元
如果两个元素所在集合的代表元相同，那么我们就能知道这两个元素在一个集合当中。
如果我们想合并两个集合，只需要把其中一个集合的代表元改为第二个集合的代表元

• 这道题中，每次将一个海洋 i 变成一个岛屿 i，那么先将岛屿数量加一
• 再依次查看这个岛屿的四周的四个方格
  • 如果相邻的方格 j 也是岛屿，那么先判断 i 是不是和 j 在同一个集合里
  • 如果不是在一个集合里，那么 i j 所在的两个集合就是连通的，可以合并算为一个集合,然后让岛屿数量-1 。
  • 如果已经是在同一个集合里了，那就不用在进行任何操作
• 我们只要让 i 所在集合的代表元改为 j 所在集合的代表元就完成了合并操作。
• 注意：数据中有可能多次将一个位置变成岛屿，第一次以后的操作都是无效的操作，跳过就好了
• 注意 2：x->x1->x2->x3->x4->x5->x6->........->代表元 T
  我们在第一次寻找 x 的代表元的回溯的时候
  顺便把这条路径的所有 xi 的父亲改为了代表元 T
  这样我们以后再次访问 x....x6....T 这条链上的内容时候就可以很快的得到答案

//伪代码 for i 1:n
fa[i]=i //伪代码，一开始让所有的父亲都是本身
//我们规定代表元的父亲为本身，如果一个节点的父亲不是本身，说是它在一个元素个数大于 1 的集合中，而且这个节点并不是代表元
function find(x) //寻找 x 所在集合的代表元
if(fa[x]==x)
return x; //x 是代表元，直接返回
else
return fa[x]=find(fa[x]) //x 不是代表元，寻找 x 的父亲的代表元是谁，并且直接把代表元赋值给 x 的父亲
function uniue （ x,y ）//合并两个集合
fa[find(x)]=find(y)

复杂度分析

时间复杂度

暴力做法

每次操作都会做一遍 bfs，做一遍 bfs 的时间复杂度是 O(NM)
所以总时间复杂度是 O(KNM)，K 是操作次数，NM 是地图长和宽
并查集
每次查询代表元均摊是 O(α) α代表反阿克曼函数，反阿克曼函数是渐进增长很慢很慢的，我们可以近似的认为每次查询是 O(1)的复杂度 我们一共有 K 次操作，每次操作最多并查集查询 4 次，并查集合并 4 次,所以我们最终的时间复杂度是 O(K)的

空间复杂度

n，m 是输入数组 的长和宽
我们需要一个 fa 数组大小为 nm，一个 vis 数组（标记该点有没有变成岛屿），所以空间复杂度是 O(nm)

public class Solution {
    /**
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */

    public int find(int []fa, int x) {
        if(x == fa[x]) {
            return x;
        } else {
            return fa[x] = find(fa, fa[x]);
        }
    }
    public int calc(int x, int y, int n, int m) {
        return x * m + y;
    }
    public List<Integer> numIslands2(int n, int m, Point[] operators) {

        // write your code here
        List<Integer> ans = new ArrayList<>();
        int [] fa = new int [n * m + 5];
        Map<Integer, Boolean>visited = new HashMap<Integer, Boolean>();
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                fa[calc(i, j, n, m)] = calc(i, j, n, m);
                visited.put(calc(i, j, n, m), false);
            }
        }
        //行走数组，用于遍历 i 岛屿的四周四个方向的岛屿下标
        int[] zx = {0, 0, 1, -1};
        int[] zy = {1, -1, 0, 0};

        if(operators == null) {
            return ans;
        }
        for(int i = 0; i < operators.length; i++) {



            int x = operators[i].x, y = operators[i].y;
            // 第 i 次操作的点 已经是岛屿了，跳过就好了
            if(visited.get(calc(x, y, n, m)) == true) {
                ans.add(cnt);
                continue;
            }
            //第 i 次操作的点 出现了新的岛屿
            cnt++;
            //遍历这个岛屿的四周四个方向
            for(int k = 0; k < 4; k++) {
                int nx = x + zx[k];
                int ny = y + zy[k];
                //判断往四周走有没有走越界，或者走到海洋里，越界或者走到海洋都是没有的状态
                if(nx < 0 || nx >= n || ny < 0 || ny >= m || visited.get(calc(nx, ny, n, m)) == false) {
                    continue;
                }
                //判断四周的岛屿是不是和当前第 i 次操作的岛屿 已经在一个集合了
                if(find(fa, calc(x, y, n, m)) == find(fa, calc(nx, ny, n, m))) {
                    continue;
                }
                /*
                如果不是在一个集合里，那么 i j 所在的两个集合就是连通的，可以合并算为一个集合,然后让岛屿数量-1 。
                我们只要让 i 所在集合的代表元改为 j 所在集合的代表元就完成了合并操作
                */
                else {
                    cnt--;
                    fa[find(fa, calc(x, y, n, m))] = find(fa, calc(nx, ny, n, m));
                }
            }
            //标记它是个岛屿
            visited.put(calc(x, y, n, m), true);
            ans.add(cnt);
        }
        return ans;
    }
}

Google 的磁悬浮负载均衡器

holinhot：https://research.google/pubs/pub44824/ 想试一试这个磁悬浮负载均衡器， 文档我看了，说得很牛逼的样子，但是我找了很久没找到在哪下载啊。 难道不是开源的，只是出来水一下让大家看吗？holinhot：https://opensource.google/projects/list/featured 在这也没找…

Google Chrome Helper 问题

fox：macbook 疯狂风扇旋转，cpu100，一看是 Google Chrome Helper 占了 99 的 cpu，沙掉就好了。 这个问题几天内发生了两次了，查了一下似乎是一个历史遗留问题。 都 2020 年了，为啥还没修复这个问题。

谷歌云(Google Cloud)免费政策改变了？只有三个月了吗？

jememouse：https://cloud.google.com/free/docs/gcp-free-tier?hl=zh-cn 有没有朋友最近新建过，是否只有三个月了？Tink：是的 gqbre：握草。。 白嫖的日子一去不复返 trepwq：是…

LeetCode题解212. 单词搜索 II

给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。示例:输入: words = ["oath","pea","eat","rain"] and bo…

LeetCode题解45.跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…