查找陣列對角線

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; 
} 

但它並不一定是所有的解決方案

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

Answer 2

我會預處理陣列通過使數字形成對角線向上下相互轉動每個子陣列。首先定義功能向任意方向旋轉，通過n元素單一陣列：

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

你的陣列會是這個樣子：

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

和功能的不斷增加在任一方向的量旋轉每個子陣列這與垂直排隊的人一樣：

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

現在問題已經減少到尋找垂直線。要做到這一點，這將是最簡單的先轉的數組，你可以做：

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

您現在可以測試的四個或更多的人任何運行的存在與

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

捕捉究竟對角運行發生留作練習的信息。

Answer 3

那麼這是最好的，因爲它從我這裏得到。它只在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++){ 
 
    \t for(var y = 0; y <= x && y < minDim; y++){ 
 
    \t item1 = a[y][x-y];   // slash test on x axis 
 
    \t item2 = a[yLen-1-y][x-y]; // backslash test on x axis 
 
    \t temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1) 
 
    \t            : (temp1.push(item1), quadros.push(temp1), temp1 = []) 
 
    \t      : temp1 = [item1]; 
 
    \t temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2) 
 
    \t            : (temp2.push(item2), quadros.push(temp2), temp2 = []) 
 
    \t      : temp2 = [item2]; 
 
    \t } 
 
    \t temp1 = []; 
 
    \t temp2 = []; 
 
    } 
 
    for (var y = 1; y <= yMax; y++){ 
 
    \t for(var x = xLen-1; x >= xLen - minDim + y; x--){ 
 
    \t item1 = a[y-x+xLen-1][x]; // slash test on y axis 
 
    \t item2 = a[yLen-y-xLen+x][x];// backslash test on y axis 
 
    \t temp1[0] === item1 ? temp1.length < rep-1 ? temp1.push(item1) 
 
    \t            : (temp1.push(item1), quadros.push(temp1), temp1 = []) 
 
    \t      : temp1 = [item1]; 
 
    \t temp2[0] === item2 ? temp2.length < rep-1 ? temp2.push(item2) 
 
    \t            : (temp2.push(item2), quadros.push(temp2), temp2 = []) 
 
    \t      : temp2 = [item2]; 
 
    \t } 
 
    \t temp1 = []; 
 
    \t 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);