Google – Image And

Google – Image And
两个黑白image, 用2D matrix表示，matrix的边长为2^k。 要求设计一个数据结构来表示image，尽量做到space最少。然后对两个Image做And，黑黑得黑，白白得白，黑白得白。
[Solution]
看到2^k边长的条件，考点是QuadTree肯定错不了。
Quad tree既可以省空间，也可以省时间。因为如果某一大块下面所有的cell都是黑（或者都是白），那么它就不需要任何sub tree了。做And的时候也可以直接返回，要比O(n^2) Brute force一个cell一个cell的做And快很多。

class TNode {

  public char val;

 

  public TNode leftTop;

  public TNode rightTop;

  public TNode leftBot;

  public TNode rightBot;

 

  public TNode(char val) {

    this.val = val;

  }

}

 

class Solution {

 

  public TNode buildTree(char[][] image) {

    int n = image.length;

    return buildTree(image, 0, 0, n - 1, n - 1);

  }

 

  public TNode buildTree(char[][] image, int row1, int col1, int row2, int col2) {

    if (row1 < 0 || row1 >= image.length || row2 < 0 || row2 >= image.length || col1 < 0 || col1 >= image.length || col2 < 0 || col2 >= image.length || row1 > row2 || col1 > col2) {

      return null;

    }

 

    if (row1 == row2 && col1 == col2) {

      TNode result = new TNode(image[row1][col1]);

      if (image[row1][col1] == '1') {

        result.val = '1';

      }

      else {

        result.val = '0';

      }

      return result;

    }

 

    int midX = row1 + (row2 - row1) / 2;

    int midY = col1 + (col2 - col1) / 2;

 

    TNode root = new TNode('#');

 

    TNode leftTop = buildTree(image, row1, col1, midX, midY);

    TNode rightTop = buildTree(image, row1, midY + 1, midX, col2);

    TNode leftBot = buildTree(image, midX + 1, col1, row2, midY);

    TNode rightBot = buildTree(image, midX + 1, midY + 1, row2, col2);

 

    if (leftTop.val == '1'

        && rightTop.val == '1'

        && leftBot.val == '1'

        && rightBot.val == '1') {

 

      root.val = '1';

    }

    else if (leftTop.val == '0'

        && rightTop.val == '0'

        && leftBot.val == '0'

        && rightBot.val == '0') {

 

      root.val = '0';

    }

    else {

      root.leftTop = leftTop;

      root.rightTop = rightTop;

      root.leftBot = leftBot;

      root.rightBot = rightBot;

    }

 

    return root;

  }

 

  public TNode imageAnd(TNode root1, TNode root2) {

    TNode root = new TNode('#');

    if (root1 == null && root2 == null) {

      return null;

    }

    if (root1.val == '1' && root2.val == '1') {

      return new TNode('1');

    }

    else if (root1.val == '0' || root2.val == '0') {

      return new TNode('0');

    }

    else if (root1.val == '#' && root2.val == '1') {

      root.leftTop = imageAnd(root1.leftTop, root2);

      root.rightTop = imageAnd(root1.rightTop, root2);

      root.leftBot = imageAnd(root1.leftBot, root2);

      root.rightBot = imageAnd(root1.rightBot, root2);

    }

    else if (root1.val == '1' && root2.val == '#') {

      root.leftTop = imageAnd(root1, root2.leftTop);

      root.rightTop = imageAnd(root1, root2.rightTop);

      root.leftBot = imageAnd(root1, root2.leftBot);

      root.rightBot = imageAnd(root1, root2.rightBot);

    }

    else {

      root.leftTop = imageAnd(root1.leftTop, root2.leftTop);

      root.rightTop = imageAnd(root1.rightTop, root2.rightTop);

      root.leftBot = imageAnd(root1.leftBot, root2.leftBot);

      root.rightBot = imageAnd(root1.rightBot, root2.rightBot);

    }

    return root;

  }

 

  public void toMatrix(TNode root, char[][] matrix, int row1, int col1, int row2, int col2) {

    if (root == null) {

      return;

    }

 

    if (root.val == '1' || root.val == '0') {

      for (int i = row1; i <= row2; i++) {

        for (int j = col1; j <= col2; j++) {

          matrix[i][j] = root.val;

        }

      }

    }

    else {

      int midX = row1 + (row2 - row1) / 2;

      int midY = col1 + (col2 - col1) / 2;

      toMatrix(root.leftTop, matrix, row1, col1, midX, midY);

      toMatrix(root.rightTop, matrix, row1, midY + 1, midX, col2);

      toMatrix(root.leftBot, matrix, midX + 1, col1, row2, midY);

      toMatrix(root.rightBot, matrix, midX + 1, midY + 1, row2, col2);

    }

  }

}

Read full article from Google – Image And