[interview]螺旋队列问题

摘要

本文主要讲解三种螺旋队列的实现方式和打印输出：

• 从中心往外端顺时针旋转，记为『外螺旋队列』
• 从左顶点开始,绕剩下的最大圈顺时针往内旋转，记为『内螺旋队列』
• 从左顶点开始,之字形旋转(只能同行同列地移动)，记为『 』螺旋队列』
• 从左顶点开始,之字形旋转(只能沿-45°斜线移动),记为 『/ 螺旋队列 』

前三个螺旋队列图示如下：

1. 外螺旋队列

通过几个标记位，来确定其他值的大小，

由这两个值再来确定其他值，首先，我们可以确定这个值的大致范围： maxAbs=max{ fabs(r),fabs(c)},这样这个值就在 (2maxAbs-1)~(2maxAbs+1)的范围。接下来，我们从东南西北四个方向分析具体的值：

令$N=maxAbs$, 标志位上平方数元素的表示为：

\begin{gather}
f(-k,k) = (2k+1)^2 , \qquad k=0,1,2...\\
f(k,-(k-1)) = (2k)^2, \qquad k=1,2...
\end{gather}

• 北:$f(r,c)=f(-N,N)-(N-c), \qquad r=-N,r<c$
• 东:$f(r,c)=f(-(N-1),(N-1))+(r+(N-1))+1, \qquad c=N,r>-c$
• 南:$f(r,c)=f(N,-(N-1))-(c+(N-1)), \qquad r=N,r>c$
• 西:$f(r,c)=f(N,-(N-1))+(N-r)+1, \qquad c=-N,r<-c$

int rotQueue1(int r,int c)

{

	if(r>0 && r+c==1)

		return (2*r)*(2*r);

	if(r<=0 && r+c==0)

		return (2*c+1)*(2*c+1);

	int N=fabs(r)>fabs(c)?fabs(r):fabs(c);

	if( r==-N && r<c)

		return rotQueue1(-N,N)-(N-c);

	else if( c==N && r>-c)

		return rotQueue1(-(N-1),(N-1))+(r+(N-1))+1;

	else if( r==N && r>c )

		return rotQueue1(N,-(N-1))-(c+(N-1));

	else if( c==-N && r<-c)

		return rotQueue1(N,-(N-1))+(N-r)+1;

}

2. 内螺旋队列

可以通过迭代建立数组，外圈循环从 i←0 to n/2,表示从外到内，循环圈子慢慢缩小，内圈循环从按照北东南西的顺序递增地建立数组。

int **rotQueue2(int r,int c)

{

	int **a=malloc2D(r,c);

	int m=1;

	for(int i=0; i<r/2; i++)

	{

		for(int j=i;j<c-1-i;j++)

			a[i][j] = m++;

		for(int j=i;j<r-1-i;j++)

			a[j][c-1-i] = m++;

		for(int j=c-1-i;j>i;j--)

			a[r-1-i][j] = m++;

		for(int j=r-1-i;j>i;j--)

			a[j][i] = m++;

	}

	if(r%2==1&&c%2==1)

		a[r/2][c/2]=m;

	return a;

}

3. 』螺旋队列

有两个方法确定数组：

1. 可用标志位——平方数的加减得到，行列标从1开始的话， a(2k,1)=(2k) , a(1,2k-1)=(2k-1) 类似于rotQueue1
2. 类似于内螺旋队列，整体迭代赋值建立数组，下面用第二种。

int **rotQueue3(int N)

{

	int **a=malloc2D(N,N);

	int m=1;

	a[0][0]=m++;

	for(int i=1;i<N; ++i ){

		if(i%2==1){

			for(int j=0;j<=i;++j)// j为行

				a[j][i]=m++;

			for(int j=i-1;j>=0;--j)// j为列

				a[i][j]=m++;

		}

		else{

			for(int j=0;j<=i;++j)// j为列

				a[i][j]=m++;

			for(int j=i-1;j>=0;--j)// j为行

				a[j][i]=m++;

		}

	}

	return a;

}

4. / 螺旋队列 （zigzag数组）

可以将这个数组看成一个上三角形和一个倒三角形的组合。分成两部分赋值即可。（分析略去）。

5. 输出

最后，给出动态分配二维数组和打印程序，主程序与最后的结果。

int** malloc2D(int r,int c)

{

	int **pt2D =(int**) malloc( r*sizeof(int*) );

	for(int i=0; i< r;i++){

		pt2D[i] = (int*)malloc( c*sizeof(int) );

		for(int j=0;j<c;j++)

			pt2D[i][j]=0;

	}

	return pt2D;

}

void printRotQueue(int**a,int r,int c)

{

	for(int i=0; i<r;i++){

		for(int j=0;j<c;j++){

			printf("%3d ",a[i][j]);

		}

		printf("\n");

	}

}

int main()

{

	int r=5,c=5;

	printf("rotQueue1(%d,%d):\n",r,r);

	for(int i= -r/2; i<=r/2 ; ++i ){

		for(int j= -r/2;j<=r/2;++j){

			printf("%3d ",rotQueue1(i,j) );

		}

		printf("\n");

	}

	int** a2=rotQueue2(r,c);

	printf("\nrotQueue2(%d,%d):\n",r,c);

	printRotQueue(a2,r,c);

	printf("\nrotQueue3(%d,%d):\n",r,r);

	int** a3=rotQueue3(r);

	printRotQueue(a3,r,r);

	return 0;

}