关于leetcode:200岛屿数量-算法leetcode附思维导图-全部解法300题

零 题目：算法（leetcode，附思维导图 + 全副解法）300 题之（200）岛屿数量

一 题目形容

二 解法总览（思维导图）

三 全副解法

1 计划 1

1)代码：

// 计划 1“本人。模仿 - 标记法”。// 思路：// 1）状态初始化：m = grid.length, n = grid[0].length;。// tempMap = new Map(), resMap = getMapByGrid(), resCount = 0;。// 2）外围：循环解决 —— 条件为 存在未被拜访过的海洋。// 3）返回后果 resCount。var numIslands = function(grid) {const getMapByGrid = () => {let resMap = new Map();

        for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === '1') {const tempVal = `${i}#${j}`;
                    resMap.set(tempVal, 1);
                }
            }
        }

        return resMap;
    };

    // 1）状态初始化：m = grid.length, n = grid[0].length;。// tempMap = new Map(), resMap = getMapByGrid(), resCount = 0;。const m = grid.length,
        n = grid[0].length;
    let // tempMap：目前已被拜访过的海洋。tempMap = new Map(),
        resMap = getMapByGrid(),
        resCount = 0;

    // 2）外围：循环解决 —— 条件为 存在未被拜访过的海洋。while (resMap.size !== 0) {for (const [key, val] of resMap) {if (!tempMap.has(key)) {tempMap.set(key, 1);
                let tempQueue = [key];
                
                while (tempQueue.length !== 0) {const key = tempQueue.shift(),
                        [tempI, tempJ] = key.split('#').map(v => parseInt(v));
                    
                    // 标记为已被拜访。resMap.delete(key);

                    // 4 个方向的拜访。// 上
                    if (tempI - 1 >= 0 && grid[tempI - 1][tempJ] === '1') {const key = `${tempI - 1}#${tempJ}`;
                        if (!tempMap.has(key)) {tempQueue.push(key);
                            tempMap.set(key, 1);
                        }
                    }
                    // 下

                    if (tempI + 1 < m && grid[tempI + 1][tempJ] === '1') {const key = `${tempI + 1}#${tempJ}`;
                        if (!tempMap.has(key)) {tempQueue.push(key);
                            tempMap.set(key, 1);
                        }
                    }
                    // 左
                    if (tempJ - 1 >= 0 && grid[tempI][tempJ - 1] === '1') {const key = `${tempI}#${tempJ - 1}`;
                        if (!tempMap.has(key)) {tempQueue.push(key);
                            tempMap.set(key, 1);
                        }
                    }
                    // 右
                    if (tempJ + 1 < n && grid[tempI][tempJ + 1] === '1') {const key = `${tempI}#${tempJ + 1}`;
                        if (!tempMap.has(key)) {tempQueue.push(key);
                            tempMap.set(key, 1);
                        }
                    }
                }

                // 以后岛屿无奈再次连贯到任何海洋了。resCount++;
            }
            break;
        }
    }

    // 3）返回后果 resCount。return resCount;
};

2 计划 2

1)代码：

// 计划 2“本人。深度优先搜寻法”。// 参考：// 1）https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/

// 思路：// 1）状态初始化：m = grid.length, n = grid[0].length;。// resCount = 0;
// 2）外围：遍历 grid。// 2.1）若 以后的格子为 海洋，则 岛屿数量减少 1 并 执行深度搜寻函数 —— dfs(i, j)。// 3）返回后果 resCount。var numIslands = function(grid) {
    // 深度搜寻（实现：递归）const dfs = (curI = 0, curJ = 0) => {
        // 1）递归进口：其实被暗藏起来 —— 当坐标超出格子范畴 或 坐标不符合条件时。// 2）递归主体。// 2.1）以后海洋置为 水。grid[curI][curJ] = '0';

        // 2.2）上下左右，四个方向执行深度搜寻。if (curI - 1 >= 0 && grid[curI - 1][curJ] === '1') {dfs(curI - 1, curJ);
        }
        if (curI + 1 < m && grid[curI + 1][curJ] === '1') {dfs(curI + 1, curJ);
        }
        if (curJ - 1 >= 0 && grid[curI][curJ - 1] === '1') {dfs(curI, curJ - 1);
        }
        if (curJ + 1 < n && grid[curI][curJ + 1] === '1') {dfs(curI, curJ + 1);
        }
    };

    // 1）状态初始化：m = grid.length, n = grid[0].length;。// resCount = 0;
    const m = grid.length,
        n = grid[0].length;
    let resCount = 0;

    // 2）外围：遍历 grid。for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {// 2.1）若 以后的格子为 海洋，则 岛屿数量减少 1 并 执行深度搜寻函数 —— dfs(i, j)。if (grid[i][j] === '1') {
                resCount++;
                dfs(i, j);
            }
        }
    }

    // 3）返回后果 resCount。return resCount;
};

