一个面试题，汗啊！

Question

给你个参数N，从下图中找出规律，让你打印出N*N的矩形阵列
1  12  11  10
2  13  16  9
3  14  15  8
4  5   6   7很遗憾，小弟算法很烂，希望哪位大虾能回答我。

Answer 1

ACM题目 不是很难 不过题目具体要求还是不太明白

Answer 2

类似迷宫问题,不算难,
先饶一圈,碰到初始位置,就退一格往其他方向走
class a
{
    int m,n;//2维坐标
    boolean flag;//判断该坐标是否写过数据了
    int O;方向(东南西北),比如往南走不过只能往东走,这个自己注意下 
}

Answer 3

这是FORTRAN语言书上的习题，我记得大学的时候做过，很简单的，楼主偷懒，呵呵。
做个数组，存储结果数据再打印

Answer 4

int O;方向(东南西北),比如往南走不过只能往东走,这个自己注意下 int O;方向(东南西北),比如往南走不过的时候只能往东走,这个自己注意下 个人觉得从外到里好写.如果从里到外,定位是不是有点麻烦?

Answer 5

public static int[][] go(int n)
{
int[][] blanks=new int[n][n];
int direct=0; //初始方向

int num=1; //要填入的数字
int posX=0,posY=0; //要填入的位置
int tempX=0,tempY=0; //下一次填入的位置的临时值
while(true)
{
blanks[posX][posY]=num; //将当前数字填入

if(num==n*n) break; //如果已经全部填入,退出循环
switch(direct) //根据方向指示,计算下一次填入的位置,保存为临时值
{
case 0:
tempY=posY+1;
break;
case 1:
tempX=posX+1;
break;
case 2:
tempY=posY-1;
break;
case 3:
tempX=posX-1;
break;
}

//如果临时位置超出数组的范围,或者该位置已经填入了值,改变方向并放弃临时值
if(tempX<0 || tempX>=n || tempY<0 || tempY>=n || blanks[tempX][tempY]!=0)
{
tempX=posX;
tempY=posY;
direct=(direct<3)?(direct+1):0;
}
else //否则,数字自增,并将下一次要填入的位置设为临时值
{
num++;
posX=tempX;
posY=tempY;
}
}

return blanks;
}public static void print(int[][] blanks,int n)
{
for(int i=0; i < n; i++ )
{
for(int j=0;j<n;j++)
{
System.out.print(blanks[j][i]+" ");
}
System.out.println();
}
}

Answer 6

public class HelixMatrix {
String[][] hmStr;
int n, h, v, step = 1, value = 0, east, south, west, north;
boolean up = false, down = true, right = false, left = false;

HelixMatrix(int n){
this.n = n;
hmStr = new String[n][n];
}

void next(){
value += step;
if(value > step * n * n){
return;
}
hmStr[v][h] = value + "";
if(down){
if(++v >= n - south){
v--;
h++;
west++;
down = false;
right = true;
}
next();
}
if(right){
if(++h >= n - east){
h--;
v--;
south++;
up = true;
right = false;
}
next();
}
if(up){
if(--v < north){
v++;
h--;
east++;
up = false;
left = true;
}
next();
}
if(left){
if(--h < west){
h++;
v++;
north++;
down = true;
left = false;
}
next();
}
}

void printResult(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.print(hmStr[i][j] + "\t");
}
System.out.println("");
}
}

public static void main(String[] args){
HelixMatrix hm = new HelixMatrix(4);
hm.next();
hm.printResult();

hm = new HelixMatrix(6);
hm.next();
hm.printResult();
}
}

Answer 7

我感觉logic_online(淡忘) 写的很明白。

Answer 8

