https://leetcode-cn.com/tag/breadth-first-search/
题目汇总
200. 岛屿数量中等[✔]
207. 课程表中等（图的知识，需要用到拓扑排序，没有做）
210. 课程表 II中等（图的知识，需要用到拓扑排序，没有做）
279. 完全平方数中等[✔]（只会动态规划的思路，没有想到可以用BFS）
301. 删除无效的括号困难（没做）
310. 最小高度树中等（图的知识）
200. 岛屿数量中等
给你一个由
'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
类似题目
- 463. 岛屿的周长 （简单）
- 695. 岛屿的最大面积 （中等）
- 827. 最大人工岛 （困难）
思路一：DFS
题目的意思就是求“1”连成一片的地方有几处。遍历整个矩阵，当遇到 grid[i][j] == '1' 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 。
class Solution {//执行用时 :2 ms, 在所有 Java 提交中击败了97.40%的用户
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0)
return 0;
int row = grid.length;
int col = grid[0].length;
int count = 0;
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == '1'){
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs(char[][] grid, int i, int j){
if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1')
return;
grid[i][j] = '2';//将格子标记为「已遍历过」，避免重复遍历
// 访问上、下、左、右四个相邻结点
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
思路二：BFS
转载https://leetcode-cn.com/problems/number-of-islands/solution/number-of-islands-shen-du-you-xian-bian-li-dfs-or-/
借用一个队列 queue，判断队列首部节点 (i, j) 是否未越界且为 1：
若是则置零（删除岛屿节点），并将此节点上下左右节点 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 加入队列；
若不是则跳过此节点；
循环 pop 队列首节点，直到整个队列为空，此时已经遍历完此岛屿。
class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了30.70%的用户
public int numIslands(char[][] grid) {
if(grid == null || grid.length == 0)
return 0;
int rows = grid.length;
int cols = grid[0].length;
int count = 0;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(grid[i][j] == '1'){
bfs(grid, i, j);
count++;
}
}
}
return count;
}
public void bfs(char[][] grid, int i, int j){
Queue<int[]> list = new LinkedList<>();
list.add(new int[] { i, j });
while(!list.isEmpty()){
int[] cur = list.remove();
i = cur[0]; j = cur[1];
if(i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == '1') {
grid[i][j] = '0';
list.add(new int[] { i + 1, j });
list.add(new int[] { i - 1, j });
list.add(new int[] { i, j + 1 });
list.add(new int[] { i, j - 1 });
}
}
}
}
207. 课程表中等
你这个学期必须选修
numCourse门课程，记为0到numCourse-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示：
- 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
210. 课程表 II中等
现在你总共有 n 门课需要选，记为
0到n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们:[0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
279. 完全平方数中等
给定正整数 n，找到若干个完全平方数（比如
1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。
示例 :
输入: n =13
输出: 2
解释:13 = 4 + 9.
思路：动态规划
时间复杂度：O(n*sqrt(n))，一个嵌套循环，其中外部循环是 n 次迭代，而内部循环最多需要 sqrt(n)次迭代
思路：BFS
https://leetcode-cn.com/problems/perfect-squares/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--51/的解法三：可以一层一层的算。第一层依次减去一个平方数得到第二层，第二层依次减去一个平方数得到第三层。直到某一层出现了 0，此时的层数就是我们要找到平方数和的最小个数。
class Solution {//执行用时：47 ms, 在所有 Java 提交中击败了44.35%的用户
public int numSquares(int n) {
Queue<Integer> queue = new LinkedList<>();
HashSet<Integer> visited = new HashSet<>();
int level = 0;
queue.add(n);
while (!queue.isEmpty()) {
int size = queue.size();
level++; // 开始生成下一层
for (int i = 0; i < size; i++) {
int cur = queue.poll();
//依次减 1, 4, 9... 生成下一层的节点
for (int j = 1; j * j <= cur; j++) {
int next = cur - j * j;
if (next == 0) {
return level;
}
if (!visited.contains(next)) {
queue.offer(next);
visited.add(next);
}
}
}
}
return -1;
}
}
