这个矩阵挑战有什么想法或解决方案吗？

Question

你好，我是一名练习算法的新手，我正在思考如何解决这个螺旋矩阵挑战：

编写函数 MatrixSpiral(strArr)，该函数会读取存储在 strArr 中的字符串数组，该数组将表示一个二维 N 矩阵，您的程序应打印此矩阵的元素，并按顺时针螺旋顺序返回这些元素。您应该将新形成的元素列表作为字符串返回，其中数字用逗号分隔。例如：input:

["[4, 5, 6, 5]",   
 "[1, 1, 2, 2]",  
 "[5, 4, 2, 9]"]   

输出：

"4,5,6,5,2,9,2,4,5,1,1,2"

我之前做过简单的矩阵螺旋，但不知道如何解决这样的问题。

这不是一个简单的矩阵螺旋。我尝试了这段代码，但输出完全不同。

输入是一个由“字符串数组”组成的数组（请参见双引号），输出应为用逗号分隔的数字字符串。

const spiralOrder = (matrix) => {

if(!matrix.length || !matrix[0].length){
        return [];
}
//Use 4 pointes to create wall around square
let rowBegin = 0,
    rowEnd = matrix.length - 1,
    colBegin = 0,
    colEnd = matrix[0].length - 1;

let result = [];
while(rowBegin <= rowEnd && colBegin <= colEnd){

    //move right
    for(let i= colBegin; i<= colEnd; i++){
            result.push(matrix[rowBegin][i]);
    }
    rowBegin++; // mark row as traversed after moving right

    //move down
    for(let i=rowBegin; i<= rowEnd; i++){
            result.push(matrix[i][colEnd]);
    }
    colEnd--; //mark column as traversed after moving down

    //move left
    if(rowBegin <= rowEnd){
            for(let i=colEnd; i >= colBegin; i--){
                    result.push(matrix[rowEnd][i]); 
            }
    }
    rowEnd--; //mark end row as traversed after moving left

    //move up
    if(colBegin <= colEnd){ 
            for(let i=rowEnd; i >= rowBegin; i--){
                    result.push(matrix[i][colBegin]);
            }
    }
    colBegin++; //mark begining column as traversed after moving up
}

return result;
};

spiralOrder([[4, 5, 6, 5], [1, 1, 2, 2], [5, 4, 2, 9]])

Output: [ '[',
  '4',
  ',',
  ' ',
  '5',
  ',',
  ' ',
  '6',
  ',',
  ' ',
  '5',
  ']',
  ']',
  ']',
  '9',
  ' ',
  ',',
  '2',
  ' ',
  ',',
  '4',
  ' ',
  ',',
  '5',
  '[',
  '[',
  '1',
  ',',
  ' ',
  '1',
  ',',
  ' ',
  '2',
  ',',
  ' ',
  '2' ]

你能分享一下任何解决方案吗？

- Mauricio Orozco

---

可能是以螺旋顺序打印二维数组的重复问题。 - tevemadar

@JohnColeman 感谢您的回答。我已经编辑了我的问题。我认为现在有点不同了。 - Mauricio Orozco

谢谢。问题改进很多。 - John Coleman

Answer 1

一种有所不同的方法，符合“递归”标签的特点，是注意到处理螺旋的一个好方法是取出顶部行，将其移除，将矩阵逆时针旋转，然后重复该过程，直到完成所有行。它看起来像这样:

->  4 5 6 5  --------------+ 
    1 1 2 2  \_ rotate     |
    5 4 2 9  /          ___V___
                       [4 5 6 5]
                        -------

->  2 9  ------------------------+         
    2 2 \                        |
    1 4  +- rotate               |
    1 5 /                       _V_
                       [4 5 6 5 2 9]
                                ---

->  2 4 5  ---------------------------+  
    2 1 1  >- rotate                __V__
                       [4 5 6 5 2 9 2 4 5]  
                                    -----

->  1  -----------------------------------+
    1  \_ rotate                          |
    2  /                                  V
                       [4 5 6 5 2 9 2 4 5 1]  
                                          - 

->  1 2  ------------------------------------+
                                            _V_
                       [4 5 6 5 2 9 2 4 5 1 1 2]  
                                            ---

