在数组中对角线上查找相同的值。

Question

我有一个数组，比方说：

var array = [ [1, 0, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 1, 0],
              [0, 0, 1, 0, 1, 0, 0],
              [0, 0, 0, 1, 0, 0, 0],
              [0, 0, 1, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 0, 0]
            ]

我想创建一个查找任何数字在对角线上出现四次的匹配的功能。

目前，我正在使用：

function checkDiagonal(array, bottomToTop) {
    var Ylength = array.length;
    var Xlength = array[0].length;
    var maxLength = Math.max(Xlength, Ylength);
    var temp;
    var returnArray = [];
    for (var k = 0; k <= 2 * (maxLength - 1); ++k) {
        temp = [];
        for (var y = Ylength - 1; y >= 0; --y) {
            var x = k - (bottomToTop ? Ylength - y : y);
            if (x >= 0 && x < Xlength) {
                temp.push(array[y][x]);
            }
        }
        if(temp.length > 0) {
            returnArray.push(temp.join(''));
        }
    }
    return returnArray;
}

然而它并不总能找到所有的解决方案。

- Nick

---

这个链接可能对你有所帮助：http://stackoverflow.com/questions/21011011/multi-dimensional-array-check-for-diagonal-consecutive-values - Geeky

在这个例子中，你期望返回什么值？ - jjenzz

Answer 1

有趣的案例。实际上很难找到/编写一个简单的方法来解决这个问题。 我试图理解你的脚本，但发现它有点难以跟踪/调试，所以我尝试在自己的脚本中复制你所做的事情，并成功地得到了所需的结果。虽然我的代码比你的更长一些，但它声明了一些变量并附带了一些注释，因此更容易理解（对于将来的其他人）。

希望这可以帮助：

function checkDiagonal(array, matchCount) {
  var result = [];

  if(array.length >= matchCount) {
    // Search towards bottom-right.
    result = result.concat(getDiagonalResult(array, matchCount, 1));

    // Search towards top-right.
    result = result.concat(getDiagonalResult(array, matchCount, -1));
  } else {
    // No use searching if not enough rows are present.
  }

  return result;
}

function getDiagonalResult(array, matchCount, direction) {
  var result = [];

  // Specific from and to points to only search in possible rows (e.g. no use searching top-right on first row).
  var yFrom, yTo;

  // Search direction (bottom-right vs top-right).
  switch(direction) {
      // Bottom-right.
    case 1:
      yFrom = 0;
      yTo = (array.length - matchCount);
      break;

      // Top-right.
    case -1:
      yFrom = (matchCount - 1);
      yTo = (array.length - 1);
      break;
  }

  // Loop through all 'rows'.
  for(var y = yFrom; y <= yTo; y++) {

    // Loop through all 'columns'.
    for(var x = 0; x <= (array[y].length - matchCount); x++) {

      // Current value to match on.
      var originalValue = array[y][x];
      var matches = [];

      // Get matches.
      for(var i = 0; i < matchCount; i++) {
        // Search direction (row up or down).
        var yDirection = (i * direction);

        var value = array[y+yDirection][x+i];

        if(value === originalValue) {
          matches.push(value);
        }
      }

      if(matches.length == matchCount) {
        result.push(matches.join(""));
      }
    }

  }

  return result;
}

var array = [
  [1, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 1, 0],
  [0, 0, 1, 0, 1, 0, 0],
  [0, 0, 0, 1, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0]
];

console.log(checkDiagonal(array, 4));

- Richard

Answer 2

这是我能做到的最好的了。它仅计算一个 n 大小组中的每个元素一次。换句话说，存在于一个组中的元素不能存在于另一个组中。

这是一个使用最优数量的 x 和 y 起始索引的游戏，然后从该起始点开始计算每个元素的索引，沿着前后对角线移动。显然，我们应该在正确的 x 和 y 索引处开始和停止，以便我们可以找到对角线上的 n 个元素。随着 n 的增长，这将减少要完成的工作量。因此，具有每组12个元素的100x100数组将比每组4个元素的数组计算得快得多。

