Rah*_*yas 56 language-agnostic arrays algorithm math
如何以螺旋顺序打印5×5二维数组？
是否有任何公式,以便我可以按螺旋顺序打印任何大小的数组？
cod*_*ict 78
我们的想法是将矩阵视为一系列图层,右上图层和左下图层.为了以螺旋方式打印基质,我们可以从这些基质上剥离层,打印去皮部分并递归调用左侧部分的打印件.当我们没有任何要打印的图层时,递归终止.
输入矩阵:
1 2 3 4
5 6 7 8
9 0 1 2
3 4 5 6
7 8 9 1
剥离右上层后:
1 2 3 4
8
5 6 7 2
9 0 1 6
3 4 5 1
7 8 9
从子矩阵剥离左下图层后:
6 7
5 0 1
9 4 5
3
7 8 9
从子矩阵剥离右上层后:
6 7
1
0 5
4
从子矩阵剥离左下图层后:
0
4
递归终止.
C函数:
// function to print the top-right peel of the matrix and
// recursively call the print bottom-left on the submatrix.
void printTopRight(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print values in the row.
for(i = x1; i<=x2; i++) {
printf("%d ", a[y1][i]);
}
// print values in the column.
for(j = y1 + 1; j <= y2; j++) {
printf("%d ", a[j][x2]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the bottom left of the sub matrix.
printBottomLeft(a, x1, y1 + 1, x2-1, y2);
}
}
// function to print the bottom-left peel of the matrix and
// recursively call the print top-right on the submatrix.
void printBottomLeft(int a[][COL], int x1, int y1, int x2, int y2) {
int i = 0, j = 0;
// print the values in the row in reverse order.
for(i = x2; i>=x1; i--) {
printf("%d ", a[y2][i]);
}
// print the values in the col in reverse order.
for(j = y2 - 1; j >= y1; j--) {
printf("%d ", a[j][x1]);
}
// see if more layers need to be printed.
if(x2-x1 > 0) {
// if yes recursively call the function to
// print the top right of the sub matrix.
printTopRight(a, x1+1, y1, x2, y2-1);
}
}
void printSpiral(int arr[][COL]) {
printTopRight(arr,0,0,COL-1,ROW-1);
printf("\n");
}
小智 32
Python代码:
import itertools
arr = [[1,2,3,4],
[12,13,14,5],
[11,16,15,6],
[10,9,8,7]]
def transpose_and_yield_top(arr):
while arr:
yield arr[0]
arr = list(reversed(zip(*arr[1:])))
print list(itertools.chain(*transpose_and_yield_top(arr)))
jus*_*alf 25
我看到没有人只for loop使用一个而且没有递归代码,所以我想贡献.
这个想法是这样的:
想象一下,有一只乌龟站在点(0,0),即左上角,朝东(右)
它将继续前进,每次看到一个标志,乌龟将向右转
因此,如果我们把乌龟放在面向右边的点(0,0),如果我们将标志放在适当的位置,乌龟将以螺旋方式穿过阵列.
现在的问题是:"在哪里放置标志？"
让我们看看我们应该在哪里放置标志(用#标记,数字用O标记):
For a grid that looks like this: O O O O O O O O O O O O O O O O We put the signs like this: O O O # # O # O O # # O # O O # For a grid that looks like this: O O O O O O O O O O O O We put the signs like this: O O # # # O O # O # O # And for a grid that looks like this: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O We put the signs like this: O O O O O O # # O O O O # O O # O O # O O O # O O O # O # O O O O O #
我们可以看到,除非该点位于左上角部分,否则符号位于距离最近的水平边界和最近的垂直边界的距离相同的点处,而对于左上角的部分,距离是顶部边框比左边框的距离多一个,如果点是水平居中,则优先考虑右上角,如果点垂直居中,则优先考虑左上角.
这可以通过一个简单的函数很容易地实现,取最小的(curRow和height-1-curRow),然后是(curCol和width-1-curCol)的最小值,并比较它们是否相同.但我们需要考虑左上角的情况,即最小值curRow和curCol自己的情况.在那种情况下,我们相应地减少垂直距离.
这是C代码:
#include <stdio.h>
int shouldTurn(int row, int col, int height, int width){
int same = 1;
if(row > height-1-row) row = height-1-row, same = 0; // Give precedence to top-left over bottom-left
if(col >= width-1-col) col = width-1-col, same = 0; // Give precedence to top-right over top-left
row -= same; // When the row and col doesn't change, this will reduce row by 1
if(row==col) return 1;
return 0;
}
int directions[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
void printSpiral(int arr[4][4], int height, int width){
int directionIdx=0, i=0;
int curRow=0, curCol=0;
for(i=0; i<height*width; i++){
printf("%d ",arr[curRow][curCol]);
if(shouldTurn(curRow, curCol, height, width)){
directionIdx = (directionIdx+1)%4;
}
curRow += directions[directionIdx][0];
curCol += directions[directionIdx][1];
}
printf("\n");
}
int main(){
int arr[4][4]= {{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
printSpiral(arr, 4, 4);
printSpiral(arr, 3, 4);
}
哪个输出:
1 2 3 4 8 12 16 15 14 13 9 5 6 7 11 10 1 2 3 4 8 12 11 10 9 5 6 7
以下是三种有趣的方式
以螺旋方式阅读可以被视为一条蛇向边界移动并且打开边界或自身(我发现它优雅且最有效的是N次迭代的单个循环)
ar = [
[ 0, 1, 2, 3, 4],
[15, 16, 17, 18, 5],
[14, 23, 24, 19, 6],
[13, 22, 21, 20, 7],
[12, 11, 10, 9, 8]]
def print_spiral(ar):
"""
assuming a rect array
"""
rows, cols = len(ar), len(ar[0])
r, c = 0, -1 # start here
nextturn = stepsx = cols # move so many steps
stepsy = rows-1
inc_c, inc_r = 1, 0 # at each step move this much
turns = 0 # how many times our snake had turned
for i in range(rows*cols):
c += inc_c
r += inc_r
print ar[r][c],
if i == nextturn-1:
turns += 1
# at each turn reduce how many steps we go next
if turns%2==0:
nextturn += stepsx
stepsy -= 1
else:
nextturn += stepsy
stepsx -= 1
# change directions
inc_c, inc_r = -inc_r, inc_c
print_spiral(ar)
输出:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
递归方法是打印外层并为内部矩形调用相同的函数,例如
def print_spiral(ar, sr=0, sc=0, er=None, ec=None):
er = er or len(ar)-1
ec = ec or len(ar[0])-1
if sr > er or sc > ec:
print
return
# print the outer layer
top, bottom, left, right = [], [], [], []
for c in range(sc,ec+1):
top.append(ar[sr][c])
if sr != er:
bottom.append(ar[er][ec-(c-sc)])
for r in range(sr+1,er):
right.append(ar[r][ec])
if ec != sc:
left.append(ar[er-(r-sr)][sc])
print " ".join([str(a) for a in top + right + bottom + left]),
# peel next layer of onion
print_spiral(ar, sr+1, sc+1, er-1, ec-1)
Finally here is a small snippet to do it, not efficient but fun :), basically it prints top row, and rotates whole rectangle anti-clockwise and repeats
def print_spiral(ar):
if not ar: return
print " ".join(str(a) for a in ar[0]),
ar = zip(*[ reversed(row) for row in ar[1:]])
print_spiral(ar)
小智 6
该程序适用于任何n*n矩阵..
public class circ {
public void get_circ_arr (int n,int [][] a)
{
int z=n;
{
for (int i=0;i<n;i++)
{
for (int l=z-1-i;l>=i;l--)
{
int k=i;
System.out.printf("%d",a[k][l]);
}
for (int j=i+1;j<=z-1-i;j++)
{
int k=i;
{
System.out.printf("%d",a[j][k]);
}
}
for (int j=i+1;j<=z-i-1;j++)
{
int k=z-1-i;
{
System.out.printf("%d",a[k][j]);
}
}
for (int j=z-2-i;j>=i+1;j--)
{
int k=z-i-1;
{
System.out.printf("%d",a[j][k]);
}
}
}
}
}
}
希望能帮助到你
当我学习Ruby时,我对这个问题很着迷.这是我能做的最好的事情:
def spiral(matrix)
matrix.empty? ? [] : matrix.shift + spiral(matrix.transpose.reverse)
end
您可以通过回顾这个要点中的修订来查看我的其他一些解决方案.此外,如果你按照我分享要点的链接回来,你会找到一些其他聪明的解决方案.真正有趣的问题,可以通过多种优雅方式解决 - 特别是在Ruby中.