步长任意，初值可为0：
public class HelixMatrix {
String[][] hmStr;
int n, h, v, step = 1, value = 0, east, south, west, north, times;
boolean up = false, down = true, right = false, left = false;

HelixMatrix(int n){
System.out.println("Helix matrix: " + n + " * " + n +
", step: 1, start value: 1");
this.n = n;
hmStr = new String[n][n];
}

HelixMatrix(int n, int step){
System.out.println("Helix matrix: " + n + " * " + n +
", step: " + step + ", start value: 1");
this.step = step;
this.n = n;
hmStr = new String[n][n];
}

HelixMatrix(int n, int step, int start){
System.out.println("Helix matrix: " + n + " * " + n +
", step: " + step + ", start value: " + start);
value = start - step;
this.step = step;
this.n = n;
hmStr = new String[n][n];
}

void next(){
value += step;
if(++times > n * n){
return;
}
hmStr[v][h] = value + "";
if(down){
if(++v >= n - south){
v--;
h++;
west++;
down = false;
right = true;
}
}
else if(right){
if(++h >= n - east){
h--;
v--;
south++;
up = true;
right = false;
}
}
else if(up){
if(--v < north){
v++;
h--;
east++;
up = false;
left = true;
}
}
else if(left){
if(--h < west){
h++;
v++;
north++;
down = true;
left = false;
}
}
next();
}

void printResult(){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
System.out.print(hmStr[i][j] + "\t");
}
System.out.println("");
}
}

public static void main(String[] args){
HelixMatrix hm = new HelixMatrix(4);
hm.next();
hm.printResult();

hm = new HelixMatrix(4, 2);
hm.next();
hm.printResult();

hm = new HelixMatrix(4, 2, 0);
hm.next();
hm.printResult();
}
}

Answer 9

Result：
Helix matrix: 4 * 4, step: 1, start value: 1
1 12 11 10
2 13 16 9
3 14 15 8
4 5 6 7
Helix matrix: 4 * 4, step: 2, start value: 1
2 24 22 20
4 26 32 18
6 28 30 16
8 10 12 14
Helix matrix: 4 * 4, step: 2, start value: 0
0 22 20 18
2 24 30 16
4 26 28 14
6 8 10 12

Answer 10

修正：
HelixMatrix(int n){
System.out.println("Helix matrix: " + n + " * " + n +
", step: " + step + ", start value: " + step);
this.n = n;
hmStr = new String[n][n];
}

HelixMatrix(int n, int step){
System.out.println("Helix matrix: " + n + " * " + n +
", step: " + step + ", start value: " + step);
this.step = step;
this.n = n;
hmStr = new String[n][n];
}

Answer 11

//以下程序调试通过
public class Tt{
public Tt(int m,int n){
r=new int[m+2][n+1]; //初始化数组（数组加大的目的是为了便于递归时的判断）
for (int i=0;i<r.length;i++)
for (int j=0;j<r[0].length;j++) r[i][j]=1;

for (int i=1;i<r.length-1;i++)
for (int j=0;j<r[0].length-1;j++) r[i][j]=0;
r[0][0]=0;

//调用递归添数
process(0,0,0);
}

public void process(int fx,int i,int j){
if (r[i][j]>0)
return; if (r[i+fxiang[fx][0]][j+fxiang[fx][1]]==0){
r[i][j]=count++;
i+=fxiang[fx][0];
j+=fxiang[fx][1];
process(fx,i,j);
} else {
r[i][j]=count++;
fx=(fx+1) % 4;
i+=fxiang[fx][0];
j+=fxiang[fx][1];
process(fx,i,j);
}
}

public void showResult(){
for(int i=1;i<r.length-1;i++){
for(int j=0;j<r[0].length-1;j++)
System.out.print(r[i][j]+" ");
System.out.println();
}
} public  static void  main(String args[]){
Tt tt=new Tt(4,4);
tt.showResult();
}

private final int[][] fxiang={{1,0},{0,1},{-1,0},{0,-1}};//对应下、左、上、右
private int[][] r;//保存结果
private int count=0;
}

Answer 12

//说明:
//方向问题其实不需要判断,因为走的顺序确定下,右,上,左.
//精简以后的代码:
public class Tt{
public Tt(int m,int n){
r=new int[m+2][n+1]; //初始化数组（数组加大的目的是为了便于递归时的判断）
for (int i=0;i<r.length;i++)
for (int j=0;j<r[0].length;j++) r[i][j]=1;

for (int i=1;i<r.length-1;i++)
for (int j=0;j<r[0].length-1;j++) r[i][j]=0;
r[0][0]=0;

//调用递归添数
process(0,0,0);
}

public void process(int fx,int i,int j){
if (r[i][j]>0) return; r[i][j]=count++;
if (r[i+fxiang[fx][0]][j+fxiang[fx][1]]!=0) fx=(fx+1) % 4;
i+=fxiang[fx][0];
j+=fxiang[fx][1];
process(fx,i,j);
}

public void showResult(){
for(int i=1;i<r.length-1;i++){
for(int j=0;j<r[0].length-1;j++)
System.out.print(r[i][j]+" ");
System.out.println();
}
} public  static void  main(String args[]){
Tt tt=new Tt(4,4);
tt.showResult();
}

private final int[][] fxiang={{1,0},{0,1},{-1,0},{0,-1}};//对应下、左、上、右
private int[][] r;//保存结果
private int count=0;
}

