问题模板
为什么要将格子标记为【已遍历】—避免 重复遍历
（这是因为，网格结构本质上是一个「图」，我们可以把每个格子看成图中的结点，每个结点有向上下左右的四条边。在图中遍历时，自然可能遇到重复遍历结点。这时候，DFS 可能会不停地「兜圈子」，永远停不下来
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
200. 岛屿数量
class Solution {
public int numIslands(char[][] grid) {
if(grid==null||grid.length==0)
return 0;
int cnt=0;
int m=grid.length;
int n =grid[0].length;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]=='1')
{
cnt++;
dfs(grid,i,j);
}
}
}
return cnt;
}
void dfs(char[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != '1') {
return;
}
grid[r][c] = '2'; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(char[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
695. 岛屿的最大面积
这道题同样根据dfs模板走，只不过区别是dfs返回值变成了 1+dfs(上下左右)的面积
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int max_area=0;
for(int i = 0;i<m;i++)
{
for(int j=0;j<n;j++)
{
int temp_area=dfs(grid,i,j);
max_area=Math.max(max_area,temp_area);
}
}
return max_area;
}
int dfs(int[][] grid,int r,int c)
{
int m = grid.length;
int n= grid[0].length;
if(!inArea(grid,r,c))
return 0;
//不是岛屿 直接返回
if(grid[r][c]!=1)
return 0;
grid[r][c]=2;
return 1+
dfs(grid,r-1,c)
+dfs(grid,r+1,c)
+dfs(grid,r,c-1)
+dfs(grid,r,c+1);
}
boolean inArea(int[][] grid,int r,int c)
{
return r>=0&&r<grid.length&&c>=0&&c<grid[0].length;
}
}
463. 岛屿的周长
岛屿的周长是计算岛屿全部的「边缘」，而这些边缘就是我们在 DFS 遍历中，dfs 函数返回的位置。
当我们的 dfs 函数因为「坐标 (r, c) 超出网格范围」返回的时候，实际上就经过了一条黄色的边；而当函数因为「当前格子是海洋格子」返回的时候，实际上就经过了一条蓝色的边
class Solution {
public int islandPerimeter(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
// 题目限制只有一个岛屿，计算一个即可
return dfs(grid, r, c);
}
}
}
return 0;
}
int dfs(int[][] grid, int r, int c) {
// 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
if (!inArea(grid, r, c)) {
return 1;
}
// 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
if (grid[r][c] == 0) {
return 1;
}
// 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = 2;
return dfs(grid, r - 1, c)
+ dfs(grid, r + 1, c)
+ dfs(grid, r, c - 1)
+ dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
另一类bfs问题
994. 腐烂的橘子
想象以污染的橘子为污染源，然后将相邻的橘子一层一层污染，考虑BFS
class Solution{
public int orangesRotting(int[][] grid) {
int M = grid.length;
int N = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int count = 0; // count 表示新鲜橘子的数量
for (int r = 0; r < M; r++) {
for (int c = 0; c < N; c++) {
if (grid[r][c] == 1) {
count++;
}
//一开始，我们找出所有腐烂的橘子，将它们放入队列，作为第 0 层的结点。
//就是污染源
else if (grid[r][c] == 2) {
queue.add(new int[]{r, c});
}
}
}
int round = 0; // round 表示腐烂的轮数，或者分钟数
while (count > 0 && !queue.isEmpty()) {
round++;
int n = queue.size();
for (int i = 0; i < n; i++) {
int[] orange = queue.poll();
int r = orange[0];
int c = orange[1];
//将相邻方向依次污染
if (r-1 >= 0 && grid[r-1][c] == 1) {
grid[r-1][c] = 2;
count--;
queue.add(new int[]{r-1, c});
}
if (r+1 < M && grid[r+1][c] == 1) {
grid[r+1][c] = 2;
count--;
queue.add(new int[]{r+1, c});
}
if (c-1 >= 0 && grid[r][c-1] == 1) {
grid[r][c-1] = 2;
count--;
queue.add(new int[]{r, c-1});
}
if (c+1 < N && grid[r][c+1] == 1) {
grid[r][c+1] = 2;
count--;
queue.add(new int[]{r, c+1});
}
}
}
if (count > 0) {
return -1;
} else {
return round;
}
}
}
207. 课程表
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//判断是否是有向无环图-------》拓扑排序
//通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency
//统计课程安排图中每个节点的入度，生成 入度表 indegrees。
//借助一个队列 queue，将所有入度为 0 的节点入队。
//拓扑排序过程
//删顶点 再把顶点的出边删掉，即对应所有邻接节点的入度-1
//当入度 −1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，
//此时将 cur 入队。
int[] indegree = new int[numCourses];
List<List<Integer>> adjacent = new ArrayList<>();
Queue<Integer> list = new LinkedList<>();
for(int i=0;i<numCourses;i++)
adjacent.add(new ArrayList<>());
for(int[] tmp : prerequisites) {
indegree[tmp[0]]++;
adjacent.get(tmp[1]).add(tmp[0]);
}
//将所以入度为0的节点入队
for(int i=0;i<numCourses;i++)
{
if(indegree[i]==0)
list.add(i);
}
//排序过程
while(!list.isEmpty())
{
int pre =list.poll();
numCourses--;
//他的邻接节点入度--
for(int tmp :adjacent.get(pre))
{
indegree[tmp]--;
if(indegree[tmp]==0)
list.add(tmp);
}
}
return numCourses==0;
}
}
208. 实现 Trie (前缀树)
class Trie {
class TrieNode{
private boolean isEnd;
TrieNode[] next;
public TrieNode() {
isEnd = false;
next= new TrieNode[26];
}
}
private TrieNode root;
public Trie()
{
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray())
{
if(node.next[c-'a']==null)
node.next[c-'a']=new TrieNode();
node=node.next[c-'a'];
}
node.isEnd = true;
}
public boolean search(String word) {
TrieNode node = root;
for(char c :word.toCharArray())
{
if(node.next[c-'a']==null)
{
return false;
}
node=node.next[c-'a'];
}
return node.isEnd;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for(char c :prefix.toCharArray())
{
if(node.next[c-'a']==null)
{
return false;
}
node=node.next[c-'a'];
}
return true;
}
}
注意 startwith和search的区别
startwith 走完prefix循环就可以返回true;
而search走完循环还要看是不是到最终的叶结点了
不然 比如word为prefix 而树中是prefixxx 也会错误的search为true
