注：纯手打，如有错误欢迎评论区交流！
转载请注明出处：https://blog.csdn.net/testleaf/article/details/148953015
编写此文是为了更好地学习前端知识，如果损害了有关人的利益，请联系删除！
本文章将不定时更新，敬请期待！！！
欢迎点赞、收藏、转发、关注，多谢！！！
前端JavaScript力扣HOT100刷题【1-50】：
https://blog.csdn.net/testleaf/article/details/147258015

九、图论

51、【中等】岛屿数量

题目描述：
给你一个由 '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

/*** @param {character[][]} grid* @return {number}*/
var numIslands = function(grid) {const m = grid.length, n = grid[0].length;function dfs(i, j) {// 出界，或者不是 '1'，就不再往下递归if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== '1') {return;}grid[i][j] = '2'; // 插旗！避免来回横跳无限递归dfs(i, j - 1); // 往左走dfs(i, j + 1); // 往右走dfs(i - 1, j); // 往上走dfs(i + 1, j); // 往下走}let ans = 0;for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === '1') { // 找到了一个新的岛dfs(i, j); // 把这个岛插满旗子，这样后面遍历到的 '1' 一定是新的岛ans++;}}}return ans;
};

52、【中等】腐烂的橘子

题目描述：
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：
输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

/*** @param {number[][]} grid* @return {number}*/
var orangesRotting = function(grid) {const m = grid.length, n = grid[0].length;let fresh = 0;let q = [];for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === 1) {fresh++; // 统计新鲜橘子个数} else if (grid[i][j] === 2) {q.push([i, j]); // 一开始就腐烂的橘子}}}let ans = 0;while (fresh && q.length) {ans++; // 经过一分钟const tmp = q;q = [];for (const [x, y] of tmp) { // 已经腐烂的橘子for (const [i, j] of [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]) { // 四方向if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] === 1) { // 新鲜橘子fresh--;grid[i][j] = 2; // 变成腐烂橘子q.push([i, j]);}}}}return fresh ? -1 : ans;
};

53、【中等】课程表

题目描述：
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

/*** @param {number} numCourses* @param {number[][]} prerequisites* @return {boolean}*/
var canFinish = function(numCourses, prerequisites) {const g = Array.from({ length: numCourses }, () => []);for (const [a, b] of prerequisites) {g[b].push(a);}const colors = Array(numCourses).fill(0);// 返回 true 表示找到了环function dfs(x) {colors[x] = 1; // x 正在访问中for (const y of g[x]) {if (colors[y] === 1 || colors[y] === 0 && dfs(y)) {return true; // 找到了环}}colors[x] = 2; // x 完全访问完毕return false; // 没有找到环}for (let i = 0; i < numCourses; i++) {if (colors[i] === 0 && dfs(i)) {return false; // 有环}}return true; // 没有环
};

54、【中等】实现 Trie (前缀树)

题目描述：
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

示例：
输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

解释

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

var Trie = function() {this.root = new Node();
};function Node() {this.son = Array(26).fill(null);this.end = false;
}/** * @param {string} word* @return {void}*/
Trie.prototype.insert = function(word) {let cur = this.root;for (let c of word) {c = c.charCodeAt(0) - 'a'.charCodeAt(0);if (cur.son[c] === null) {cur.son[c] = new Node();}cur = cur.son[c];}cur.end = true;
};Trie.prototype._find = function(word) {let cur = this.root;for (let c of word) {c = c.charCodeAt(0) - 'a'.charCodeAt(0);if (cur.son[c] === null) {return 0;}cur = cur.son[c];}return cur.end ? 2 : 1;
};/** * @param {string} word* @return {boolean}*/
Trie.prototype.search = function(word) {return this._find(word) === 2;
};/** * @param {string} prefix* @return {boolean}*/
Trie.prototype.startsWith = function(prefix) {return this._find(prefix) !== 0;
};/** * Your Trie object will be instantiated and called as such:* var obj = new Trie()* obj.insert(word)* var param_2 = obj.search(word)* var param_3 = obj.startsWith(prefix)*/