V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzzzzggggggg
V2EX  ›  程序员

[第 6 期] 面试 BAT 前应该知道的二维数组

  •  1
     
  •   zzzzzzggggggg · 2020-03-25 10:53:30 +08:00 · 1119 次点击
    这是一个创建于 831 天前的主题,其中的信息可能已经有所发展或是发生改变。

    也许你看过很多面经里都讲到面试会问一些奇奇怪怪的算法题,说实话,手撕红黑树做不出来不丢人,很难的动态规划没思路也没关系,但是二维数组相关的题目还是希望你了解一下。

    不同于一些奇怪的算法题让你面试造核弹,二维数组算法题目很能考察到逻辑能力、程序边界问题,而且有相当一部分二维数组可以使用递归来解决,可以说是程序员居家之必备题。

    考察数组下标规律和边界

    此类问题,重点是从数组的下标中发现规律,写代码的时候要注意程序的边界问题,常见于 Z 字形打印二维数组、蛇形打印二维数组、杨辉三角等等问题。

    杨辉三角

    LeetCode.118 ,难度简单

    题目

    给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。 示例:

    输入: 5
    输出:

    [ [1],
    [1,1],
    [1,2,1],
    [1,3,3,1],
    [1,4,6,4,1] ]

    思路

    观察给出的例子,可以发现规律,比如对于 arr1=[1,2,1]和 arr2=[1,3,3,1]来说:

    可以看出规律来:

    1. arr2[0] = 1
    2. arr2[1] = arr1[0] + arr1[1]
    3. arr2[2] = arr1[1] + arr1[2]
    4. arr[3] = 1

    反过来思路就是:

    • 遍历 arr1,index=0 时,arr2.push(1)
    • 如果 index=arr1.length-1,arr2.push(1)
    • 否则,arr2.push(arr1[index] + arr1[index+1])

    代码

    /**
     * @param {number} numRows
     * @return {number[][]}
     */
    var generate = function(n) {
      if(n === 0)
        return [];
      if(n === 1)
        return [ [1] ];
      
      let res = [[1]];
      
      for(let i = 1;i < n;i++) {
        let lastArr = res[i-1];
        let newArr = [];
        for(let j = 0;j < lastArr.length;j++) {
          if(j === 0)
              newArr.push(1);
          if(j === lastArr.length-1)
            newArr.push(1);
          else {
            newArr.push(lastArr[j]+lastArr[j+1]);
          }
        }
        
        res.push(newArr);
      }
      return res;
    };
    

    对角线遍历二维数组

    LeetCode.498 ,难度中等

    题目

    给定一个含有 M x N 个元素的矩阵( M 行,N 列),请以对角线遍历的顺序返回这个矩阵中的所有元素,对角线遍历如下图所示。 示例:

    输入: [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ]
    ]

    输出: [1,2,4,7,5,3,6,8,9]

    思路

    观察一个例子,对于下面这个二维数组来说,对角线遍历的顺序如下:

    1. (0,0)
    2. (0,1), (1,0)
    3. (2,0), (1,1), (0,2)
    4. (0,3), (1,2), (2,1)
    5. (2,2), (1,3)
    6. (2,3)

    [
    A, B, C, D,
    E, F, G, H,
    I, J, K, L
    ]

    可以看出来一些规律:

    • 按打印一次对角线来算,一共要打印 6 次,也就是行数+列数-1 次
    • 按最开始那一次算第 count=0 次的话,如果 count 小于行数,那 x=count 且 y=count-x,否则 x=行数-1 且 y=count-x,对于列数来说也是一样的道理

    代码

    /**
     * @param {number[][]} matrix
     * @return {number[]}
     */
    var findDiagonalOrder = function(matrix) {
        if(matrix === null || matrix.length === 0 || matrix[0].length === 0)
            return [];
        
        let rows = matrix.length;
        let cols = matrix[0].length;
        let count = 0;
        let res = [];
        
        while(count < rows+cols-1) {
            let r1 = count < rows ? count : rows-1;
            let c1 = count - r1;
            while(r1 >= 0 && c1 < cols) {
                res.push(matrix[r1][c1]);
                r1--;
                c1++;
            }
            
            count++;
            if(count >= rows+cols-1)
                break;
            
            let c2 = count < cols ? count : cols-1;
            let r2 = count - c2;
            while(c2 >= 0 && r2 < rows) {
                res.push(matrix[r2][c2]);
                r2++;
                c2--;
            }
            count++
        }
        
        return res;
    };
    

    螺旋矩阵

    LeetCode.54 ,难度中等

    题目

    给定一个包含 m x n 个元素的矩阵( m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

    示例 1:

    输入: [
    [ 1, 2, 3 ],
    [ 4, 5, 6 ],
    [ 7, 8, 9 ] ]
    输出: [1,2,3,6,9,8,7,4,5]

    示例 2:

    输入: [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9,10,11,12] ]
    输出: [1,2,3,4,8,12,11,10,9,5,6,7]

    思路

    从题目给出的例子可以看出,螺旋遍历矩阵其实就是按照顺时针一层一层的遍历。注意好边界的划分,以及特殊情况比如一行和一列的处理。

    代码

    /**
     * @param {number[][]} matrix
     * @return {number[]}
     */
    var traverseLayer = function(m, startRow, endRow, startCol, endCol, res) {
        if(startRow === endRow) {
        // 一列的情况
            for(let i = startCol;i <= endCol;i++) {
                res.push(m[startRow][i]);
            }
        } else if(startCol === endCol) {
            for(let i = startRow;i <= endRow;i++) {
                res.push(m[i][startCol]);
            }
        } else {
            let curR = startRow;
            let curC = startCol;
            
            while(curC < endCol) {
                res.push(m[curR][curC]);
                curC++;
            }
            while(curR < endRow) {
                res.push(m[curR][curC]);
                curR++;
            }
            while(curC > startCol) {
                res.push(m[curR][curC]);
                curC--;
            }
            while(curR > startRow) {
                res.push(m[curR][curC]);
                curR--;
            }
        }
    }
    
    var spiralOrder = function(matrix) {
        if(matrix === void 0 || matrix.length === 0 || matrix[0].length === 0)
            return [];
        
        let res = [];
        let startRow = 0;
        let endRow = matrix.length-1;
        let startCol = 0;
        let endCol = matrix[0].length-1;
        
        
        while(startRow <= endRow && startCol <= endCol) {
            traverseLayer(matrix, startRow, endRow, startCol, endCol, res);
            startRow++;
            endRow--;
            startCol++;
            endCol--;
        }
        
        return res;
    };
    

    考察递归思路

    对于此类问题,最重要的是要注意到不是简单地找数组下标的规律就能解决的,要把问题抽象成递归的思路,递归入口、递归调用、递归结束条件,这三点缺一不可。

    朋友圈

    LeetCode.547 ,难度中等

    题目

    班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

    给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果 M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

    示例 1:

    输入:
    [[1,1,0],
    [1,1,0],
    [0,0,1]]

    输出: 2
    说明:已知学生 0 和学生 1 互为朋友,他们在一个朋友圈。 第 2 个学生自己在一个朋友圈。所以返回 2 。

    示例 2:

    输入:
    [[1,1,0],
    [1,1,1],
    [0,1,1]]

    输出: 1
    说明:已知学生 0 和学生 1 互为朋友,学生 1 和学生 2 互为朋友,所以学生 0 和学生 2 也是朋友,所以他们三个在一个朋友圈,返回 1 。

    注意: N 在[1,200]的范围内。 对于所有学生,有 M[i][i] = 1 。 如果有 M[i][j] = 1,则有 M[j][i] = 1 。

    思路

    看一下这道题的示例,可以看出来如果 arr[0,1]=1,0 和 1 是朋友,那接下来就要去检查 1 和其他的人是否是朋友,再依次检查下去,说到这里就可以考虑深度优先的搜索方法了。

    代码

    /**
     * @param {number[][]} M
     * @return {number}
     */
    var findCircleNum = function(M) {
        // 深度优先
        let visited = [];
        for(let i = 0;i < M.length;i++) {
            visited.push(false);    
        }
        
        let res = 0;
        for(let i = 0;i < visited.length;i++) {
            if(visited[i]) 
                continue;
            traverse(M, i, visited);
            res++;
        }
        
        return res;
    };
    
    function traverse(M, cur, visited) {
        visited[cur] = true;
        for(let i = 0;i < M.length;i++) {
            if(visited[i] || !M[cur][i])
                continue;
            traverse(M, i, visited);
        }
    }
    

    岛屿的最大面积

    LeetCode.695 ,难度中等

    题目

    给定一个包含了一些 0 和 1 的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。

    找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为 0 。)

    示例 1:

    [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]]

    对于上面这个给定矩阵应返回 6 。
    注意答案不应该是 11,因为岛屿只能包含水平或垂直的四个方向的‘1’。

    示例 2:

    [[0,0,0,0,0,0,0,0]]

    对于上面这个给定的矩阵, 返回 0 。
    注意: 给定的矩阵 grid 的长度和宽度都不超过 50 。

    思路

    对于[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]这样的矩阵来说,从最左上角的 1 出发,分别再考察它的四周(上下左右)是否为 1,它的上下左右再考察自己的四周是否为 1,遇到是 1 则可以加 1,遇到是 0 则不处理即可,说到这里基本就可以确定可以使用递归了,即有一个自己调用自己的过程;这里面有个细节,处理过的 1 需要置为 0,否则会有重复计算的问题。

    代码如下:

    /**
     * @param {number[][]} grid
     * @return {number}
     */
    var maxAreaOfIsland = function(grid) {
        if(grid === null || grid.length === 0)
            return 0;
        
        let res = 0;
        for(let i = 0;i < grid.length;i++) {
            for(let j = 0;j < grid[0].length;j++) {
                if(grid[i][j] === 1)
                    res = Math.max(res, help(grid, i, j));
            }
        }
        
        return res;
    };
    
    var help = function(grid, i, j) {
        grid[i][j] = 0;
        
        let sum = 1;
        if(i > 0 && grid[i-1][j] === 1)
            sum += help(grid, i-1, j);
        if(i < grid.length-1 && grid[i+1][j] === 1) 
            sum += help(grid, i+1, j);
        if(j > 0 && grid[i][j-1] === 1)
            sum += help(grid, i, j-1);
        if(j < grid[0].length-1 && grid[i][j+1] === 1)
            sum += help(grid, i, j+1);
        
        return sum;
    }
    

    欢迎关注微信公众号——前端亚古兽( fe-yagushou )

    1 条回复    2020-03-25 14:55:00 +08:00
    huahuacui
        1
    huahuacui  
       2020-03-25 14:55:00 +08:00
    可以转发博客嘛哈哈哈
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1367 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 23:32 · PVG 07:32 · LAX 16:32 · JFK 19:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.