Answer 13

简单方法；=====================================================        final int N = 6;
        int[][] arr = new int[N][N];
        int num = 0;        for(int round=0; round<(N+1)/2; round++)
        {
            int x = round;
            int y = round;
            int nCount = N-2*round -1;        //  顺时针============
        //  for(int i=0; i<nCount; i++) arr[x][y++] = ++num;
        //  for(int i=0; i<nCount; i++) arr[x++][y] = ++num;
        //  for(int i=0; i<nCount; i++) arr[x][y--] = ++num;
        //  for(int i=0; i<nCount; i++) arr[x--][y] = ++num;
        //  逆时针============
            for(int i=0; i<nCount; i++) arr[x++][y] = ++num;
            for(int i=0; i<nCount; i++) arr[x][y++] = ++num;
            for(int i=0; i<nCount; i++) arr[x--][y] = ++num;
            for(int i=0; i<nCount; i++) arr[x][y--] = ++num;
            if(nCount==0) arr[x][y] = ++num;
        }

Answer 14

http://community.csdn.net/Expert/topic/3848/3848013.xml?temp=.7831385
主　　题：  螺旋数字排列  
作　　者：  yuchenln (yuchen)  
====================================================最后两回帖是我发的。那里有N*M数组的螺旋数字排列

Answer 15

回复人： fantasydog(百里怜雪) ( ) 信誉：100  2005-05-31 17:58:00  得分: 0  
 
 
   O(n)的都不错
用到双层循环的就欠点火候了===================================
此言差矣！

Answer 16

int N=5;
int[][] test=new int[N][N];
int temp=0;
for(int i=0; i<N; i++) test[i][0]=i+1;
temp=N+1;
for(int i=(N-1); i>0; i--){
for(int j=N-i; j<i+1; j++) {test[i][j]=temp; temp++;}
for(int j=i; j>N-i; j--) {test[j-1][i]=temp; temp++;}
for(int j=i; j>N-i-1; j--) {test[N-i-1][j]=temp;temp++;}
for(int j=i; j>N-i; j--) {test[N-j][N-i]=temp;temp++;}
}----------------------------
时间复杂度，空间复杂度都是O(n)，个人认为最佳了

Answer 17

N*M的时候：
-------------------------------------------- int N=8;
int M=2;
int[][] test=new int[N][M];
int temp=0;
for(int i=0; i<N; i++) test[i][0]=i+1;
temp=N+1;
for(int i=(N-1); i>(N/2-1); i--){
if((N-i)>(M/2) || i<N/2 ) break;
for(int j=N-i; j<(M-N)+i+1; j++) {
test[i][j]=temp; 
temp++;
}

if((M-N+i)<(M/2) || i-1<(N-1)/2) break;
for(int j=i; j>N-i-1; j--) {
test[j-1][M-N+i]=temp; 
temp++;
}

                   if(M/2 > (M-N+i-1) )  break;
for(int j=(M-N)+i-1; j>N-i-1; j--) {
test[N-i-1][j]=temp;
temp++;
}

if(((M+1)/2)<(N-i)) break;
for(int j=i; j>N-i; j--) {
test[N-j][N-i]=temp;
temp++;
}
}

Answer 18

//更佳的代码：
-----------------------------------------
int N=8;
int M=1;
int[][] test=new int[N+2][M+2];
int temp=1;
for(int i=0; i<java.lang.Math.min((N+1)/2, (M+1)/2); i++){
if(i>=N-i) break;
for(int j=i; j<N-i; j++) {
test[j][i]=temp; 
temp++;
}

if(i+1>=M-i) break;
for(int j=i+1; j<M-i; j++) {
test[N-i-1][j]=temp; 
temp++;
}

if(N-i-1<=i)  break;
for(int j=N-i-2; j>i-1; j--) {
test[j][M-i-1]=temp;
temp++;
}

if(M-i-1 <=i+1)  break;
for(int j=M-i-1; j>i+1; j--) {
test[i][j-1]=temp;
temp++;
}
}

