LeetCode 水域大小

<>1.题目

<>2.思路

经典的DFS+回溯法套路模板,这题比较麻烦的是需要遍历 8 个方向
Java语言题解
class Solution { List<Integer> array = new ArrayList<Integer>(); int rowLen;
int colLen; public int[] pondSizes(int[][] land) { rowLen = land.length; colLen
= land[0].length; for(int i = 0;i<rowLen;i++){ for(int j = 0;j<colLen;j++){ if(
land[i][j] == 0){ array.add(dfs(land,i,j)); land[i][j] = 0; } } } Collections.
sort(array); int size = array.size(); int[] result = new int[size]; for(int i =
0;i<size;i++){ result[i] = array.get(i).intValue(); } return result; } public
int dfs(int[][] land,int i,int j){ if(!checkBoard(land,i,j)){ return 0; } int
count= 1; land[i][j] = -1; count+=dfs(land,i-1,j-1); // 左上角 count+=dfs(land,i-1,
j); //正上方 count+=dfs(land,i-1,j+1); //右上角 count+=dfs(land,i,j+1); //右一个 count+=
dfs(land,i+1,j+1); //右下角 count+=dfs(land,i+1,j); //正下方 count+=dfs(land,i+1,j-1);
//左下角 count+=dfs(land,i,j-1); //左一个 return count; } public boolean checkBoard(
int[][] land,int i,int j){ if(i>=rowLen || i<0) return false; if(j>=colLen || j<
0) return false; return land[i][j] == 0; } }
<>3.总结

不要忘记回溯,DFS过程中做的标记需要记得还原,否则会栈溢出

• « 上一篇：英伟达官方道歉：机器人买空了RTX 3080
• » 下一篇：特征工程