找出3个数最大的乘积

interview.js

/*
 * 题目：
 *
 * 给定一个n * n的矩阵，例如: 
 * 10 45 90 11
 * 23 68 29 09
 * 49 39 23 78
 * 46 92 21 90
 *
 * 写一个函数找出连续三个数的最大的乘积，条件如下：
 * 这三个数必须是连续的，例如10、45、90是这样的数，但10、45、11不是 
 * 这些数可以在水平，竖直，斜线方向连续
 *
 *
 * 解题思路：
 *
 * 方法一：用传统的思维，从左到右，由上到下，以及斜边的方向上找到合适的数组，然后将里面的数相乘（缺点是逻辑会变得比较复杂）。
 * 方法二：就是以下脚本，遍历每一个数，以该数为中心点，向周边扫描，以一定的长度为半径，匹配成合法的数组再进行计算，最终得到的所有积汇集到数组中，进行排序（但缺点是可能会有重复的计算以及做全局的遍历）。
 *
 */


var items = [[10, 45, 90, 11],[23,68, 29, 9],[49, 39, 23, 78], [46, 92, 21, 90]];
var items2 = [[34, 84, 75, 35],[55,21,89,36],[75,95,35,64], [25,45,95,49]];

var find_largest = function( square ) {

  var printAllNumbers = function ( square ){
    for( var i in square ){
      for( var n in square[i] ){
        //console.log( square[i][n] + '该数字的 : ' );
        //get all numbers from the square 
        scanNumbers( square , i , n );
        // x = i , y = n 
      }
    }
  };

  //scan other numbers around it
  //设定半径
  //set radius
  var r = 3;
  var finalArray = [];
  var scanNumbers = function ( square , x , y ){
    var directionCombination = [
      {"name":"east", "x" : 0 , "y" : 1 },
      {"name":"west", "x" : 0 , "y" : -1 },
      {"name":"south", "x" : 1 , "y" : 0 },
      {"name":"north", "x" : -1 , "y" : 0 },
      {"name":"east-north","x" : 1 , "y" : -1 },
      {"name":"east-south","x": 1 , "y" : 1 },
      {"name":"west-north","x" : -1 , "y" : -1 },
      {"name":"west-south","x": -1 , "y" : 1 }
    ];
    var allArray = [];
    for( var m in directionCombination ){
      var eachArray = [];
      for( var i = 0 ; i < r ; i ++ ){
        var a = i*directionCombination[m]['x'];
        var b = i*directionCombination[m]['y'];
        var xValue = (parseInt(x) + a); 
        var yValue = (parseInt(y) + b);
        if( xValue < 0 || yValue < 0 || xValue > (square.length - 1) || yValue > (square.length - 1) ) continue;
        eachArray.push( square[ xValue ][ ( yValue ) ] );
      }
      var item = { 
        "name" : directionCombination[m]["name"],
        "list" : eachArray 
      };
      allArray.push( item ); 
    }
    //console.log( 'all array is' , allArray );
    for( var i in allArray ){
      if( allArray[i]['list'].length == r ){
        var num = 1;
        for( var p in allArray[i]['list'] ){
          num *= allArray[i]['list'][p];
        }
        finalArray.push( num );
      }
    }
  };

  var sortNumber = function (a,b){
    return a - b
  };

  printAllNumbers( square );

  var newArray = finalArray.sort(sortNumber);

  console.log( 'finalArray is : ' , finalArray.sort(sortNumber) );

  return newArray[ (newArray.length-1) ]; 
  
}

find_largest( items );
find_largest( items2 );
//Your answer should match these strings
console.log('Your answer should match these strings');
console.log(find_largest(items)===299880);
console.log(find_largest(items2)===496375);

var items = [[10, 45, 90, 11],[23,68, 29, 9],[49, 39, 23, 78], [46, 92, 21, 90]];
var items2 = [[34, 84, 75, 35],[55,21,89,36],[75,95,35,64], [25,45,95,49]];
var items3 = [[10, 45, 90, 11, 34, 84, 75, 35],[23,68, 29, 9, 34, 84, 75, 35],[49, 39, 23, 78, 34, 84, 75, 35], [46, 92, 21, 90, 34, 84, 75, 35], [10, 45, 90, 11, 34, 84, 75, 35],[23,68, 29, 9, 34, 84, 75, 35],[49, 39, 23, 78, 34, 84, 75, 35], [46, 92, 21, 90, 34, 84, 75, 35]];

/*
 * 方法：
 * 遍历每一个点，但是只找满足四个向量的点，这样可以避免重复出现的情况
 */
function find_largest(squire) {
    var start = Date.now()
    // 记录四个方向的向量， 分别是东北， 正东， 东南， 正南
    var k = [[1, -1], [1, 0], [1, 1], [0, 1]]
    var nMax = squire.length
    var resultArr = []
    for (var x in squire) {
        for (var y in squire[x]) {
            for ( var z in k) {
                // 两个坐标点，因为半径为3
                var x1 = +x + k[z][0]
                var x2 = +x + k[z][0] * 2
                var y1 = +y + k[z][1]
                var y2 = +y + k[z][1] * 2
                // 判断超出的点直接pass，留下存在的点
                if (x1 < nMax && x2 < nMax && squire[x1][y1] && squire[x2][y2]) {
                    resultArr.push(squire[+x][+y] * squire[x1][y1] * squire[x2][y2])
                }
            } 
        }
    }
    resultArr.sort(function(a, b) {
        return b - a
    })
    var time = Date.now() - start
    console.log('speed is' + time + 'ms')
    console.log('result is' + resultArr[0])
    return resultArr[0]
}

// find_largest(items)
// find_largest(items2)
find_largest(items3)