算法|ss dfsbfs

本文主要是介绍算法|ss dfsbfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

• 200.岛屿数量—1
• 207.课程表—1
• 547.省份数量
• 695.岛屿的最大面积

200.岛屿数量—1

/*** @param {character[][]} grid* @return {number}*/
var numIslands = function (grid) {let ans = 0;let m = grid.length;let n = grid[0].length;const dirs = [[1, 0],[-1, 0],[0, 1],[0, -1],];const checkList = Array(m).fill(0).map(() => Array(n).fill(0));for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (grid[i][j] === "1" && checkList[i][j] === 0) {ans += bfs(i, j);}}}function bfs(i, j) {let count = 1;const queue = [];queue.push([i, j]);while (queue.length) {const [x, y] = queue.pop();for (let [dx, dy] of dirs) {let nextX = dx + x;let nextY = dy + y;if (nextX >= 0 &&nextX < m &&nextY >= 0 &&nextY < n &&grid[nextX][nextY] === "1" &&checkList[nextX][nextY] === 0) {queue.push([nextX, nextY]);checkList[nextX][nextY] = 1;}}}return count;}return ans;
};
numIslands([["1", "1", "1", "1", "0"],["1", "1", "0", "1", "0"],["1", "1", "0", "0", "0"],["0", "0", "0", "0", "0"],
]);

207.课程表—1

// numCourses = 2, prerequisites = [[1,0]]
/*** @param {number} numCourses* @param {number[][]} prerequisites* @return {boolean}*/
var canFinish = function (numCourses, prerequisites) {const map = {};const nextMap = {};for (let [a, b] of prerequisites) {if (map[a] === undefined) {map[a] = 0;}if (nextMap[b] === undefined) {nextMap[b] = [];}map[a] += 1;nextMap[b].push(a);if (map[b] === undefined) map[b] = 0;}//const queue = [];for (let ch in map) {if (map[ch] === 0) {queue.push(ch);}}while (queue.length) {const cur = queue.shift();const nextCur = nextMap[cur];if (!nextCur) continue;for (let ch of nextCur) {map[ch] -= 1;if (map[ch] === 0) {queue.push(ch);}}}//   console.log(map);return Object.values(map).every((item) => item === 0);
};
canFinish(2, [[1, 0],[0, 1],
]);

547.省份数量

/*** @param {number[][]} isConnected* @return {number}*/
// 思路
// 遍历一层， 对没有检查的可以看作是一个省份
// 递归dfs，对相连的城市都去dfs一下，然后设置对应的checklist为1，
// dfs的作用就是使相连的城市的checklist都为1
var findCircleNum = function (isConnected) {const n = isConnected.length;const checklist = Array(n).fill(0);let ans = 0;for (let i = 0; i < n; i++) {if (checklist[i] === 0) {dfs(i);ans += 1;}}//   console.log(ans);return ans;function dfs(idx) {checklist[idx] = 1;for (let j = 0; j < n; j++) {if (j !== idx && checklist[j] === 0 && isConnected[idx][j] === 1) {dfs(j);}}}
};
findCircleNum([[1, 0, 0],[0, 1, 0],[0, 0, 1],
]);
// [[1,0,0],[0,1,0],[0,0,1]]

695.岛屿的最大面积

/*** @param {number[][]} grid* @return {number}*/
// 思路
// dfs的返回值 应该怎么定义
// 什么条件下返回
// 合格返回 1
// 不合格返回0
var maxAreaOfIsland = function (grid) {const m = grid.length;const n = grid[0].length;let ans = 0;let dirs = [[-1, 0],[1, 0],[0, 1],[0, -1],];const checklist = Array(m).fill(0).map(() => Array(n).fill(0));for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {if (checklist[i][j] === 0 && grid[i][j] === 1) {ans = Math.max(ans, dfs(i, j));}}}//   console.log(ans);return ans;function dfs(x, y) {// 不符合条件的return 0if (x < 0 ||x >= m ||y < 0 ||y >= n ||grid[x][y] === 0 ||checklist[x][y] === 1) {return 0;}let ans = 1;// 符合条件的返回anschecklist[x][y] = 1;for (let [dx, dy] of dirs) {ans += dfs(dx + x, dy + y);}return ans;}
};
maxAreaOfIsland([[0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],[0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],[0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0],[0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0],[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],[0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0],[0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0],
]);
// [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]

这篇关于算法|ss dfsbfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---