一道google面试题 ---- Z字型穿梭矩阵_求职面试_非技术区_程序员俱乐部

今天听一友人说了一道在google的面试题,题目是这样的：有一个M*N的矩阵，要求你以“Z”字型遍历矩阵。

例如,如果输入为 5 * 10的矩阵：?

[00, 02, 03, 09, 10, 19, 20, 29, 30, 39]
[01, 04, 08, 11, 18, 21, 28, 31, 38, 40]
[05, 07, 12, 17, 22, 27, 32, 37, 41, 46]
[06, 13, 16, 23, 26, 33, 36, 42, 45, 47]
[14, 15, 24, 25, 34, 35, 43, 44, 48, 49]

?

则输出为:?00 , 01 , 02 .... 48, 49。

?

再如，如果输入为 10 * 8 的矩阵：

?

[00, 02, 03, 09, 10, 20, 21, 35]
[01, 04, 08, 11, 19, 22, 34, 36]
[05, 07, 12, 18, 23, 33, 37, 51]
[06, 13, 17, 24, 32, 38, 50, 52]
[14, 16, 25, 31, 39, 49, 53, 64]
[15, 26, 30, 40, 48, 54, 63, 65]
[27, 29, 41, 47, 55, 62, 66, 73]
[28, 42, 46, 56, 61, 67, 72, 74]
[43, 45, 57, 60, 68, 71, 75, 78]
[44, 58, 59, 69, 70, 76, 77, 79]

?

则输出为：00, 01, 02, ... , 77, 78, 79。

?

觉得不是很难，友人也这样觉得，但却在这一轮被淘汰了，不知道是什么地方欠考虑呢，还是google的面试官比较挑剔：P 现将算法贴在下面，请大侠指教。这里稍稍做了一点变化：

?

1）为了省去输入矩阵数据的麻烦，直接就将遍历矩阵改成了输出遍历顺序，也就是说：

?? 输入为矩阵的维度M，N 比如5*10，输出则为如下形式的矩阵：

[00, 02, 03, 09, 10, 19, 20, 29, 30, 39]
[01, 04, 08, 11, 18, 21, 28, 31, 38, 40]
[05, 07, 12, 17, 22, 27, 32, 37, 41, 46]
[06, 13, 16, 23, 26, 33, 36, 42, 45, 47]
[14, 15, 24, 25, 34, 35, 43, 44, 48, 49]

?

我想这和原来的问题是等价的。

?

2）其实为了输出美观，做了一些处理，比如像上面这个例子，由于最大的是两位数，所以一位数前都加了0保证矩阵输出的美观性。

?

/*
 * Tranverse a matrix in a "Z" shape.
 */
import java.util.Arrays;

public class TranverseMatrix {

	public static int M = 5;
	public static int N = 10;
                //用于计算输出的矩阵中元素的位数，用于格式化数据，使得输出矩阵中的所有数字位数都相同
           public static int bits = 1;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[][] matrix = new String[M][N];
		
                                //初始化bits
		initBits();
		
		
		int x = 0;
		int y = -1;
		int deltax = 0;
		int deltay = 0;
                                //x代表横坐标也就是列，y代表纵坐标也就是行
		for (int k = 0; k < M * N; k++) {
			x += deltax;
			y += deltay;
                                               //当遍历超出下边界的情况
			if (y >= M )
			{
				deltax = 1;
				deltay = -1;
				x += 2;
				y = M -1;
			}
                                                //当遍历超出右边界的情况
			else if ( x >= N)
			{
				deltax = -1;
				deltay = 1;
				x = N -1;
				y += 2;
			}
                                                //当遍历超出左边界的情况
			else if (x < 0) {
				deltax = 1;
				deltay = -1;
				x = 0;

			}
                                                //当遍历超出上边界的情况
			else if (y < 0) {
				deltax = -1;
				deltay = 1;
				y = 0;
			}
			
		                //在相应位置赋值代表遍历顺序，赋值前先格式化一下数据
			matrix[y][x] = getStringValue(k);
		}
        for (int index = 0 ; index < matrix.length ; index ++ )
		System.out.println(Arrays.toString(matrix[index]));

	}
	public static void initBits()
	{
		 
		int temp = M * N -1 ;
		
		while (temp >= 10)
		{
			bits *= 10;
			temp /= 10;
		}
		
	}
	
	public static String getStringValue ( int k )
	{
		StringBuffer result = new StringBuffer("");
		int temp = bits;
		while ( k < temp && temp > 1)
		{
			result.append('0');
			temp /= 10;
		
		}
		result.append(k);
		
		return result.toString();
	}
	

}

???