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
