代码之家 › 专栏 › 技术社区 › No Name QA

盒子之塔

recursion algorithm java

-3

No Name QA · 技术社区 · 7 年前

我们有 N 盒。每个框有3个参数:宽度、长度和高度。

我需要写一个函数,用这个框生成可能最高的塔。函数必须遵守以下规则:底部框的所有参数都应大于其上方的框。

例子

假设我们有一个称为int数组的框 {width, length, height} -> {1, 2, 5} ,然后:

输入: boxes = {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}

输出: 8 自从 {4, 5, 4} greater than {2, 2, 3} greater than {1, 1, 1}

解决方案

我找到了一个我无法理解的解决方案。

void sortArrDesc(int[][] array) {
  Arrays.sort(array, new java.util.Comparator<int[]>() {
    public int compare(int[] a, int[] b) {
      return -1 * Integer.compare(a[2], b[2]);
    }
  });
}

boolean canPlaceOnTop(int prevBoxIndex, int currBoxIndex, int[][] boxes) {
  if (prevBoxIndex == -1) return true;
  int[] bottomBox = boxes[prevBoxIndex];
  int[] topBox = boxes[currBoxIndex];

  return (bottomBox[0] > topBox[0] && 
          bottomBox[1] > topBox[1] && 
          bottomBox[2] > topBox[2]);
}

int getHighestTower(int prevBoxIndex, int currBoxIndex, int[][] boxes) {
  if (currBoxIndex == boxes.length) return 0;

  int nextBoxIndex = currBoxIndex + 1;

  int heightWithCurrBox = 0;

  if (canPlaceOnTop(prevBoxIndex, currBoxIndex, boxes)) { 
    int currentBoxHeight = boxes[currBoxIndex][2];
    int heightNextBox = getHighestTower(currBoxIndex, nextBoxIndex, boxes);
    heightWithCurrBox = heightNextBox + currentBoxHeight;
  }

  int heightWithoutCurrBox = 
            getHighestTower(prevBoxIndex, nextBoxIndex, boxes);


  return Math.max(heightWithCurrBox, heightWithoutCurrBox);
}

int getHighestTower(int[][] boxes) {
  sortArrDesc(boxes);
  return getHighestTower(-1, 0, boxes);
}

我不明白到底是什么 getHighestTower 功能是什么。

例如,当我调用函数 Math.sqrt(5) 我知道我会得到5的平方根。但是在这里 高塔 发生了什么奇怪的事。

很明显,这个电话 getHighestTower(-1, 0, boxes) 将返回最高的塔。

但是当我们进行递归调用时,我不明白它们的意思。 getHighestTower(prevBoxIndex, nextBoxIndex, boxes)

这句话是什么意思?

似乎该调用应该返回从开始的最大可能高度 nextBox 那我们为什么要使用 prevBoxIndex ?

此外,这一呼吁 getHighestTower(currBoxIndex, nextBoxIndex, boxes); 看起来也一样,但不是 prevBoxIndex 我们使用 currBoxIndex 为什么?

另外,我已经找到这个了 question ,但它不包含任何有用的信息。

1 回复 | 直到 7 年前

SomeDude 7 年前

这个问题可以这样解决:

按高度把箱子分类。
然后问题是寻找高度之和最大的递增子序列——这里的“递增”意味着:

currLength > prevLength && currWidth > prevWidth && currHeight > prevHeight

输入 {{2, 2, 3}, {1, 1, 1}, {3, 3, 3}, {4, 5, 4}, {7, 7, 1}}

假设按高度排序的数组是:

{7,7,1}, {1,1,1}, {2,2,3}, {3,3,3}, {4,5,4}

然后,使用上述准则的递增子序列是

{1,1,1}, {3,3,3}, {4,5,4}

那么身高就是 1 + 3 + 4 = 8 .

为什么需要先按高度排序? 因为,假设输入是

{{4,5,4}, {2,2,3}, {1,1,1}, {3,3,3}, {7,7,1}}

如果不按高度排序,则按上述标准递增的子序列将产生

{1,1,1}, {3,3,3}

答案是 1 + 3 = 4 这不是最优的。

Java代码:

 private static int getHeighestTower( int[][] x ) {
    Arrays.sort( x, new Comparator<int[]>() {
      @Override
      public int compare( int[] a, int[] b ) {
        return a[2] - b[2];
      }
    });

    int[] L = new int[x.length];
    Arrays.fill(L,1);
    int max = 0;
    int h = 0;
    int hi = 0;
    for ( int i = 0; i < x.length; i++ ) {
      hi = x[i][2];
      int lastAdded = 0;
      for ( int j = 0; j < i; j++ ) {
        if ( aBiggerThanB(x[i], x[j]) ) {
          if ( L[i] < 1 + L[j] ) {
            L[i] = 1 + L[j];
            hi += x[j][2];
            lastAdded = x[j][2];
          } else if ( L[i] == 1 + L[j] ) {
            hi = Math.max( hi, hi - lastAdded + x[j][2]);
          }
        }
      }
      h = Math.max( h, hi);
      max = Math.max( max, L[i] );
    }

    return h;
 }

 private static boolean aBiggerThanB( int[] a, int[] b ) {
    return a[0] > b[0] && a[1] > b[1] && a[2] > b[2];
 }