LeetCode130 被围绕的区域

来源:8-7 floodfill算法,一类经典问题 Number of Islands-

不考过程序员不改名字

2022-03-29

老师,您能帮忙看下问题出在哪嘛,总感觉我的递归终止条件和for循环内的判断逻辑理不清楚,您能给个思路或者建议嘛?

public class LeetCode130 {
    boolean[][] flag;
    int[][] go = {{-1,0},{0,1},{1,0},{0,-1}};
    int m,n;
    public void solve(char[][] board) {
        m = board.length;
        if (m<1){
            return;
        }
        n = board[0].length;
        flag = new boolean[m][n];
        for (int i = 1; i < m-1; i++) {
            for (int j = 1;j<n-1;j++){
                if (!flag[i][j]&&board[i][j]=='O'){
                    bfs(board,i,j,true);
                }
            }
        }
    }
    private boolean bfs(char[][] board,int startX,int startY,boolean flag1){
        //如果不是O返回false
        if (board[startX][startX]!='O'){
            return false;
        }
        //如果是O但是处于边界
        if (board[startX][startY]=='O'&&!judgeBoard(startX,startY)){
            flag1=false;
            return false;
        }
        flag[startX][startY]=true;
        board[startX][startY]='X';
        for (int i = 0;i<4;i++){
            int newX = startX+go[i][0];
            int newY = startY+go[i][1];
            if (inArea(newX,newY)&&judgeBoard(newX,newY)){
                boolean a = bfs(board,newX,newY,flag1);
                if (!flag1){
                    board[startX][startY]='O';
                    return false;
                }
            }
        }
        return true;
    }
    //判断是否为边界元素
    private boolean judgeBoard(int x,int y){
        if (x==m-1||x==0){
            return false;
        }else return y != n - 1 && y != 0;
    }
    //判断是否在边界内
    private boolean inArea(int x,int y){
        if ((x>=0&&x<m)&&(y>=0&&y<n)){
            return true;
        }else {
            return false;
        }
    }
}
写回答

1回答

liuyubobobo

2022-03-29

我没有看完你的代码。因为看到一半就懵了。因为语义不清晰。


请回答以下问题:

1)bfs 函数(实际上你使用的是 dfs) 的返回值是什么意思?

2)bfs 函数参数中的 flag1 表示什么意思?

3)什么叫 judgeBoard?这个名字看似把这个函数要做什么写出来了,但其实没有用。请问到底是传进去的点在边界上返回 true?还是不在边界上返回 true?如果这个函数是在判断一个点是在边界上,是不是叫 inBorder 更清晰?(或者 notInBorder)

4)猛地看你的逻辑,flag1 初始传进去 true,似乎永远是 true,不会改变,唯一变化 flag1 的地方在一个 if 中,之后马上 return 了,所以这个改变也没有影响任何逻辑。但 anyway,关键还是,你的 flag1 到底是什么意思。(另外一点就是整个函数的返回值似乎在逻辑中也没有用。)


你必须用自然语言能够讲清楚你的函数的每一个变量的语义是什么,我才能看到你的逻辑是不是围绕这些语义展开的,才能验证你的逻辑是否正确,你自己也能检查这一点。这是我给看了你的这版代码,给你的唯一的建议。这个建议本身,也是写程序(不仅仅是算法)需要遵循的首要原则。


继续加油!:)

0
1
不考过程序员不改名字
老师,按照您说的我梳理了下逻辑重新写了一遍,第25个用例没通过,您能帮忙看下整体逻辑有什么问题嘛 ,回复里贴不了代码我重新再发一个
2022-03-29
共1条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程