如何递归地螺旋遍历矩阵

how to spirally traverse a matrix recursively - javascript

本文关键字：螺旋 遍历 何递归 递归      更新时间：2023-09-26

请看这个JSFiddle: https://jsfiddle.net/hc2jcx26/

我正在尝试螺旋遍历矩阵output(任何大小)，以便它每2秒以螺旋顺序打印每个元素到console.log:

var output = [[0, 1, 2, 3],
              [4, 5, 6, 7]];

我期待这样的输出:

0
1 //after 2 seconds delay
2 //after 2 seconds delay
3 //etc.
7
6
5
4

但是我没有得到这个与上面的代码。输出到处都是，甚至没有正确的元素数量。我使用递归在每次迭代后(通过setTimeout)在我的循环中添加延迟，但我认为我没有正确设置变量。但是当我看代码时，它对我来说是有意义的。我遗漏了什么?

这是我解决你问题的方法。

迭代版本

var matrix1 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
], matrix2 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    [10, 11, 12]
], matrix3 = [
    [0, 1, 2, 3],
    [4, 5, 6, 7]
], matrix4 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
(function (matrix) {
    var i,
        nRows = matrix.length,
        nCols = matrix[0].length,
        rowLimit = nRows - 1,
        colLimit = nCols - 1,
        rounds = 0,
        printedElements = 0,
        nElements = nRows * nCols,
        timeoutLapse = 2000;
    function print(val) {
        printedElements += 1;
        setTimeout(function () {
            console.log(val);
        }, printedElements * timeoutLapse);
    }
    do {
        for (i = rounds; i <= colLimit - rounds; i += 1) {// from left to right
            print(matrix[rounds][i]);
        }
        for (i = rounds + 1; i <= rowLimit - rounds; i += 1) {// from top to bottom
            print(matrix[i][colLimit - rounds]);
        }
        for (i = colLimit - rounds - 1; i >= rounds; i -= 1) {// from right to left
            print(matrix[rowLimit - rounds][i]);
        }
        for (i = rowLimit - rounds - 1; i >= rounds + 1; i -= 1) {// from bottom to top
            print(matrix[i][rounds]);
        }
        rounds += 1;
    } while (printedElements < nElements);
})(matrix4);

这是小提琴(你必须打开控制台才能看到结果)。

递归版本

var matrix1 = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
], matrix2 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9],
    [10, 11, 12]
], matrix3 = [
    [0, 1, 2, 3],
    [4, 5, 6, 7]
], matrix4 = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];
(function(matrix){
    var printedElements = 0,
        timeoutLapse = 1000;
    function print(val) {
        printedElements += 1;
        setTimeout(function () {
            console.log(val);
        }, printedElements * timeoutLapse);
    }
    function printArray(arr) {
        for(var i = 0; i < arr.length; i++) {
            print(arr[i]);
        }
    }
    // Recursive algorithm, consumes the matrix.
    function printMatrix(matrix, direction) {
        var dir = direction % 4,
            rowLimit = matrix.length - 1,
            i;
        if (dir === 0) {// from left to right
            printArray(matrix.shift());
        } else if (dir === 1) {// from top to bottom
            for(i = 0; i <= rowLimit; i++) {
                print(matrix[i].pop());
            }
        } else if (dir === 2) {// from right to left
            printArray(matrix.pop().reverse());
        } else {// from bottom to top
            for(i = rowLimit; i >= 0; i--) {
                print(matrix[i].shift());
            }
        }
        if (matrix.length) {// Guard
            printMatrix(matrix, direction + 1);
        }
    }
    // Initial call.
    printMatrix(matrix, 0);
})(matrix4);

我添加了一些例子来测试它。我只是按照螺旋模式每两秒钟打印出矩阵的元素。

可以看到，递归版本更具有声明性，尽管它完全清空了矩阵。这是小提琴

try

