一道google面试题 ---- Z字型穿梭矩阵

leonzhx

浏览: 798621 次
性别:
来自: 上海

最近访客更多访客>>

u012363178

justsimple

cdphantom

wang_xuewu

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2014-05 ( 22)
2014-04 ( 47)
2014-03 ( 25)
更多存档...

博客分类：

算法

Google 面试算法 J#JavaScript

今天听一友人说了一道在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，输出则为如下形式的矩阵：

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

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

}

8
顶

0
踩

分享到：

Immutable Java Objects | Simple Solution for Complex Java Web App ...

2010-10-19 21:22
浏览 6547
评论(26)
分类:编程语言
查看更多

26 楼魅影骑士 2010-11-03

使用C#简单实现Z字型遍历数组，请大家指教
using System;
using System.Collections.Generic;
using System.Text;

namespace z字型穿梭
{
    class Program
    {
        static void Main(string[] args)
        {
            string[,] zjz =
            {
                {"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","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","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"}
            };

            int x = zjz.GetLength(0)-1;
            int y = zjz.GetLength(1)-1;

            int i = 0, j = 0, k = 0;//i，j为数组下标变量，k为遍历方向变量
            for (; i <=x & j <= y; )
            {
                Console.Write(zjz[i, j]+" ");
                if (i == 0 || j==y)//判断边界为上边界和右边界
                {
                    k = 1;//改变变量k
                    if (j == 0)//判断是否为第一点，是，则为左边界，改变量k=-1
                    {
                        i = i + k;
                        k = -1;
                    }
                    else if (j == y)
                        i = i + k;
                    else
                        j = j + k;
                    Console.Write("\n" + zjz[i, j]+" ");
                }
                else if (i == x || j == 0)//判断边界为左边界和右边界，改变量k=1
                {
                    k = -1;
                    if (i == x)
                        j = j - k;
                    else if (i != x)
                        i = i - k;
                    Console.Write("\n" + zjz[i, j]+" ");
                }
                //根据方向变量k值改变数组下标i、j值
                i = i + k >= 0 ? i + k : 0;
                j = j - k >= 0 ? j - k : 0;
            }
            Console.Read();
        }
    }
}

25 楼 yangguo 2010-11-01

我觉得你的算法虽然比较PO，但效率在这里应该是最高的，也比较清晰。
只是一些辅助函数却写得比较破。

initBits(){
 return String.valueOf(size).length();
}

getStringValue ( int k )  {
  NumberFormat nf = NumberFormat.getInstance();
    nf.setMinimumIntegerDigits(bits);
    nf.setGroupingUsed(false);
    System.out.println(nf.format(k));
  

}

24 楼 smzd 2010-10-29

看我的http://smzd.iteye.com/blog/796224

23 楼 zxflb 2010-10-28

学习受教了 kuchaguangjie 的思路俺最喜欢

22 楼 beck1986 2010-10-28

一共41行代码
用了1小时左右

21 楼 beck1986 2010-10-28

package com.huaweisymantec.invs.sort;

public class TestZ
{
    private static int M = 5;
    private static int N = 10;

