注：純手打，如有錯誤歡迎評論區交流！
轉載請注明出處：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)*/