Answer 19

偶的算法，希望大家批评指正，谢谢//思路是对每个环取值,比如外环:1-2-3-4-5-6-7-8-9-10-11-12,内环:13-14-15-16,
//每个环都是一个独立的个体import java.io.*;
public class MyData{
public static void main(String args[])throws IOException{
int i=0,j=0,sum=0,p=0,n,q;
//p记录环数(即初始点)，q记录循环次数
System.out.println("请输入数据n:");
DataInputStream d=new DataInputStream(System.in);
n=new Integer(d.readLine()).intValue();
q=n;
int[][] a=new int[n][n];
while(p<=(n+1)/2){

for(;i<q;i++)
a[i][j]=++sum;

for(j=j+1,i=i-1;j<q;j++)
a[i][j]=++sum;

for(i=i-1,j=j-1;i>=p;i--)
a[i][j]=++sum;

for(j=j-1,i=i+1;j>p;j--)
a[i][j]=++sum;

p++;
q=q-1;
i=p;
j=p;
}
System.out.println("输出的矩阵列是:");
for(i=0;i<n;i++){
for(j=0;j<n;j++)
System.out.print(a[i][j]+" ");
System.out.println();
}
}
}

Answer 20

凑个热闹~~~
public static void test(int n) {
    int[][] is = new int[n][n];
    int count = 1;
    int leftMin = 0;
    int rightMax = n - 1;
    int upMin = 0;
    int downMax = n - 1;
    while (true) {
        //down
        for (int i = upMin; i <= downMax; i++) {
            is[i][leftMin] = count++;
        }
        leftMin++;
        if (count >= n * n + 1) {
            break;
        }
        //right
        for (int i = leftMin; i <= rightMax; i++) {
            is[downMax][i] = count++;
        }
        downMax--;
        if (count >= n * n + 1) {
            break;
        }
        //up
        for (int i = downMax; i >= upMin; i--) {
            is[i][rightMax] = count++;
        }
        rightMax--;
        if (count >= n * n + 1) {
            break;
        }
        //left
        for (int i = rightMax; i >= leftMin; i--) {
            is[upMin][i] = count++;
        }
        upMin++;
        if (count >= n * n + 1) {
            break;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.print(is[i][j] + "\t");
        }
        System.out.println();
    }
}
    }

Answer 21

//说明:我的代码的再次说明,时间为o(m*n)
//方向问题其实不需要判断,因为走的顺序确定下,右,上,左.public class Tt{
        public Tt(int m,int n){
                r=new int[m+2][n+1];                //初始化数组（数组加大的目的是为了便于递归时的判断）
                //如果在一个方向填充数据时，遇到一个数组单元不为零则改变方向．
                for (int i=0;i<r.length;i++)
                for (int j=0;j<r[0].length;j++) r[i][j]=1;                for (int i=1;i<r.length-1;i++)
                for (int j=0;j<r[0].length-1;j++) r[i][j]=0;
                r[0][0]=0;　　　　　　　　//调用递归添数
　　　　　　　　process(0,0,0);
　　　　}　　　　public void process(int fx,int i,int j){
　　　　　　　　if (r[i][j]>0) return;//如果走到某一个不为零的单元,则退出运算.                r[i][j]=count++; //填充数据
                if (r[i+fxiang[fx][0]][j+fxiang[fx][1]]!=0)fx=(fx+1) % 4;//改变方向
                i+=fxiang[fx][0]; //坐标改变
                j+=fxiang[fx][1]; //坐标改变
                process(fx,i,j);  //下一个坐标处理
         }         public void showResult(){//数据打印
                 for(int i=1;i<r.length-1;i++){
                 for(int j=0;j<r[0].length-1;j++)
                 System.out.print(r[i][j]+" ");
                 System.out.println();
                 }
          }          public  static void  main(String args[]){
                 Tt tt=new Tt(4,4);
                 tt.showResult();
          }          private final int[][] fxiang={{1,0},{0,1},{-1,0},{0,-1}};//对应下、左、上、右.在某一个方向上,坐标改变的情况.
          private int[][] r;//保存结果
          private int count=0;
}