使用递归以螺旋模式遍历二维数组

Question

我正在准备面试，并且已经被这个问题困扰了很长一段时间。有人可以帮我解决代码吗？如果不完整的话可能是其中的一个片段？ 请..

Answer 1

Python 2，从左上角到中心按顺时针方向打印 2D 嵌套列表：

>>> def clockwise(r):
...     return list(r[0]) + clockwise(list(reversed(zip(*r[1:])))) if r else []
... 
>>> a = [ 
...   [ 1,  2,  3], 
...   [ 5,  6,  7], 
...   [ 9, 10, 11]]
>>> clockwise(a)
[1, 2, 3, 7, 11, 10, 9, 5, 6]
>>> a = [ 
...   [ 1,  2,  3,  4], 
...   [ 5,  6,  7,  8], 
...   [ 9, 10, 11, 12],
...   [13, 14, 15, 16]]
>>> clockwise(a)
[1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10]

那么这里会发生什么？ 顺时针的参数是一个二维数组r。我们想要从左到右顺时针打印其内容。因此，如果二维数组不为空，那么我们可以打印它的第一个元素，即顶行。接下来，我们要打印剩余行的最后一个元素（右侧的数字）。我们不想重复自己。所以我们要做的就是转换剩余的行，以便下一个要打印的数字位于顶行。我们通过调换剩余的行（使它们成为列）然后反转它们来做到这一点。

如果我用 Haskell 编写，也许算法会变得更清晰：

import Data.List

clockwise :: [[a]] -> [a] 
clockwise (x:xs) = x ++ (clockwise $ reverse $ transpose $ xs) 
clockwise _      = []

Answer 2

下面的代码本质上是将数组划分为层。因此，所有外部元素，即第一行、最后一列、最后一行和第一列，将构成第一层。第二层将由紧邻第一层内部的所有元素组成，依此类推。

在尝试了几种行数和列数组合后，我得出结论，层数由行数的一半或列数的一半给出，以较小者为准（小数点向上舍入）。

在每一层上调用 shell() 可以有效地允许您以螺旋顺序遍历和数组。

import java.util.Scanner;

//program to input elements in spiral order 
public class spiral{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("enter number of rows");
        int m = sc.nextInt();
        System.out.println("enter number of columns");
        int n = sc.nextInt();
        int arr[][] = new int[m][n];
        /*
         * recursive approach is used here
         * shell() takes input for only the outer layer of the array
         * mid stores the number of layers, which is half of the number of rows or
         * columns whichever is lesser
         * calling shell() for each layer of the array effectively returns an array in
         * spiral order
         */

        int mid = arr.length > arr[0].length ? (int) Math.ceil(arr[0].length / 2) : (int) Math.ceil(arr.length / 2);

        for (int i = 0; i < mid; i++) {
            shell(arr, i, arr[0].length - i - 1, i, arr.length - i - 1);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                System.out.print(arr[i][j] + " ");
            }
            System.out.println();
        }
        sc.close();
    }

    // iterate through first row, last column, last row and first column in order
    public static void shell(int arr[][], int col_start, int col_end, int row_start, int row_end) {
        //Here I am taking input for the array. Whatever is inside each of 
        //these loops can be manipulated. 
        for (int i = col_start; i < col_end; i++) {
            arr[row_start][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_start; i < row_end; i++) {
            arr[i][col_end] = new Scanner(System.in).nextInt();
        }
        for (int i = col_end; i > col_start; i--) {
            arr[row_end][i] = new Scanner(System.in).nextInt();
        }
        for (int i = row_end; i > row_start; i--) {
            arr[i][col_start] = new Scanner(System.in).nextInt();
        }

    }
}