如何更改此矩阵螺旋遍历的方向和起点？

Question

我有一些代码（following this example）从左上角开始遍历矩阵，顺时针旋转。我想使基于关闭的这三个新方法：

• 一个从左上角开始并且前往逆时针
• 一个从中间开始，然后顺时针方向进入
• 一个从中间开始，逆时针走

我需要改变每一个这些工作？我尝试了反转计数器增量，并且没有成功地改变开始/结束行/列。

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()); 
} 

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; 

就个人而言，我更喜欢divide-and-conquer递归方法。由于围绕网格尺寸3x3的螺旋线基本上与围绕网格2x2螺旋缠绕的网格相同，因此您可以使用递归来查找&解决问题的最小版本并逐步建立到您的解决方案。

我强烈建议您分别考虑递归和除法&征服方法。如果您只是对解决螺旋遍历问题感兴趣，包括顺时针，逆时针，顺时针向外和逆时针向外，请参阅GitHub Gist here。

注意：上面提供的代码原样，没有任何保证任何种类。所以要警告。

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++; 
} 

Matrix，在其行＃和列＃是奇数，则可以选择通过（moveCol，左右改变，UPDOWN）定义的任何起动方向。然而，其行号＃或列号＃均匀的矩阵，则开始方向是重要的。

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

对于实施例，用一个4×4矩阵，如果起始点是P（1,1）（= STARTROW（4-1）/ 2，startCol =（4-1）/ 2），只有一个方式逆时针螺旋去（UPDOWN =真，左右改变=真，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++; 
} 

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); 
    } 
}