javascript - 这个矩阵挑战的任何想法或解决方案？

Question

嗨，我是练习算法的新手，我只是想知道如何解决这个螺旋矩阵挑战:

Have the function MatrixSpiral(strArr) read the array of strings stored in strArr which will represent a 2D N matrix, and your program should return the elements after printing them in a clockwise, spiral order. You should return the newly formed list of elements as a string with the numbers separated by commas. For example: 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' ]

能否请您分享任何解决方案？

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]  
                                            ---

并且我们可以通过反转矩阵转置的结果来编写逆时针旋转函数。换位是将其翻转到西北/东南对 Angular 线上。例如:

  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，所以它们在数组的数组上工作。)