美文网首页Leetcode/Java学习笔记
547. Friend Circles (如何处理棋盘类型的问题

547. Friend Circles (如何处理棋盘类型的问题

作者: 萧瑟空间 | 来源:发表于2018-10-03 08:22 被阅读0次

    一个典型的棋盘问题都是带有一个矩阵的,例如:

    Input:
    [[1,1,0],
     [1,1,0],
     [0,0,1]]
    

    棋盘类型的问题最麻烦的部分是查询每个点的相邻点的时候并不复杂,但是难以简化,条件众多,导致代码可读性变差,看起来好像是硬编码似的结构不好看。其实对于棋盘类型的问题有一些比较好用的小tricks。

    Tricks 1:简化读取相邻点

    //通常我们需要使用类似于
    if([x, y+1] fits some requirements){
      #Then do something;
    }
    else if([x, y-1] fits some requirements){
      #Then do something;
    }
    //这样重复四遍,代码过长结构也难看
    
    其实我们可以这样设置:
    int[] directionX = {0,1,-1,0};
    int[] directionY = {1,0,0,-1};
    这样只需要对一个参数循环达到遍历相邻四个点的目的
    
    for(int i = 0; i < 4; i++){
      if([x+directionX[i], y+directionY[i]] fits some requirements){
        do something;
      }
    }
    

    Tricks 2: 如何将避免数组越界的代码简化

    理论上对每个点都需要检测是否越出矩阵界限。最好的检测方式是将这个步骤单独提出来做成一个helper函数
    
    private boolean inBound(int x, int y, boolean[][] grid){
      int n = grid.length;
      int m = grid[0].length;
      return x>=0 && x<n && y>=0 && y<m; 
    }
    
    这样只需要在主函数中加入
    if(!inBound(x,y,grid)){
      continue;
    }
    就可以方便越过越界的点而不去讨论;
    

    相关文章

      网友评论

        本文标题:547. Friend Circles (如何处理棋盘类型的问题

        本文链接:https://www.haomeiwen.com/subject/jvlzoftx.html