3 计划 3

1)代码：

// 计划 3“广度优先搜寻法（实质：跟计划 1 差不多）”。// 参考：// 1）https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/

// 思路：// 1）状态初始化：m = grid.length, n = grid[0].length;
// resCount = 0;。// 2）外围：2 层循环的遍历。// 2.1）若 以后地位为 海洋，非凡解决，// 并 进行 广度优先（应用队列 queue）的遍历解决。// 3）返回后果 resCount。var numIslands = function(grid) {// 1）状态初始化：m = grid.length, n = grid[0].length;
    // resCount = 0;。const m = grid.length,
        n = grid[0].length;
    let resCount = 0;

    // 2）外围：2 层循环的遍历。for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {
            // 2.1）若 以后地位为 海洋，非凡解决，// 并 进行 广度优先（应用队列 queue）的遍历解决。if (grid[i][j] === '1') {grid[i][j] = '0';
                resCount++;
                let queue = [[i, j]];
                
                while (queue.length !== 0) {const [tempI, tempJ] = queue.shift();
                    // 上下左右，4 个方向。if (tempI - 1 >= 0 &&grid[tempI - 1][tempJ] === '1') {queue.push([tempI - 1, tempJ]);
                        grid[tempI - 1][tempJ] = '0';
                    }
                    if (tempI + 1 < m &&grid[tempI + 1][tempJ] === '1') {queue.push([tempI + 1, tempJ]);
                        grid[tempI + 1][tempJ] = '0';
                    }
                    if (tempJ - 1 >= 0 &&grid[tempI][tempJ - 1] === '1') {queue.push([tempI, tempJ - 1]);
                        grid[tempI][tempJ - 1] = '0';
                    }
                    if (tempJ + 1 < n &&grid[tempI][tempJ + 1] === '1') {queue.push([tempI, tempJ + 1]);
                        grid[tempI][tempJ + 1] = '0';
                    }
                }
            }
        }
    }

    // 3）返回后果 resCount。return resCount;
}

4 计划 4

1)代码：

// 计划 4“并查集法”。// 参考：// 1）https://leetcode.cn/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/

// 注：有问题，通过 12 / 49。TODO：排查问题 && 从新手撕。var numIslands = function(grid) {
    class Unionfind {constructor() {
            let count = 0,
                parent = [],
                rank = [];
            
            for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {
                    const tempIndex = n * i + j;
                    if (grid[i][j] === '1') {parent[tempIndex] = tempIndex;
                        count++;
                    }
                    //？rank[tempIndex] = 0;
                }
            }

            this.count = count;
            this.parent = parent;
            this.rank = rank;
        }

        find(index) {const {parent} = this;
            if (parent[index] !== index) {
                // 找到该坐标最开始的“先人”？parent[index] = this.find(parent[index]);
            }
            
            this.parent = parent;
            return parent[index];
        }

        union(index_1, index_2) {let {rank, parent, count} = this;

            const root_1 = this.find(index_1),
                root_2 = this.find(index_2);
            
            if (root_1 !== root_2) {if (rank[root_1] > rank[root_2]) {parent[root_2] = root_1;
                }
                else if (rank[root_1] < rank[root_2]) {parent[root_1] = root_2;
                }
                else {parent[root_2] = root_1;
                    //？rank[root_1] += 1;
                }
                count--;
            }
            
            this.count = count;
            this.parent = parent;
            this.rank = rank;
        }

        getCount() {const {count} = this;

            return count;
        }
    }

    const m = grid.length,
        n = grid[0].length;
    let unionfind = new Unionfind();

    for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === '1') {grid[i][j] = '0';
            }

            // 上下左右，4 个方向。const tempIndex = n * i + j;
            if (i - 1 >= 0 && grid[i - 1][j] === '1') {unionfind.union(tempIndex, n * (i - 1) + j);
            }
            if (i + 1 < m && grid[i + 1][j] === '1') {unionfind.union(tempIndex, n * (i + 1) + j);
            }
            if (j - 1 >= 0 && grid[i][j - 1] === '1') {unionfind.union(tempIndex, n * i + (j - 1));
            }
            if (j + 1 < n && grid[i][j + 1] === '1') {unionfind.union(tempIndex, n * i + (j + 1));
            }
        }
    }

    return unionfind.getCount();}

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少，一个致力于编写 极简、但齐全题解（算法 ）的博主。
专一于 一题多解、结构化思维，欢送一起刷穿 LeetCode ~