我该如何改变这个矩阵螺旋遍历的方向和起始点？

Question

我有一些代码（参考这个例子）来遍历一个矩阵，从左上角开始顺时针方向。我想基于此创建三种新方法:

• 一个从左上角开始逆时针方向
• 一个从中间开始顺时针方向
• 一个从中间开始逆时针方向

为了使每个方法都能够正常工作，我需要做哪些更改？我尝试过反转计数器增量，并更改起始/结束行/列，但没有成功。

public static void traverseSpiral(int[][] matrix) {

    if(matrix.length == 0|| matrix[0].length == 0) {
        return;
    }

    StringBuffer stringBuffer = new StringBuffer();
    int counter = matrix.length * matrix[0].length;
    int startRow = 0;
    int endRow = matrix.length-1;
    int startCol = 0;
    int endCol = matrix[0].length-1;
    boolean moveCol = true;
    boolean leftToRight = true;
    boolean upDown = true;

    while(counter>0) {
        if(moveCol) {
            if(leftToRight) {

            /* printing entire row left to right */
                for(int i = startCol; i <= endCol ; i++){
                    stringBuffer.append(matrix[startRow][i]);
                    counter--;
                }
                leftToRight = false;
                moveCol = false;
                startRow++;
            }
            else{

            /* printing entire row right to left */
                for(int i = endCol ; i >= startCol ; i--){
                    stringBuffer.append(matrix[endRow][i]);
                    counter--;
                }
                leftToRight = true;
                moveCol = false;
                endRow--;
            }
        }
        else
        {
            if(upDown){

            /* printing column up down */
                for(int i = startRow ; i <= endRow ; i++){
                    stringBuffer.append(matrix[i][endCol]);
                    counter--;
                }
                upDown = false;
                moveCol = true;
                endCol--;
            }
            else
            {

            /* printing entire col down up */
                for(int i = endRow ; i >= startRow ; i--){
                    stringBuffer.append(matrix[i][startCol]);
                    counter--;
                }
                upDown = true;
                moveCol = true;
                startCol++;
            }
        }
    }
    System.out.println(stringBuffer.toString());
}

- Chelsea Kelly-Reif

---

似乎有人在要求解决一份作业... - rlegendi

放心，这不是机器翻译。我在寻找SE实习面试问题时看到了螺旋遍历的主题，所以我想尝试一下。 - Chelsea Kelly-Reif

这里的任何答案对您有帮助吗？如果是的话，请考虑将此问题标记为已回答。 - Taylor Hx

Answer 1

你的代码问题在于你把所有内容都堆在了一个方法中，这使得你的代码非常难以阅读和修改（而不会破坏任何东西）。

既然这是一个“面试问题”，你应该努力寻找不仅是解决方案，而且是最优雅的解决方案。或者是最快的解决方案。或者最短的解决方案。最终，每个程序员在编写代码时都有不同的优先事项。但是大多数（如果不是所有）程序员都努力编写“好的代码”。

“好的代码”易于阅读、编写和维护。虽然没有确切的定义可以说明什么是好的代码，但 Kristopher Johnson 发布了 this answer，我认为它很好地涵盖了基本要素。

考虑将你的代码分解成各自负责的单独方法。我立即可以看到四个应该成为自己方法的代码块（从左到右打印，从右到左打印，从上到下打印和从下到上打印）。这将使你的代码更加清晰。

例如，在递归解决方案中，我至少会有5种方法：

// A method that will handle the traversal of the spiral.
public static String clockwise(int[][] matrix);

// Responsible for printing a column from bottom to top.
public static String up(int[][] matrix, int first, int last);

// Responsible for printing a column from top to bottom.
public static String down(int[][] matrix, int first, int last);

// Responsible for printing a column from right to left.
public static String left(int[][] matrix, int first, int last);

// Responsible for printing a column from left to right.
public static String right(int[][] matrix, int first, int last);

使用这样的方法，实现逆时针遍历相同螺旋的方法将会非常简单，只需要编写另一个方法并重用up(matrix, first, last)、down(matrix, first, last)、left(matrix, first, last)和right(matrix, first, last)中的代码即可。

Clockwise          = right, down, left, up;
Counter-Clockwise  = down, right, up, left;

个人而言，我更喜欢使用分治递归方法。由于绕着一个大小为3x3的网格螺旋前进本质上与绕着一个2x2的网格螺旋前进并多转一圈相同，你可以使用递归方法找到和解决问题的最小版本，并逐步构建出解决方案。

