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)

这是书中的解决方案

Step 1 所有物品先按高度排序，再按重量排序 这表示如果所有高度都是唯一的，则按高度排序 如果高度相同，则按重量排序

步骤 2 找到包含增加高度和增加权重的最长序列为此，我们：

a) 从序列的开头开始 目前，max_sequence 为空

b) 如果下一件物品的身高和体重不大于上一件物品，我们将该物品标记为“不合适”</p>

c) 如果找到的序列的项数超过“最大序列”，则变为“最大序列”</p>

d) 之后从“不合适的项目”开始重复搜索，直到我们到达原始序列的末尾

我对其解决方案有一些疑问。

第一季度

我相信这个解决方案是错误的。

例如

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

显然，(6,7)是一个不合适的项目，但怎么样(7,8)？根据解决方案，它不是不合适的，因为它的 h 和 w 都比 大(6,7)，但是，它不能被考虑到序列中，因为(7,8)不适合(5,9)。

我对吗？

如果我是对的，解决方法是什么？

第二季度

我相信即使有上述解决方案的修复，解决方案的风格至少会导致O(n^2)，因为它需要一次又一次地迭代，根据步骤 2-d。

那么是否有可能有一个 O(nlogn) 解决方案？

4

5 回答 5

1

你可以用动态规划来解决这个问题。

按身高对剧团进行排序。为简单起见，假设所有高度 h_i 和权重 w_j 都是不同的。因此 h_i 是一个递增序列。

我们计算一个序列 T_i，其中 T_i 是一个塔，其中人 i 位于最大尺寸的顶部。T_1 就是 {1}。我们可以从之前的 T_j 推导出后续的 T_k——找到最大的塔 T_j，它可以承受 k 的重量（w_j < w_k）并将 k 站在上面。

剧团中最大的可能塔是 T_i 中最大的。

该算法需要 O(n**2) 时间，其中 n 是剧团的基数。

于 2013-07-22T23:50:52.163 回答
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

例如

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

显然，(6,7) 是一个不合适的项目，但是 (7,8) 呢？

回答您的问题 - 算法首先从 3,2 开始运行，并获得序列 (3,2) (5,9) 标记 (6,7) 和 (7,8) 不合适。

然后它再次从 (6,7) （第一个不合适的）开始并得到 (6,7) (7,8)，这使得答案为 2。由于没有更多“不合适”的项目，序列以最大值终止长度 2。

于 2014-05-13T17:15:06.983 回答
0

在首先按高度和重量对数组进行排序之后，我的代码检查如果我们抓取数组中剩余的任何元组（以及可能的后续元组），最大的塔将是什么。为了避免重新计算子问题，solution_a用于存储从尾部开始的最佳最大长度input_array。

这beginning_index是我们可以考虑从中抓取元素的索引（我们可以从中考虑可以在人类堆栈中低于的人的索引），并且beginning_tuple是指堆栈中较高的元素/人。

该解决方案在 O(nlogn) 中运行以进行排序。使用的空间是 O(n) 用于solution_a数组和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 回答
0

这是用代码完全解决问题的另一种方法；

算法

  1. 先按高度排序，再按宽度排序

排序数组：[(56, 90), (60, 95), (65, 100), (68, 110), (70, 150), (75, 190)]

  1. 寻找权重的最长递增子序列的长度

为什么最长的权重子序列是答案？人是按身高递增排序的，所以当我们找到体重增加的人的子序列时，这些选定的人将满足我们的要求，因为他们的身高和体重都是递增的顺序，因此可以形成一个人塔。

例如：[(56, 90) (60,95) (65,100) (68,110) (70,150) (75,190)]

高效实施

在附加的实现中，我们维护了一个不断增加的数字和用途的列表，该列表bisect_left在后台使用二分搜索实现，以找到插入的正确索引。

请注意; 方法生成的序列longest_increasing_sequence可能不是实际最长的子序列，但是，它的长度- 肯定是最长递增子序列的长度。
请参阅最长递增子序列高效算法了解更多详细信息。

根据需要，总体时间复杂度为 O(n log(n))。

代码

from bisect import bisect_left

def human_tower(height, weight):
    def longest_increasing_sequence(A, get_property):
        lis = []
        for i in range(len(A)):
            x = get_property(A[i])
            i = bisect_left(lis, x)
            if i == len(lis):
                lis.append(x)
            else:
                lis[i] = x
        return len(lis)
    # Edge case, no people
    if 0 == len(height):
        return 0
    # Creating array of heights and widths
    people = [(h, w) for h, w in zip(height, weight)]
    # Sorting array first by height and then by width
    people.sort()
    # Returning length longest increasing sequence
    return longest_increasing_sequence(people, lambda t : t[1])

assert 6 == human_tower([65,70,56,75,60,68], [100,150,90,190,95,110])
于 2021-02-24T23:05:33.120 回答