平方数螺旋矩阵

 分享一道面试题，要求1.5小时内完成，如下：

 观测下面数字矩阵，编写一个方法实现之。

 

 输入 3， 输出内容到文件：
 1  2  3 
 8  9  4 
 7  6  5 

 输入 5， 输出内容到文件：
 01  02  03  04  05 
 16  17  18  19  06 
 15  24  25  20  07 
 14  23  22  21  08 
 13  12  11  10  09 

 输入 10， 输出内容到文件：

 001  002  003  004  005  006  007  008  009  010 
 036  037  038  039  040  041  042  043  044  011 
 035  064  065  066  067  068  069  070  045  012 
 034  063  084  085  086  087  088  071  046  013 
 033  062  083  096  097  098  089  072  047  014 
 032  061  082  095  100  099  090  073  048  015 
 031  060  081  094  093  092  091  074  049  016 
 030  059  080  079  078  077  076  075  050  017 
 029  058  057  056  055  054  053  052  051  018 
 028  027  026  025  024  023  022  021  020  019 

 输入 11， 输出内容到文件：
 001  002  003  004  005  006  007  008  009  010  011 
 040  041  042  043  044  045  046  047  048  049  012 
 039  072  073  074  075  076  077  078  079  050  013 
 038  071  096  097  098  099  100  101  080  051  014 
 037  070  095  112  113  114  115  102  081  052  015 
 036  069  094  111  120  121  116  103  082  053  016 
 035  068  093  110  119  118  117  104  083  054  017 
 034  067  092  109  108  107  106  105  084  055  018 
 033  066  091  090  089  088  087  086  085  056  019 
 032  065  064  063  062  061  060  059  058  057  020 
 031  030  029  028  027  026  025  024  023  022  021 

 

 

 

  在下当时是没能写出来，不过走出门口那刻才突然想出方法。。。所以有问题卡住时建议起身走走。

 

  在下思路：

1. 首先观察示例输出，得出其规律为对于输入数n，数字矩阵的数字个数为n^2，最大数为n^2，边长数字个数为n，矩阵数字排列为以左上角为起点，顺时针旋向内旋转至最大数。
2. 反射性地，我想到用一个二维数组去存放数字矩阵。然后用一个List<String> xyList 按螺旋顺序存放二维数组的坐标对。
3. for each 1 到 n^2 个数，取对应xyList的坐标，根据坐标把数字写入二维数组。
4. 根据二维数组write line to 文件。

 

  代码：

import java.io.*;
import java.util.*;

public class NumMatrix {

	private List<String> getRotateXY( int num )
	{
		List<String> list = new ArrayList<String>();
		
		// 走出门口想到的关键那步， 
		// 这个 level 指的是根据输入数字得出矩阵“从外到内”的数字边框层数
		// 如2 有1层，3有3层， 5有3层， 10有5层， 11有6层
		int levl = (num % 2) == 0 ? num/2: (num+1)/2;
		
		//x，y的分隔符
		String sep = ",";
		
		
		// 拿2， 3， 5和 6的矩阵为例，试着在纸上按照
		// “从外到内”的每一层， 列出所有坐标，
		// 注意每一层分四段，每一段以矩阵的四个点划分，
		// 四个点为起点，右上角，右下角，左下角，层终点，
		// 以 5 矩阵为例， 
		// 第一层四个点为：0,0  0,4  4,4  4,0  1.0
		// 第二层为               ：1,1  1,3  3,3  3,3  2,1
		// 第三层为               ：2,2  -  -  -  2,2  为最终点
		StringBuilder sb = new StringBuilder();
		for( int i=1; i<=levl; i++ )
		{
			int x = i-1;
			int y = i-1;
			int t = num-i;
			
			// 起点到右上角的所有坐标
			while( y <= t )
			{
				list.add(sb.append(x).append(sep).append(y).toString());
				sb.delete(0, sb.length());
				y++;
			}
			y = t;
			x++;
			
			// 右上角到右下角的所有坐标
			while( x <= t )
			{
				list.add(sb.append(x).append(sep).append(y).toString());
				sb.delete(0, sb.length());
				x++;
			}
			x = t;
			y--;
			
			// 右下角到左下角的所有坐标
			while( y >= (i-1) )
			{
				list.add(sb.append(x).append(sep).append(y).toString());
				sb.delete(0, sb.length());
				y--;
			}
			y = i-1;
			x--;
			
			// 左下角到层终点的所有坐标
			while( x >= i )
			{
				list.add(sb.append(x).append(sep).append(y).toString());
				sb.delete(0, sb.length());
				x--;
			}
		}
	
		return list;
	}
	
	private String[][] getMatrixArr(int num, List<String> list)
	{
		String[][] arr = new String[num][num];
		
		// 求输入数平方
		int pow = new Double(Math.pow(num, 2)).intValue();
		
		//获取最大数的字符串形式的长度， 用于前缀补“0”
		int len = Integer.toString(pow).length();
		
		StringBuilder sb = new StringBuilder();
		for( int i=1; i<=pow; i++ )
		{
			// 前缀补“0”操作
			sb.append(i);
			int iLen = sb.length();
			if( iLen < len )
			{
				sb.delete(0, sb.length());
				while( iLen < len )
				{
					sb.append("0");
					iLen++;
				}
				sb.append(i);
			}
			
			
			String[] rc = list.get(i-1).split(",");
			int r = Integer.parseInt(rc[0]);
			int c = Integer.parseInt(rc[1]);
			
			arr[r][c] = sb.toString();
			sb.delete(0, sb.length());
		}
		
		return arr;
	}
	
	//写入数据到文件
	public void printToFile(int num, String fileName)
	{
		List<String> list = this.getRotateXY(num);
		
		String [][] arr = this.getMatrixArr(num, list);
		
		FileWriter writer = null;
		try 
		{
			writer = new FileWriter(fileName);
			
			StringBuilder sb = new StringBuilder();
			for( String [] line : arr )
			{
				for( String str : line )
				{
					sb.append(str).append("   ");
				}
				
				String lb = System.getProperty("line.separator");
				writer.write(sb.toString() + lb + lb);
				
				sb.delete(0, sb.length());
			}
		} 
		catch (IOException e) 
		{
			e.printStackTrace();
		}
		finally
		{
			try 
			{
				writer.close();
			} 
			catch (IOException e) {}
		}
	}
	
	
	public static void main(String[] args) 
	{
		NumMatrix test = new NumMatrix();
		
		test.printToFile(6, "matrix.txt");
	}
	
}

 

  其实个人感觉这种方案有些复杂，应该还有别的更巧妙的方法，利用相关的图算法应该是突破口，可惜在下不会图算法。