我强烈建议你独立地研究递归和分治方法。如果你只对螺旋遍历问题的解决方案感兴趣，包括顺时针、逆时针、顺时针向外和逆时针向外，请参阅Github Gist这里。

注意：上面的代码是按原样提供的，没有任何形式的保证。所以请注意。

- Taylor Hx

Answer 2

需要实现三种方法：

1. 从左上角开始逆时针旋转

2. 从中间开始顺时针旋转

3. 从中间开始逆时针旋转

让我们先来讨论第一种方法（您已经实现了它）

我们来看一个3x3的矩阵

+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+  
|   |   |   |
+---+---+---+

所以根据您的实现，应该是这样的：

SR=0, ER=2, SC=0, EC=2

(SR: startRow, ER: endRow, SC: startCol, EC: endCol)

SC->EC 
SR++   (=>SR=1)
SR->ER 
EC--   (=>EC=1)
EC->SC 
ER--   (=>ER=1)
ER->SR
SC++   (=>SC=1)
SC->EC
-> finish with (SR=1,ER=1,SC=1,EC=1)

让我们把它反转，这样它就变成第三个。

SR=1, ER=1, SC=1, EC=1
EC->SC
SC--
SR->ER
ER++
SC->EC
EC++
ER->SR
SR--
EC->SC
-> finish with (SR=0,ER=2,SC=0,EC=2)

所以重点不仅是改变SR、ER、SC、EC的值，而且还要改变修改其值的位置。 而且所有的东西都是相反的，所以从左到右打印startCol变成了打印endCol。其他方向也是一样的。

因此，

if(leftToRight) {

/* printing entire row left to right */
    for(int i = startCol; i <= endCol ; i++){
        stringBuffer.append(matrix[startRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    startRow++;
} 

变成

if (leftToRight) {

    /* printing entire row left to right */
    for (int i = startCol; i <= endCol; i++) {
        stringBuffer.append(matrix[endRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    endCol++;
} 

如果矩阵的行数和列数均为奇数，则您可以选择由（moveCol，leftRight，upDown）定义的任何起始方向。但是，如果矩阵的行数或列数为偶数，则起始方向非常重要。

+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   | P |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+  
|   |   |   |   |
+---+---+---+---+

例如，对于一个4x4的矩阵，如果起始点是P（1,1）（startRow =（4-1）/ 2， startCol =（4-1）/ 2），只有一种方式可以逆时针螺旋移动（upDown = true，leftRight = true，moveCol = false）。

第二个问题可以采用类似的方法。

if (leftToRight) {

    /* printing entire row left to right */
    for (int i = startCol; i <= endCol; i++) {
        stringBuffer.append(matrix[startRow][i]);
        counter--;
    }
    leftToRight = false;
    moveCol = false;
    endCol++;
}

- vutran

Answer 3

这很简单，看看我的解决方案：

class Region  {
    int left, right, top, bottom;
    Region(int _left, int _right, int _top, int_bottom) {
        left=_left;  right=_right;  top=_top;  bottom=_bottom; 
    }
    boolean isEmpty() { return (left>right || top>bottom); }
    boolean isSingleElement() { return (left==right && top==bottom); }
}

List<Coordinate> traverseClockWise(Region r) {
    List<Coordinate> l = new List<Coordinate>();
    if (r.isEmpty()) {
        return l; 
    }
    if (r.isSingleElement()) {
        l.add(new Coordinate(r.left, r.top));
        return l; 
    }

    for (int i=r.left; i<r.right; i++) {
        l.add(new Coordinate(i, r.top));
    }
    for (int i=r.top; i<r.bottom; i++) {
        l.add(new Coordinate(r.right, i));
    }
    for (int i=r.right; i>r.left; i--) {
        l.add(new Coordinate(i, r.bottom));
    }
    for (int i=r.bottom; i>r.top; i--) {
        l.add(new Coordinate(r.left, i));
    }

    l.addAll(traverseClockWise(new Region(r.left+1, r.right-1, r.top+1, rs.bottom-1)));
    return l;
}


void traverse(Matrix A, int row, int col)  {
}

void example() {
    //suppose A is the matrix you are given and n is the size of the matrix
    Matrix A = new Matrix(n,n);
    List<Coordinates> l = traverseClockWise(new Region(1, n, 1, n));

    // to traverse it from top left counterclockwise
    for (int i=0; i<l.size(); i++) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and clockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].col, l[i].row);
    }

    // to traverse it from the middle and counterclockwise
    for (int i=l.size()-1; i>=0; i--) {
        traverse(A, l[i].row, l[i].col);
    }
}

- lindenrovio