function getDiagonals(a,rep){
  var xLen = a[0].length,         // x dimension
      yLen = a.length,            // y dimension
      xMin = rep-1,               // minimum x value to start testing from
      xMax = xLen-rep,            // maximum x value to test up until
      yMin = rep-1,               // minimum y value to start testing from
      yMax = yLen-rep,            // maximum y value to test up until
    minDim = Math.min(yLen,xLen), // the smallest dimensison
   quadros = [],                  // the resutls array
     temp1 = [],                  // utility array #1
     temp2 = [],                  // utility array #2
     item1,                       // current element on the slash test
     item2;                       // current element on the backslash test

  for (var x = xMin; x < xLen; x++){
   for(var y = 0; y <= x && y < minDim; y++){
     item1 = a[y][x-y];          // slash test on x axis
     item2 = a[yLen-1-y][x-y];   // backslash test on x axis
     temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1)
                                               : (temp1.push(item1), quadros.push(temp1), temp1 = [])
                        : temp1 = [item1];
     temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2)
                                               : (temp2.push(item2), quadros.push(temp2), temp2 = [])
                        : temp2 = [item2];
   }
   temp1 = [];
   temp2 = [];
  }
  for (var y = 1; y <= yMax; y++){
   for(var x = xLen-1; x >= xLen - minDim + y; x--){
     item1 = a[y-x+xLen-1][x];   // slash test on y axis
     item2 = a[yLen-y-xLen+x][x];// backslash test on y axis
     temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1)
                                               : (temp1.push(item1), quadros.push(temp1), temp1 = [])
                        : temp1 = [item1];
     temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2)
                                               : (temp2.push(item2), quadros.push(temp2), temp2 = [])
                        : temp2 = [item2];
   }
   temp1 = [];
   temp2 = [];
  }
  return quadros;
}

var arr = [ [1, 0, 0, 0, 0, 0, 0],
            [0, 1, 0, 0, 0, 1, 0],
            [0, 0, 1, 0, 1, 0, 0],
            [0, 0, 0, 1, 0, 0, 0],
            [0, 0, 1, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0]
          ],
    brr = Array(100).fill().map(_ => Array(100).fill().map(e => ~~(Math.random()*2))),
 result = getDiagonals(arr,4);
console.log(JSON.stringify(result),result.length);
 result = getDiagonals(brr,12);
console.log(JSON.stringify(result),result.length);

- Redu

Answer 3

我会通过旋转每个子数组来预处理数组，以便形成对角线的数字彼此对齐。首先定义函数，将单个数组向左或向右旋转n个元素：

const rotateLeft     = (array, n) => array.slice(n).concat(array.slice(0, n));
const rotateRight    = (array, n) => rotateLeft(array, -n);

并且函数可以将每个子数组按递增的角度向任意方向旋转：

const rotateAllLeft  = array => array.map(rotateLeft);
const rotateAllRight = array => array.map(rotateRight);

你的数组现在会像这样，其中的1垂直排列：

var array = [ [1, 0, 0, 0, 0, 0, 0],
              [1, 0, 0, 0, 1, 0, 0],
              [1, 0, 1, 0, 0, 0, 0],
              [1, 0, 0, 0, 0, 0, 0],
              [0, 0, 0, 0, 0, 1, 0],
              [0, 0, 0, 0, 0, 0, 0]
            ]

问题现在被简化为寻找一列连续的1。为了做到这一点，最好先转置数组，可以使用以下代码实现：

const transpose = array => array[0].map((_, i) => array.map(row => row[i]));

我们现在将编写一个小函数，它接受一个数组并返回另一个数组，其值是特定值的“运行”长度：

const run = (array, val, cnt = 0) => array.map(elt => cnt = elt === val ? ++cnt : 0;

对于 [1, 1, 1, 1, 0, 0]，返回的结果应该是 [1, 2, 3, 4, 0, 0]。其中的 4 表示在此之前有四个连续的 1。

编写一些小函数来测试单个数组中特定长度的值的连续性，或者任何子数组中特定长度的值的连续性：

const hasRunOf = (array, val, n) => run(array, val).some(len => len >= n);
const hasAnyRunOf = (array, val, n) => array.some(subarray => hasRunOf(subarray, val, n));

现在您可以使用以下代码测试是否存在四个或更多个连续的1：

hasAnyRunOf(transpose(rotateAllLeft(array)), 1, 4) || 
  hasAnyRunOf(transpose(rotateAllRight(array)), 1, 4)        

捕获有关对角线运行发生的确切位置的信息留作练习。

- user663031