一道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();
	}
	

}

   

评论

6 楼 leonzhx 2010-10-21  

我就纳闷了，我如何删除我发过的回答啊？
脑子有点混乱。但是代码的思路告诉你了，如果你有什么更好的建议的话，请告诉我。
你原始的代码有以下问题：
1、不知道你的功能是否实现了。
2、就算实现功能了，但是需要提高你的代码的性能。
性能不高的原因我主要认为如下：
1、 for (int k = 0; k < M * N; k++)
你写这个for循环的目的是干什么？难道就是为了在相应位置赋值代表遍历顺序，赋值前先格式化一下数据，既然你已经找到了你想要的数据为什么不直接输出。而又另写一个for循环专门输出呢？


其次要让你的代码简洁一点。能用一行代码实现的功能，就不要用3行代码去写。

quda 写道

我就纳闷了，我如何删除我发过的回答啊？
脑子有点混乱。但是代码的思路告诉你了，如果你有什么更好的建议的话，请告诉我。
你原始的代码有以下问题：
1、不知道你的功能是否实现了。
2、就算实现功能了，但是需要提高你的代码的性能。
性能不高的原因我主要认为如下：
1、 for (int k = 0; k < M * N; k++)
你写这个for循环的目的是干什么？难道就是为了在相应位置赋值代表遍历顺序，赋值前先格式化一下数据，既然你已经找到了你想要的数据为什么不直接输出。而又另写一个for循环专门输出呢？


其次要让你的代码简洁一点。能用一行代码实现的功能，就不要用3行代码去写。

good questions，我的回答如下：

1. 是实现了。你可以拿我的程序跑跑， 试试看改变M和N的输出结果就知道了。
2. 这样做的原因很简单，就是为了验证结果。比如，如果我要验证 5 * 10的矩阵和 10 *8 的矩阵，我必须输入这两个矩阵的数据，然后再比对程序的输出看看是不是正确，那如果我再想验证一下10*10的矩阵，是不是还要这样呢？
   但现在，我只要修改M和N的值就能一眼看出我算法的正确性，而且输出很直观，你说是吧？
3. 首先，我不是很同意你所谓的一行代码比三行代码好的论点，因为我觉得可读性和逻辑清晰很重要，如果只是为了简洁的而使程序不可读并不是好事。其次，能不能请你指出，除了你所说的第二点外，还有哪里能再简洁点的呢？

谢谢指教

5 楼 leonzhx 2010-10-21  

quda 写道

我晕，刚才发的代码有错误，真不好意思。刚才没有仔细的检查。这是我想发的代码。

package test;

import java.util.Arrays;

import com.sun.java_cup.internal.internal_error;

public class TranverseMatrix {

public static int M = 5;
public static int N = 10;

/**基本思路是把这个矩阵的维度5*10，分成多个维度2*2的矩阵，并把这个2*2的矩阵输出
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub 
String[][] matrix = new String[M][N];
int x = 0;//x坐标
int y = 0;//Y坐标
int n=2;//相当于指针吧，就是每次输出的数量

for (; x< x+n&&x<N; x=x+n) {
if (M%2!=0&&x>=N&&(x-=1)==(N-1)) {//如果矩阵的X不是偶数的话,判断是不是到最后一行，如果是最后一行则把最后一行输出
System.out.println(matrix[x][N-1]);
break;
}
for(;y<y+n&&y<M;y=y+n){
if (N%2!=0&&x>=N&&(y-=1)==(N-1)) {//如果矩阵的Y不是偶数的话,判断是不是到最后一行，如果是最后一行则把最后一行输出
System.out.println(matrix[M][y]);
break;
}
System.out.println(matrix[x][y]);
}
}
}

}

晕,我想你还是误解我的意思了,看来我的表述能力很有问题啊
这样说吧,我说的这个Z字是斜着走的(其实你把我的程序跑一下,换不同的N和M就明白了)
给出两个输入输出的例子:

(1) 输入:

[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

(2) 输入:
[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

这样应该清楚了吧?

4 楼 leonzhx 2010-10-21  

是只是给你一个思路。

quda 写道

我的代码里可能有bug，但是只是给你一个思路。

我看明白了，你的Z字是横着走的其实是“N”字...但问题是这样好像就不叫“遍”历了吧？您这样理解的话就不可能输出每一个矩阵元素啊？

不过我再看看我自己原来写的文章，确实说得太含糊了，没把题目表述清楚。现在改了下应该好多了吧？

3 楼 leonzhx 2010-10-21  

我的代码里可能有bug，但是只是给你一

quda 写道

我的代码里可能有bug，但是只是给你一个思路。

不好意思,你的程序是不是在关键的地方有些笔误? 我真的不太理解您程序的意图,以下是我对您的程序的理解:


//列从 0 --> N-1 遍历
for (; y < N; y++) {

//如果是最后一列或者第一列的话,则从上到下直接打出该列
if (y==0||y==N-1) {

for (; x< M; x++) {
System.out.println(matrix[x][y]);
}
}else {
//如果不是第一列或最后一列的话则打印该列中的某个元素,不知道这里什么意思
System.out.println(matrix[x-y][y]);
}
}

我想您大概理解错了这道题的意思了,我给出的5*10的矩阵的例子中,数字的大小就表示了遍历的顺序。另外我对我的原文加了些注释。

希望您能讲一下您的思路，谢谢

2 楼 leonzhx 2010-10-20  

quda 写道

1、首先要实现具体的功能
2、要考虑代码的性能，以及代码的可读性。你写那么多的if else语句。总共写了60多行，其实可用简单的几行代码（不超过30行代码）就可以实现功能。

首先非常感谢您的留言 其次,我想说我的代码确实比较散,但真正实现这道程序的逻辑的就是 25-56 这几行。 总共四个 if else,分别对应遍历时超出上下左右四个边界的情况，个人觉得这样写可能逻辑更清楚一点。 当然，相信高手可以将逻辑写得更简洁一些 请您不吝赐教

1 楼 kimmking 2010-10-20  

封装几个对象，
Matrix -> array[][]，Visitor -> walk()，Orient -> 1,2,3,4