零 题目：算法（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 历史文章 - 总览

文章名称解法浏览量
1. 两数之和（Two Sum）共 3 种2.7 k+
2. 两数相加 （Add Two Numbers）共 4 种2.7 k+
3. 无反复字符的最长子串（Longest Substring Without Repeating Characters）共 3 种2.6 k+
4. 寻找两个正序数组的中位数（Median of Two Sorted Arrays）共 3 种2.8 k+
5. 最长回文子串（Longest Palindromic Substring）共 4 种2.8 k+
6. Z 字形变换（ZigZag Conversion）共 2 种1.9 k+
7. 整数反转（Reverse Integer）共 2 种2.4 k+
8. 字符串转换整数 (atoi)（String to Integer (atoi)）共 3 种4.2 k+
9. 回文数（Palindrome Number）共 3 种4.3 k+
11. 盛最多水的容器（Container With Most Water）共 5 种4.0 k+
12. 整数转罗马数字（Integer to Roman）共 3 种3.2 k+
13. 罗马数字转整数（Roman to Integer）共 3 种3.8 k+
14. 最长公共前缀（Longest Common Prefix）共 4 种3.0 k+
15. 三数之和（3Sum）共 3 种60.7 k+
16. 最靠近的三数之和（3Sum Closest）共 3 种4.7 k+
17. 电话号码的字母组合（Letter Combinations of a Phone Number）共 3 种3.1 k+
18. 四数之和（4Sum）共 4 种11.5 k+
19. 删除链表的倒数第 N 个结点（Remove Nth Node From End of List）共 4 种1.2 k+
20. 无效的括号（Valid Parentheses）共 2 种1.8 k+
21. 合并两个有序链表（Merge Two Sorted Lists）共 3 种1.2 k+
22. 括号生成（Generate Parentheses）共 4 种1.1 k+
23. 合并K个升序链表（Merge k Sorted Lists）共 4 种0.9 k+
24. 两两替换链表中的节点（Swap Nodes in Pairs）共 3 种0.5 k+
25. K 个一组翻转链表（Reverse Nodes in k-Group）共 5 种1.3 k+
26. 删除有序数组中的反复项（Remove Duplicates from Sorted Array）共 4 种1.3 k+
27. 移除元素（Remove Element）共 4 种0.4 k+
28. 实现 strStr()（Implement strStr()）共 5 种0.8 k+
29. 两数相除（Divide Two Integers）共 4 种0.6 k+
30. 串联所有单词的子串（Substring with Concatenation of All Words）共 3 种0.6 k+
31. 下一个排列（Next Permutation）共 2 种0.8 k+
32. 最长无效括号（Longest Valid Parentheses）共 2 种1.4 k+
33. 搜寻旋转排序数组（Search in Rotated Sorted Array）共 3 种1.0k+
34. 在排序数组中查找元素的第一个和最初一个地位（Find First and Last Position of Element in Sorted Array）共 3 种0.5 k+
35. 搜寻插入地位（Search Insert Position）共 3 种0.3 k+
36. 无效的数独（Valid Sudoku）共 1 种0.6 k+
38. 外观数列（Count and Say）共 5 种1.1 k+
39. 组合总和（Combination Sum）共 3 种1.4 k+
40. 组合总和 II（Combination Sum II）共 2 种1.6 k+
41. 缺失的第一个负数（First Missing Positive）共 3 种1.2 k+
53. 最大子数组和（Maximum Subarray）共 3 种0.3k+
88. 合并两个有序数组（Merge Sorted Array）共 3 种0.4 k+
102. 二叉树的层序遍历（Binary Tree Level Order Traversal）共 3 种0.4 k+
146. LRU 缓存（LRU Cache）共 2 种0.5 k+
206. 反转链表（Reverse Linked List）共 3 种1.0 k+
215. 数组中的第K个最大元素（Kth Largest Element in an Array）共 3 种0.5 k+
236. 二叉树的最近公共先人（Lowest Common Ancestor of a Binary Tree）共 3 种0.1 k+

2 博主简介

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