平方数螺旋矩阵

分享一道面试题，要求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

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

在下思路：

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

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

平方数螺旋矩阵

浏览过的版块