javascript - Any Idea or solution to this matrix challenge? - Stack Overflow

admin管理员组

文章数量:1332889

Hi I'm newbie practicing algorithms, I was just wondering how to solve this spiral matrix Challenge:

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 mas. For example: input:

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

output:

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

I have done simple matrix spiral before, but don't know how to solve one like this.

This is not a simple matrix spiral. I tried with this code, but output is way different

The input is an array of "string arrays" (see the double quotes), and the output should be a string with the numbers separated by mas.

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

Could you please share any solution?

Hi I'm newbie practicing algorithms, I was just wondering how to solve this spiral matrix Challenge:

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 mas. For example: input:

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

output:

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

I have done simple matrix spiral before, but don't know how to solve one like this.

This is not a simple matrix spiral. I tried with this code, but output is way different

The input is an array of "string arrays" (see the double quotes), and the output should be a string with the numbers separated by mas.

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

Could you please share any solution?

• javascript
• algorithm
• recursion

Share Improve this question Follow edited Sep 15, 2019 at 20:53 Mauricio Orozco asked Sep 15, 2019 at 17:13 Mauricio OrozcoMauricio Orozco 7522 silver badges66 bronze badges 3

• 2 Possible duplicate of Print two-dimensional array in spiral order – tevemadar Commented Sep 15, 2019 at 17:17
• @JohnColeman thanks for your answer. I have edit my question. I think is a bit different now. – Mauricio Orozco Commented Sep 15, 2019 at 17:38
• Thanks. Much improved question. – John Coleman Commented Sep 15, 2019 at 17:42

Add a ment  | 

3 Answers 3

Sorted by: Reset to default 4

A somewhat different approach, one that fits the "recursion" tag, is to note that one good way to handle a spiral is to take the top row, remove it, rotate the matrix counterclockwise, and repeat until you've pleted all rows. It looks something like this:

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

And we can write a counterclockwise rotation function just by reversing the result of transposing the matrix. A transposition is flipping it over the Northwest/Southeast diagonal. For example:

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

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

reversing those rows, we get

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

which is a counter-clockwise rotation of the input.

So the code, involving a few reusable functions, might look like this:

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 is the only function that deals with your somewhat unusual input. spiral, transpose, rotate, and reverse reverse work on plain matrices. (Well, it's JS, so they work on a an array of arrays.)

You could take an approach with four directions and an index pair (i/j), as well as four more variables for limiting the loops with upper and lower bound, as well as left and right limits.

After taking a limit, the limit is checked an incremented or decremented. If the limit is not inside of the wanted range, the loops ends.

At the end, the left over item is added to the result set.

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]']));

We can observe that turns happen (more or less :) on the diagonals. The function, f, is the main, recursive handler, which is basically a for loop.

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)

本文标签： javascriptAny Idea or solution to this matrix challengeStack Overflow