Tripadvisor 电面

原帖地址:一亩三分地

这几天面的,问问大家tripadvisor电面多久出结果?谢拉谢拉!
一道题,火柴棍拼图数正方形拼图图片链接:http://matchstickpuzzles.blogspot.com/2011/06/55-4×4-square-how-many-squares.html
把垂直的棍子和水平的棍子抽象成两个二位数组 boolean[][] ver boolean hor[][],然后算两个dp数组 int[][]dpV(垂直方向) int[][]dpH(水平方向),其中每个值表示截至当下点有几根连续木棍,最后对dpH逐点验证是否能以该棍为左上角第一根水平棍构成长度为1~n的正方形。
面试过程中写的代码其实有几个小bug,不过我和面试官当下都没有发现,只是探讨了下看思路正确就没有深究,我后来下了自己重新测试了下,把代码改好然后发回给了面试官。
代码如下:
public int countSquare ( boolean[][] ver , boolean[][] hor ) {
if ( ver == null || hor == null || ver.length == 0 || ver[0].length == 0 || hor.length == 0 || hor[0].length == 0 ){
return 0;
}
int[][] dpV = new int[ ver.length ][ ver[0].length ];
int[][] dpH = new int[ hor.length ][ hor[0].length ];
int res = 0;
for ( int j = 0; j < dpV[0].length; ++j) { for ( int i = 0; i < dpV.length; ++i ) { if ( ver[j] ) { dpV[j] = i == 0 ? 1 : (dpV[i - 1][j] + 1); } else { dpV[j] = 0; } } } for ( int i = 0; i < dpH.length; ++i) { for ( int j = 0; j < dpH[0].length; ++j ) { if ( hor[j] ) { dpH[j] = j == 0 ? 1 : (dpH[j - 1] + 1); } else { dpH[j] = 0; } } } for ( int i = 0; i < dpH.length; ++i ) { for ( int j = 0; j < dpH[0].length; ++j ) { for ( int l = 1; l <= Math.min(dpH[0].length - j , dpV.length - i ) ; ++l){ if ( dpH[ l + j - 1 ] >= l dpH[i + l][ l + j – 1 ] >= l dpV[i + l – 1][j ] >= l dpV[ i + l – 1 ][ l + j ] >= l ) {
++res;
}
if ( !(dpH[ l + j – 1 ] >= l) ) {
break;
}
}
}
}
return res;
}

若图形为n*n 则该算法时间复杂度O(n*n*n)
总体比我想象的略难。这题虽然思路不是太难想到,但因为两个二位矩阵的input长宽一个是n*(n+1)一个是(n+1)*n所以稍微有点tricky
面过的大神记得说一下电面多久出结果哈!