我们可以通过反转转置矩阵的结果来编写逆时针旋转函数。 转置是将矩阵沿西北/东南对角线翻转。例如：

  transpose([[1, 2, 3], 
             [4, 5, 6]])

  //=>      [[1, 4],
  //         [2, 5],
  //         [3, 6]]

将那些行反转，我们得到

  //        [[3, 6],
  //         [2, 5],
  //         [1, 4]]

这是一个逆时针旋转输入的代码。

因此，代码涉及几个可重用的函数，可能会像这样：

const reverse = a => 
  [...a] .reverse ();

const transpose = m => 
  m [0] .map ((c, i) => m .map (r => r [i]))

const rotate = m => 
  reverse (transpose (m))

const spiral = m => m .length < 2
  ? [... m [0]]
  : [... m [0], ... spiral (rotate (m .slice (1))) ] 

const spiralOrder = (strs) => 
  spiral (strs .map (row => JSON .parse (row)) ) .join (',')


console .log (
  spiralOrder(["[4, 5, 6, 5]",   
               "[1, 1, 2, 2]",  
               "[5, 4, 2, 9]"
  ])
)

spiralOrder 是唯一处理您略微不寻常输入的函数。spiral、transpose、rotate 和 reverse 只对普通矩阵起作用。 （当然，这是JS，所以它们适用于数组的数组。）

- Scott Sauyet

---

很好的问题功能分解 ^^ - Mulan

Answer 2

你可以采用四个方向和一个索引对（i/j）的方法，以及另外四个变量来限制循环范围，分别是上限（upper）、下限（lower）、左边界（left）和右边界（right）。

在取得限制之后，检查并增加或减少限制。如果限制不在所需的范围内，则循环结束。

最后，将剩余项添加到结果集中。

function getSpiral(data) {
    var array = data.map(j => JSON.parse(j)),
        upper = 0,
        lower = array.length - 1,
        left = 0,
        right = array[0].length - 1,
        i = upper,
        j = left,
        result = [];

    while (true) {
        if (upper++ > lower) break;

        for (; j < right; j++) result.push(array[i][j]);
        if (right-- < left) break;

        for (; i < lower; i++) result.push(array[i][j]);
        if (lower-- < upper) break;

        for (; j > left; j--) result.push(array[i][j]);
        if (left++ > right) break;

        for (; i > upper; i--) result.push(array[i][j]);
    }
    result.push(array[i][j]);

    return result.join(',');
}

console.log(getSpiral(['[4, 5, 6, 5]', '[1, 1, 2, 2]', '[5, 4, 2, 9]']));
console.log(getSpiral(['[1, 2, 3, 4, 5]', '[6, 7, 8, 9, 10]', '[11, 12, 13, 14, 15]', '[16, 17, 18, 19, 20]']));

- Nina Scholz

Answer 3

我们可以观察到转折点（或多或少）发生在对角线上。函数f是主递归处理程序，基本上是一个for循环。

function turnAndDeltas(direction){
  return {
            // dy dx
    'r': ['d', 0, 1],
    'd': ['l', 1, 0], 
    'l': ['u', 0,-1],
    'u': ['r',-1, 0]
  }[direction]
}

function isDiagonal(h, w, y, x){
  if (x >= w >> 1)
    return (y == w - x - 1) || (h - y - 1 == w - x - 1)
  else if (y > h >> 1)
    return (h - y - 1 == x)
  else
    return (y - 1 == x)
}
 
function f(h, w, d, y, x, count, fun){
  if (count == 0)
    return

  fun(y, x)

  let [_d, dy, dx] = turnAndDeltas(d)

  if (isDiagonal(h, w, y, x))
    [_, dy, dx] = turnAndDeltas(d = _d)

  f(h, w, d, y+dy, x+dx, count-1, fun)
}

function g(h, w, fun){
  f(h, w, 'r', 0, 0, h*w, fun)
}

var m = ["[ 1, 2, 3, 4]",
         "[10,11,12, 5]",
         "[ 9, 8, 7, 6]"]
        
var M = m.map(x => eval(x))

function fun(y, x){
  console.log(M[y][x])
}

g(M.length, M[0].length, fun)

m = ["[ 1, 2, 3]",
     "[10,11, 4]",
     "[ 9,12, 5]",
     "[ 8, 7, 6]"]
     
M = m.map(x => eval(x))

g(M.length, M[0].length, fun)

- גלעד ברקן