8

最近のインタビューの質問で、次の問題がありました。

特定の都市では、さまざまな高さの建物が並んでいます。高さ h の建物が倒壊すると、その右側にある次の h-1 個の建物も倒壊します。建物の高さは 1 から 5000 の間で指定できます。すべての建物の高さ (左から右に配置されます。つまり、左端の建物のインデックス = 1 と右端の建物のインデックス = N) を考えると、最大の荒廃をもたらす建物。

例えば：

入力: 建物の数: 6

建物の高さ: 2 1 3 3 1 6

答えはインデックス3で構築する必要があります

私が試した解決策は、O（N ^ 2）の複雑さを持つブルートフォース手法を使用することでした。私がしたことは、リスト内の各建物について、それが破壊する建物の数を見つけ出すことでした。

この質問に対するより良い解決策を構築できますか?

4

5 に答える 5

10

左から順に、最初の建物を倒壊させ、合計(*)の損害を計算します。

これを次の建物（崩壊していない建物）から何度も繰り返します。

これらから、最大のものを選びます。

複雑さ: O(n)。

この貪欲なアルゴリズムが機能するのは、プロセス全体が連鎖反応であるためです。建物 A が B の崩壊を強制する場合、B から始めてより良いスコアを達成することはできません。

(*) これは、右側の何棟の建物を折りたたむかを格納する 1 つのカウンターを維持することで実行できます。 counter = max(counter - 1, height of next building).

于 2013-09-25T11:49:25.453 に答える
1
  1. 右端のインデックスから開始します。
  2. 最後の建物は、荒廃値 1 を引き起こします。
  3. 左に繰り返します。

のようなもの (建物 i からの荒廃)

D[i] = 1 + min( N-i, max( index[i]-1, 0+D[i+1],1+D[i+2],... to index[i]-1 terms ) )
于 2013-09-25T11:45:57.970 に答える
0

Java では、後続の崩壊を考慮せずに:

public static int collapse(int[] buildings) {
    int i, maxDamage, index, currentDamage;
    // do not consider the last building, it will cause only its own fall
    maxDamage = 1;
    index = buildings.length - 1;
    for(i = buildings.length - 1; i >= 0; i--) {
        // update maximum damage as the mimimum value between the building[i] (the height of the building at index i) and the remaining number of elements from i to the end of the array
        currentDamage = Math.min(buildings[i], buildings.length - i);
        System.out.println(currentDamage);
        if(currentDamage > maxDamage) {
            maxDamage = currentDamage;
            index = i;
        }
    }
    return index;
}

私の最終的な解決策は、受け入れられたものとは異なりますが、完全には理解できませんでした。アイデアは、現在のインデックスが崩壊する建物の数を右端の位置から数え始めることです。

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  4  1  3  2

次に、もう一度右端の位置から開始して、累積合計を作成します。右隣のビルから見て最後まで倒壊しなかったビルの数を、現在位置が崩壊するビルの数に加算する。

index:  7  6  5  4  3  2  1  0
height: 1  3  1  2  4  1  3  2
damage: 1  2  1  2  5  1  7  8

結局、ダメージが最大のインデックスを返すだけです。

このソリューションは実行されO(n)ますが、余分なO(n)スペースが使用されます。

次のコードは完全なバージョンです (後続の折りたたみでも機能します)。

public static int collapse(int[] buildings) {
    int i, maxIndex, max;
    int damage[] = new int[buildings.length];
    for(i = buildings.length - 1; i >= 0; i--) {
        // compute damage for each position
        damage[i] = Math.min(buildings[i], buildings.length - i);
    }
    for(i = buildings.length - 1; i >= 0; i--) {
        // update total accumulated damage for each position
        if(damage[i] > 1) {
            if(damage[i] + i - 1 < buildings.length && i != (i + damage[i] - 1) ) {
                damage[i] += damage[i + damage[i] - 1] - 1;
            }
        }
    }
    max = damage[0];
    maxIndex = 0;
    for(i = 1; i < buildings.length; i++) {
        // find the maximum damage
        if(damage[i] > max) {
            max = damage[i];
            maxIndex = i;
        }
    }
    return maxIndex;
}
于 2013-09-25T11:55:29.887 に答える