8

Cracking the Coding Interview, Fourth Editionには、次のような問題があります。

サーカスは、互いに肩の上に立つ人々からなる塔のルーチンを設計しています. 実用的および美的理由から、各人は、その下にいる人よりも背が低くて軽い必要があります. サーカスの各人の身長と体重を考えると,そのような塔にいる人の最大数を計算する方法を書いてください。

例: 入力 (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)

出力: 最長の塔は長さ 6 で、上から下まで: (56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)

これが本の解決策です

ステップ 1 すべてのアイテムを最初に高さで並べ替え、次に重量で並べ替えます。これは、すべての高さが一意である場合、アイテムは高さで並べ替えられることを意味します。高さが同じ場合、アイテムは重量で並べ替えられます。

ステップ 2 増加する高さと増加する重みを含む最長のシーケンスを見つける これを行うには、次のようにします。

a) シーケンスの先頭から開始 現在、max_sequence は空です

b) 次のアイテムの身長と体重が前のアイテムよりも大きくない場合、このアイテムは「不適合」とマークされます</p>

c) 見つかったシーケンスに「最大シーケンス」よりも多くの項目がある場合、「最大シーケンス」になります</p>

d) その後、元のシーケンスの最後に到達するまで、「不適合アイテム」から検索を繰り返します。

その解決策についていくつか質問があります。

Q1

この解決策は間違っていると思います。

例えば

(3,2) (5,9) (6,7) (7,8)

明らかに(6,7)不適合品ですが、いかが(7,8)でしょうか？解決策によれば、 h と w が よりも大きいので不適切ではありませんが(6,7)、 に適合しないため、シーケンスに含めること(7,8)はできません(5,9)。

私は正しいですか？

私が正しければ、修正は何ですか？

Q2

O(n^2)上記のソリューションに修正があったとしても、ステップ 2-d に従って何度も繰り返す必要があるため、ソリューションのスタイルは少なくとも につながると思います。

O(nlogn) ソリューションを持つことは可能ですか?

4

5 に答える 5

0

これを自分で解決しようとしましたが、「既製のソリューション」を提供するつもりはありませんでしたが、それでも、自分の理解を確認し、コード(Python)が問題なく、すべてのテストケースで機能するかどうかを確認するために、さらに多くのことを提供しました。3ケース試してみたところ正解のようでした。

#!/usr/bin/python
#This function takes a list of tuples. Tuple(n):(height,weight) of nth person
def htower_len(ht_wt):
    ht_sorted = sorted(ht_wt,reverse=True)
    wt_sorted = sorted(ht_wt,key=lambda ht_wt:ht_wt[1])
    max_len = 1 

    len1 = len(ht_sorted)
    i=0
    j=0
    while i < (len1-1):
        if(ht_sorted[i+1][1] < ht_sorted[0][1]):
            max_len = max_len+1
        i=i+1           

    print "maximum tower length :" ,max_len

###Called above function with below sample app code.
testcase =1 
print "Result of Test case ",testcase   
htower_len([(5,75),(6.7,83),(4,78),(5.2,90)])

testcase = testcase + 1
print "Result of Test case ",testcase   
htower_len([(65, 100),(70, 150),(56, 90),(75, 190),(60, 95),(68, 110)])

testcase = testcase + 1
print "Result of Test case ",testcase   

htower_len([(3,2),(5,9),(6,7),(7,8)])
于 2013-07-24T12:21:00.303 に答える
0

最初に配列を高さと重みで並べ替えた後、コードは、配列内の残りのタプル (および可能性のある後続のタプル) のいずれかを取得した場合に最大のタワーがどのようになるかをチェックします。サブ問題の再計算を避けるためにsolution_a、 の末尾からの最適な最大長を格納するために使用されinput_arrayます。

これbeginning_indexは、要素を取得することを検討できるインデックス (人間のスタックの下に移動できる人を考慮することができるインデックス) でありbeginning_tuple、スタックの上位にある要素/人物を参照します。

このソリューションは、並べ替えを行うために O(nlogn) で実行されます。使用されるスペースは、solution_a配列と のコピーにO(n) ですinput_array。

def determine_largest_tower(beginning_index, a, beginning_tuple, solution_a):
    # base case
    if beginning_index >= len(a):
        return 0
    if solution_a[beginning_index] != -1:   # already computed
        return solution_a[beginning_index]

    # recursive case
    max_len = 0
    for i in range(beginning_index, len(a)):
        # if we can grab that value, check what the max would be
        if a[i][0] >= beginning_tuple[0] and a[i][1] >= beginning_tuple[1]:
            max_len = max(1 + determine_largest_tower(i+1, a, a[i], solution_a), max_len)
    solution_a[beginning_index] = max_len
    return max_len

def algorithm_for_human_towering(input_array):
    a = sorted(input_array)
    return determine_largest_tower(0, a, (-1,-1), [-1] * len(a))

a = [(3,2),(5,9),(6,7),(7,8)]
print algorithm_for_human_towering(a)
于 2015-01-04T20:30:58.543 に答える