    public static void main(String[] args)
    {
        String[][] matrix = new String[M][N];
        for (int i = 0; i < M; i++)
        {
            for (int j = 0; j < N; j++)
            {
                matrix[i][j] = (Math.random() + "").split("\\.")[1].substring(0,
                        3);
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
        for (int k = 0; k < M + N - 1; k++)
        {
            if (k % 2 != 0)
            {
                for (int m = (k < N ? 0 : k - N + 1); m <= (k >= M ? M - 1 : k); m++)
                {
                    System.out.print(matrix[m][k - m] + " ");
                }
            }
            else
            {
                for (int m = (k >= M ? M - 1 : k); m >= (k < N ? 0 : k - N + 1); m--)
                {
                    System.out.print(matrix[m][k - m] + " ");
                }
            }
            System.out.println("");
        }
    }
}

20 楼 hackpro 2010-10-25

leonzhx 写道

hackpro 写道

搞了一个下午终于弄出来了，不过只能应用于　M小于N的情况

，耐力可嘉，你的输出样式挺逗的

其实就是按斜线输出的

19 楼 leonzhx 2010-10-25

hackpro 写道

搞了一个下午终于弄出来了，不过只能应用于　M小于N的情况

，耐力可嘉，你的输出样式挺逗的

18 楼 hackpro 2010-10-25

搞了一个下午终于弄出来了，不过只能应用于　M小于N的情况

下面是运行结果：
please define M < N ..
init date..
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63,64,65,66,67,68,69,
70,71,72,73,74,75,76,77,78,79,
80,81,82,83,84,85,86,87,88,89,
according to Z output..
10;
11;20;
30;21;12;
13;22;31;40;
50;41;32;23;14;
15;24;33;42;51;60;
70;61;52;43;34;25;16;
17;26;35;44;53;62;71;80;
81;72;63;54;45;36;27;18;
19;28;37;46;55;64;73;82;
83;74;65;56;47;38;29;
39;48;57;66;75;84;
85;76;67;58;49;
59;68;77;86;
87;78;69;
79;88;
89;

17 楼 hackpro 2010-10-25

/*
 * 
 *  @(#)GoogleTest.java	Created on Oct 25, 2010
 *
 * Copyright 2004-2005 . author:hackpro
 * 
 * Description 
 * 
 * CopyrightVersion 
 *
 */
package com.huawei.iread.ieach;

public class GoogleTest
{
    /*  
     * Tranverse a matrix in a "Z" shape. 
     *  
     */

    public static int M = 8;
    
    public static int N = 10;
    
    public static String[][] matrix = new String[M][N];
    /**  
     * @param args  
     */
    public static void main(String[] args)
    {
        if (M > N)
        {
            System.out.println("please define M < N ..");
            return;
        }
        System.out.println("init date..");
        initArray();
        System.out.println(" according to Z output.. ");
        for (int i = 0; i < N + M; i++)
        {
            reduce(i);
        }
    }
    
    public static void initArray()
    {
        int x = 0;
        for (int i = 0; i < M; i++)
        { //为以好看，都用两位数的
            for (int j = 0; j < N; j++)
            {
                matrix[i][j] = x + 10 + "";
                System.out.print(x + 10 + ",");
                x++;
            }
            System.out.println("");
        }
    }
    public static void reduce(int end)
    {
        int i = 0;
        int x = 0;
        do
        {
            x = end - i;
            if (x < 0)
            {
                x = 0;
            }
            if (x > N)
            {
                x = N;
            }
            if (end % 2 == 1)
            {
                if (i >= M || x >= N)
                {
                    
                }
                else
                {
                    System.out.print(matrix[i][x] + ";");
                }
            }
            else
            {
                if (x >= M || i >= N)
                {
                    
                }
                else
                {
                    System.out.print(matrix[x][i] + ";");
                }
            }
            
            i++;
        } while (i <= end);
        System.out.println();
        
    }
}

16 楼 leonzhx 2010-10-24

/**
 * z read array
 * @date 2010-10-23 15:30
 * @author kuchaguangjie
 * @blog http://kuchaguangjie.iteye.com
 */
var arr_one = [ 
 [ 0,  2,  3,  9, 10, 19, 20, 29, 30, 39],
 [ 1,  4,  8, 11, 18, 21, 28, 31, 38, 40],
 [ 5,  7, 12, 17, 22, 27, 32, 37, 41, 46],
 [ 6, 13, 16, 23, 26, 33, 36, 42, 45, 47],
 [14, 15, 24, 25, 34, 35, 43, 44, 48, 49 ] 
];
var arr_two= [
  	[ 0,  2,  3,  9, 10, 20, 21, 35],
  	[ 1,  4,  8, 11, 19, 22, 34, 36],
  	[ 5,  7, 12, 18, 23, 33, 37, 51],
  	[ 6, 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]
  ];
function zRead(arr) {
	// 行数
	var rowCount = arr.length;
	// 列数
	var colCount = arr[0].length;
	// 是否 row 长
	var isRow = rowCount > colCount;
	// 斜切次数
	var cut = rowCount + colCount - 1;
	// rowLength & colLength 中的最小值
	var smaller = isRow ? colCount : rowCount;
	// 结果
	var result = [];
	// 上 或 右 点
	var topOrRightPoint;
	// 左 或 下 点
	var leftOrBottomPoint;
	for ( var i = 0; i < cut; i++) {
		// 斜线超出 row 的长度
		var rowExtraCount = (i + 1) > rowCount ? (i + 1 - rowCount) : 0;
		// 斜线超出 col 的长度
		var colExtraCount = (i + 1) > colCount ? (i + 1 - colCount) : 0;
		// 斜线长度
		var len = (i + 1) - rowExtraCount - colExtraCount;
		topOrRightPoint = new Point(colExtraCount, i - colExtraCount);
		leftOrBottomPoint = new Point(i - rowExtraCount, rowExtraCount);
		if (i % 2 == 0) { // 由 top 向 leftOrBottom 读数据
			while (len-- > 0) {
				result[result.length] = arr[leftOrBottomPoint.rowIndex - len][leftOrBottomPoint.colIndex + len];
			}
		} else { // 由 left 向 topOrRight 读数据
			while (len-- > 0) {
				result[result.length] = arr[topOrRightPoint.rowIndex + len][topOrRightPoint.colIndex - len];
			}
		}
	}
	return result;
}
/**
 * 行列中的 1个点的位置
 * 
 * @param rowIndex
 *            行 index
 * @param colIndex
 *            列 index
 * @return
 */
function Point(rowIndex, colIndex) {
	this.rowIndex = rowIndex;
	this.colIndex = colIndex;
}

* html 测试文件

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/z_read.js"></script>
<script type="text/javascript">
function showResult(arr){
	document.getElementById('resultDiv').innerHTML=zRead(arr);
}
</script>
</head>
<body>
<input type="button" value="z_read 1" onclick="showResult(arr_one);" />
<input type="button" value="z_read 2" onclick="showResult(arr_two);" />
<div id="resultDiv" style="width: 300px;border:1px solid green;overflow: scroll;">
</div>
</body>
</html>

慢慢理解,呵呵~~

15 楼 leonzhx 2010-10-24

kuchaguangjie 写道

这道题目考的是你对矩阵的看法，矩阵中斜切线和 m n 的关系，至于怎么实现并不是重点，考的重点是线性代数，

我写了个通用的实现，使用 javascript 实现的，
在：
http://kuchaguangjie.iteye.com/blog/792175

领教了

,原来这个叫左斜切线,这个是线代的内容还是高代的？我忘记了已经：P
不知道左斜切线有些什么应用没？

14 楼 kuchaguangjie 2010-10-23

通过计算矩阵的斜切线，来实现：

* js

/**
 * z read array
 * @date 2010-10-23 15:30
 * @author kuchaguangjie
 * @blog http://kuchaguangjie.iteye.com
 */
var arr_one = [ 
 [ 0,  2,  3,  9, 10, 19, 20, 29, 30, 39],
 [ 1,  4,  8, 11, 18, 21, 28, 31, 38, 40],
 [ 5,  7, 12, 17, 22, 27, 32, 37, 41, 46],
 [ 6, 13, 16, 23, 26, 33, 36, 42, 45, 47],
 [14, 15, 24, 25, 34, 35, 43, 44, 48, 49 ] 
];
var arr_two= [
  	[ 0,  2,  3,  9, 10, 20, 21, 35],
  	[ 1,  4,  8, 11, 19, 22, 34, 36],
  	[ 5,  7, 12, 18, 23, 33, 37, 51],
  	[ 6, 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]
  ];
function zRead(arr) {
	// 行数
	var rowCount = arr.length;
	// 列数
	var colCount = arr[0].length;
	// 是否 row 长
	var isRow = rowCount > colCount;
	// 斜切次数
	var cut = rowCount + colCount - 1;
	// rowLength & colLength 中的最小值
	var smaller = isRow ? colCount : rowCount;
	// 结果
	var result = [];
	// 上 或 右 点
	var topOrRightPoint;
	// 左 或 下 点
	var leftOrBottomPoint;
	for ( var i = 0; i < cut; i++) {
		// 斜线超出 row 的长度
		var rowExtraCount = (i + 1) > rowCount ? (i + 1 - rowCount) : 0;
		// 斜线超出 col 的长度
		var colExtraCount = (i + 1) > colCount ? (i + 1 - colCount) : 0;
		// 斜线长度
		var len = (i + 1) - rowExtraCount - colExtraCount;
		topOrRightPoint = new Point(colExtraCount, i - colExtraCount);
		leftOrBottomPoint = new Point(i - rowExtraCount, rowExtraCount);
		if (i % 2 == 0) { // 由 top 向 leftOrBottom 读数据
			while (len-- > 0) {
				result[result.length] = arr[leftOrBottomPoint.rowIndex - len][leftOrBottomPoint.colIndex + len];
			}
		} else { // 由 left 向 topOrRight 读数据
			while (len-- > 0) {
				result[result.length] = arr[topOrRightPoint.rowIndex + len][topOrRightPoint.colIndex - len];
			}
		}
	}
	return result;
}
/**
 * 行列中的 1个点的位置
 * 
 * @param rowIndex
 *            行 index
 * @param colIndex
 *            列 index
 * @return
 */
function Point(rowIndex, colIndex) {
	this.rowIndex = rowIndex;
	this.colIndex = colIndex;
}

* html 测试文件

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/z_read.js"></script>
<script type="text/javascript">
function showResult(arr){
	document.getElementById('resultDiv').innerHTML=zRead(arr);
}
</script>
</head>
<body>
<input type="button" value="z_read 1" onclick="showResult(arr_one);" />
<input type="button" value="z_read 2" onclick="showResult(arr_two);" />
<div id="resultDiv" style="width: 300px;border:1px solid green;overflow: scroll;">
</div>
</body>
</html>

13 楼 kuchaguangjie 2010-10-23

12 楼 leonzhx 2010-10-22

非常同意lzyzizi的说法

我也觉得这四个if else可以优化一下

11 楼 leonzhx 2010-10-22

个循环每次比较K的时候都要去求M*N的

lzyzizi 写道

对了有个稍微明显点的代码不足是

 for (int k = 0; k < M * N; k++) {

这个循环每次比较K的时候都要去求M*N的结果，乘法的开销稍微有点大，M*N的结果先算好放着可能比较好。

有道理

这个确实可以改进的

不知道编译器对这种情况会不会去优化噢？

10 楼 lzyzizi 2010-10-22

对了有个稍微明显点的代码不足是

 for (int k = 0; k < M * N; k++) {

这个循环每次比较K的时候都要去求M*N的结果，乘法的开销稍微有点大，M*N的结果先算好放着可能比较好。

9 楼 lzyzizi 2010-10-22

quda 写道

leonzhx 写道

再有,我在这里所举的输入输出的例子就是我程序生成的。我这样写也很方便我举例子啊

for (int k = 0; k < M * N; k++) ，你这个代码无论怎样都要循环M*N次吧？还有谁能清楚你这个for循环是干什么的
你考虑一下如何减少你循环的次数。
对于2纬数组，你为什么只考虑一个for循环？你的M*N次循环是必须的吗？你这个代码是实现了功能，但是并不是最优化的结果，你算一下你的矩阵100*100遍历一次总共用多长时间。

为什么不考虑嵌套一个循环
行，我一定把我的完整代码给你写出来。并让它运行。我用两个嵌套循环的运算速度，我敢保证我的运行速度一定比你目前的代码运行速度快。

这个题考你的是"Z"字型遍历矩阵，他考你是一个算法。虽然你的算法功能实现了，但是这个代码不是最优的算法。你去查看一下算法方面的书。一个好的算法需要哪几个条件。

要打印这个这个举证，至少也得遍历这个矩阵的每个元素吧。

看来我是孤陋寡闻了，我比较好奇不【遍历】这个矩阵就能打印出这个矩阵的方法。

还有我期待你的完整代码。

PS：我没运行过楼主程序，就从楼主的程序来看，循环的次数是M*N，就从复杂度来讲已经最优了，唯一不足的可能就是要比较稍微多了点，或许有更巧妙的方法避免那么多的IF语句，

8 楼 leonzhx 2010-10-22

quda 写道

leonzhx 写道

再有,我在这里所举的输入输出的例子就是我程序生成的。我这样写也很方便我举例子啊

quda兄，不要激动，我没有任何要challenge你的意思，只是希望你能指出我不足的地方，从而自己有个提高。

首先M*N的矩阵有 M*N个元素，我循环M*N次也没什么奇怪呀？复杂度是 O(M*N)，你写两层循环不见得就复杂度低了吧？这和循环层数有什么任何关系么？

其次，如果你不清楚这个for循环是干什么的话，请不要武断地说别人都不清楚

没个人的思维能力是不同的。

再其次，我从来不觉得我写的code会是性能最优的，我想只有无知的人才会觉得自己写的程序是性能最优的。我之所以写这篇文章就是希望高手告诉我，我的问题在哪里，我好改进和学习。

最后，也真的很想请您赐教一下，好的算法需要哪几个条件？以及您认为的这个题的最优算法是怎样的

但我还是要强调一点，在一个大的项目里，程序的逻辑清晰与可读性是很重要的，并不是所有的标准都向性能看齐的，谢谢

7 楼 leonzhx 2010-10-21

再有,我在这里所举的输入输出的例子就是我程序生成的。我这样写也很方便我举例子啊

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论