布伦博格（蓬勃）新鲜详细面经（2组7.5轮QAQ）

wey 发表于 2018-5-14 20:04
嗯，我这样理解对不对哈：
就是给一个mn的矩阵，每个点是0的话没有船，有船就是1，找里面的1一共多少个 ...

差不多的，不过稍微复杂一点。输入是两个点，左下和右上，需要你求这两个点组成的长方形的内有几条船。会告诉你有个API类似hasShip（），输入也是两个点，左下和右上，告诉你这两个点组成的长方形内是不是有船（返回true or false），使用这个API，写出来计算船个数的算法。

找工作啊找工作 发表于 2018-5-15 10:08
差不多的，不过稍微复杂一点。输入是两个点，左下和右上，需要你求这两个点组成的长方形的内有几条船。会 ...

谢谢！

wey 发表于 2018-5-14 20:59
谢谢！

不客气！面试加油哈！

找工作啊找工作 发表于 2018-5-9 12:56
在矩阵里找一条路径，路径上都是0，且一个端点在矩阵的边界上。就是从边界上为0的点作为起始点开始DFS ， ...

请问LZ， 这个很明显是DFS， 但是试着写了下，不知道在什么时候应该把搜索到的路径加到最终结果里。终止条件

能否给个代码看看啊 多谢了

感谢楼主详细的面筋。祝福。一点没有觉得话痨，非常身临其境。谢谢

希望楼主拿到大offer。

感谢分享！祝好运！

xingwuzheng 发表于 2018-5-17 00:23
感谢楼主详细的面筋。祝福。一点没有觉得话痨，非常身临其境。谢谢

希望楼主拿到大offer。

蟹蟹~我已经拿到啦~希望你也能一切顺利~

谢谢楼主的分享 非常详细

houqingniao 发表于 2018-5-17 00:18
请问LZ， 这个很明显是DFS， 但是试着写了下，不知道在什么时候应该把搜索到的路径加到最终结果里。终止 ...

抱歉啊，我已经有点忘记当时怎么做的了。但是DFS进行下去的条件就是你有next step：上下左右至少有一个方向的值是0，如果没有，就代表已经将深搜进行到底了，把当前的path放进去，就可以return了。

找工作啊找工作 发表于 2018-5-18 11:51
抱歉啊，我已经有点忘记当时怎么做的了。但是DFS进行下去的条件就是你有next step：上下左右至少有一个方 ...

LZ 帮忙看看在哪里加到result里啊。。。
public List<List<int[]>> findZeroPath(int[][] matrix) {
        List<List<int[]>> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                helper(matrix, i, 0, res, new ArrayList<int[]>());
            }
            if (matrix[i][matrix[0].length - 1] == 0) {
                helper(matrix, i, matrix[0].length - 1, res, new ArrayList<int[]>());
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0)
                helper(matrix, 0, i, res, new ArrayList<int[]>());
            if (matrix[matrix.length - 1][i] == 0)
                helper(matrix, matrix.length - 1, i, res, new ArrayList<int[]>());
        }
        return res;
    }

    public void helper(int[][] matrix, int i, int j, List<List<int[]>> res, List<int[]> path) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length || matrix[i][j] != 0) {
            return;
        }
        path.add(new int[]{i, j});
        matrix[i][j] = -1;

        helper(matrix, i + 1, j, res, path);
        helper(matrix, i - 1, j, res, path);
        helper(matrix, i, j + 1, res, path);
        helper(matrix, i, j - 1, res, path);
        
        path.remove(path.size() - 1);
    }