var output = [[0, 1, 2, 3],
                 [4, 5, 6, 7]];
    var columns = output[0].length;
    var row;
    function spiralOrderRecursive (matrix, rowIndex) {
      rowIndex = rowIndex || 0;
      if (matrix.length) {
        row = rowIndex % 2 ? matrix[0].reverse() : matrix[0];
        row.forEach(function (item, index) {
          setTimeout(function () {
            console.log(item);
          }, (rowIndex * columns + index) * 2000);
        });
        spiralOrderRecursive (matrix.slice(1), ++rowIndex);
      }
    }
spiralOrderRecursive(output);

也是NON - RECURSIVE

var output = [[0, 1, 2, 3, 5],
                  [6, 7, 8, 9, 10],
                  [11, 12, 13, 14, 15],
                  [16, 17, 18, 19, 20]];;
var columns = output[0].length;
function spiralOrder(output) {
      output.forEach(function (row, rowIndex) {
        row = rowIndex % 2 ? row.reverse() : row;
        row.forEach(function (item, index) {
          setTimeout(function () {
            console.log(item);
          }, (rowIndex * columns + index) * 2000);
        });
      });
    }
spiralOrder(output);

你想做的伪代码

spiral_print(matrix)
{ 
 If the matrix has one row
   print the row and go to new line
 else if the matrix has two rows
  print the first row and go to new line
  sleep(2)
  print the second row in reverse order and go to new line
 else
  print the first row and go to new line
  sleep(2)
  print the second row in reverse order and go to new line
  sleep(2)      
  spiral_print(matrix.slice(2))
}

Using JS

更新:利用@acontell的打印功能 

function spiral(matrix) {
    if (matrix.length <= 0) {
        return
    }
    for (var i = 0; i < matrix[0].length; i++) {
        print(matrix[0][i])
    }
    //Get last col
    for (var i = 1; i < matrix.length; i++) {
        print(matrix[i][matrix[0].length - 1])
    }
    //Get last row
    for (var i = matrix[0].length - 2; i >= 0; i--) {
        print(matrix[matrix.length-1][i])
    }
    //Get first column
    for (var i = matrix.length - 2; i > 0; i--) {
        print(matrix[i][0])
    }
    matrix = matrix.slice(1, -1)
    for (var i = 0; i < matrix.length; i++) {
        matrix[i] = matrix[i].slice(1, -1)
    }
    spiral(matrix)
}           
function print(val) {
    printedElements += 1;
    setTimeout(function () {
        console.log(val);
    }, printedElements * 2000);
}
var printedElements = 0
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]
spiral(matrix1)
使用Python

注意:使用numpy

会容易得多
def spiral(matrix):
    if len(matrix) <= 0:
        return
    for v in matrix[0]:
        print(v)
    last_col = [matrix[i][len(matrix[0]) - 1] for i in range(1,len(matrix))]
    for v in last_col:
        print(v)
    last_row = reversed(matrix[len(matrix)-1][0:-1])
    for v in last_row:
        print(v)
    first_col = [matrix[i][0] for i in range (1, len(matrix) - 1)]
    first_col = reversed(first_col)
    for v in first_col:
        print(v)
    matrix = matrix[1:len(matrix) - 1]
    matrix = [m[1:len(matrix[0]) - 1] for m in matrix]
    spiral(matrix)
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]
spiral(matrix1)

UPDATE: With numpy

import numpy as np
def spiral(matrix):
    if len(matrix) <= 0:
        return
    for v in matrix[0]:
        print(v)
    last_col = matrix[1:, -1]
    for v in last_col:
        print(v)
    last_row = reversed(matrix[-1, :-1])
    for v in last_row:
        print(v)
    first_col = reversed(matrix[1:-1, 0])
    for v in first_col:
        print(v)
    matrix = matrix[1:-1, 1:-1]
    spiral(matrix)
matrix = [[1, 2, 3, 4],
            [5, 6, 7, 8],
            [9, 10, 11, 12],
            [13, 14, 15, 16]]
matrix1 = [[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]]
matrix2 = np.array([[1, 2, 3, 4, 31],
            [5, 6, 7, 8, 32],
            [9, 10, 11, 12, 33],
            [13, 14, 15, 16, 34],
            [35, 36, 37, 38, 39]])

spiral(matrix2)
相关文章：