寻找最佳解决方案 [英] Looking for a optimal solution

问题描述

这是亚马逊的采访问题之一。
给定一个0和1的二维数组，我们需要找到最大大小的模式。
Patters如下：

size = 1：

  1 
 1 1 1 
 1 
  

size = 2： p>

  1 
 1 
 1 1 1 
 1 
 1 
  

朴素解决方案：遍历MxN矩阵的每个元素，并搜索具有值的索引1并检查是否留下正确的条目为1，并记录索引上下1个的最大长度。

寻找更好的解决方案。如果有人有一个线索请做帖子。

解决方案

我假设围绕这样一个模式的任何1个值都不会破坏它，所以这也将具有1：

  1 1 1 1 
 1 1 1 1 
 1 1 0 1 
 1 1 1 1 
  

在这种情况下，我会建议一个算法，其中对于每列，您执行以下操作： p>

1. 初始化大小为0


2. 对于此列中的每个单元格：
   
   
   
   
   • 推送堆栈上的当前大小它表示从该单元开始向上的1个值的数量。
   
   
   • 如果此单元格中的值为1，则增加大小，否则设置它为0
   
   


3. 初始化大小为0


4. 单元格在这一列，但是相反的顺序：
   
   
   
   
   • 从栈中弹出最后一个值
   
   
   • 调用 thisSize 弹出值中的最小值和大小的值。
   
   
   • 如果 thisSize 大于目前为止找到的最佳图案，当前单元格的两边的值为1，则将其视为最佳图案。 / li>
     
   • 如果此单元格中的值为1，则增加大小，否则将其设置为0
   
   

作为进一步优化，只要当前单元格与网格顶部之间的距离变小，就可以退出第二个循环

这是JavaScript中的一个实现：

  function findPattern（a）{var rows = a.length，cols = a [0] .length，maxSize = -1，stack = [] ，col，pos，thisSize; for（col = 1; col  

This was one of the interview questions in amazon. Given a 2D array of 0's and 1's we need to find the pattern of maximum size. Patters is as follows:

size = 1:

   1
 1 1 1 
   1

size = 2:

   1
   1 
 1 1 1 
   1 
   1

Naive Solution: Traverse each and every element of MxN matrix, and search for the index with value 1 and check if left & right entries as 1 and note the maximum length of 1's above and below the index.

Looking for a better solution. If anyone has a clue please do post.

解决方案

I assume that any 1 values that surround such a pattern do not destroy it, so that also this would have size 1:

1 1 1 1
1 1 1 1
1 1 0 1
1 1 1 1

In that case I would suggest an algorithm where for each column you do the following:

1. Initialise size as 0
2. For each cell in this column:
   • Push the current size on a stack; it represents the number of 1 values in the upward direction starting from this cell.
   • If the value in this cell is a 1, then increase size, otherwise set it to 0
3. Initialise size as 0
4. For each cell in this column, but in reverse order:
   • Pop the last value from the stack
   • Call thisSize the least of the popped value and the value of size.
   • If thisSize is greater than the best pattern found so far and the values at both sides of the current cell are 1, then consider this the best pattern.
   • If the value in this cell is a 1, then increase size, otherwise set it to 0

As a further optimisation you could exit the second loop as soon as the distance between the current cell and the top of the grid becomes smaller than the size of the largest pattern we already found earlier.

Here is an implementation in JavaScript:

function findPattern(a) {
    var rows = a.length,
        cols = a[0].length,
        maxSize = -1,
        stack = [],
        row, col, pos, thisSize;
        
    for (col = 1; col < cols-1; col++) {
        stack = [];
        // Downward counting to store the number of 1s in upward direction
        size = 0;
        for (row = 0; row < rows; row++) {
            stack.push(size);
            size = a[row][col] == 1 ? size + 1 : 0;
        }
        // Reverse, but only as far as still useful given the size we already found
        size = 0;
        for (row = rows - 1; row > maxSize; row--) {
            thisSize = Math.min(size, stack.pop());
            if (thisSize >= maxSize && a[row][col-1] == 1 && a[row][col+1] == 1) {
                maxSize = thisSize;
                pos = [row, col];
            }
            size = a[row][col] == 1 ? size + 1 : 0;
        }
    }
    return [maxSize, pos];
}

// Sample data:
var a = [
    [0, 0, 1, 0, 0, 1, 0],
    [0, 0, 1, 1, 0, 1, 0],
    [1, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 1, 0],
    [1, 1, 1, 1, 0, 1, 0],
    [0, 1, 1, 1, 1, 1, 1],
    [0, 0, 1, 0, 0, 1, 0]];

var [size, pos] = findPattern(a);

console.log('Size ' + size + ' with center at row ' + (pos[0]+1) 
            + ' and column ' + (pos[1]+1) + ' (first row/col is numbered 1)');

这篇关于寻找最佳解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！