Foo Bar -在未知边缘情况下失败的电源饥饿挑战测试用例

Question

挑战是找到给定数组的子集的最大乘积。问题是：

编写一个函数解决方案(Xs)，它接受表示数组中每个面板的功率输出级别的整数列表，并返回这些数字的一些非空子集的最大乘积。例如，如果数组包含功率输出级别为2，-3，1，0，-5的面板，则最大乘积将取子集: xs0 = 2，xs1 = -3，xs4. = -5，给出乘积2*(-3)*(-5) = 30。因此，解决方案(2，-3，1，0，-5)将是"30“。每个太阳能电池板至少有一个，但不超过50个电池板，每个电池板的绝对值不超过1000 (一些电池板的故障严重到耗尽能量，但你知道太阳能电池板的波稳定器有一个诀窍，它可以让你把两个负输出板组合起来，产生其功率值倍数的正输出)。

我的代码基本上删除了列表中的所有0's，然后迭代数组中的所有剩余整数，并将每个整数放在各自的数组中(正数或负数)。我用负数对数组进行排序，然后检查它的长度；如果它是奇数，则删除最后一个元素(自排序以来，它始终是最接近0的元素)。最后，我将这两个数组中的每个数字相乘，并返回结果(我们需要将其作为字符串返回)。

def solution(xs):
    negatives = []
    positives = []
    product = 1

    xs = filter(lambda a: a != 0, xs)

    if not xs:
        return '0'

    for num in xs:
        if num > 0:
            positives.append(num)
        elif num < 0:
            negatives.append(num)

    if not positives and len(negatives) == 1:
        return '0'

    negatives.sort()

    if negatives:
        if len(negatives) % 2 != 0:
            negatives.pop()

    for x in positives + negatives:
        product *= x

    return str(product)

我已经搜索了为什么我的逻辑失败了第四个测试用例，我读过，如果数组中只有一个负数，你应该返回0，但我也看到你应该返回负值。但是，在编写代码中检查这种可能性的部分之前，第五个测试用例也失败了。所以在这种情况下，您需要返回0。

这是我的代码，打开测试用例和我添加的一些测试用例。

显然，我的代码失败了，但我根本找不到。救命求你了？

Answer 1

你的密码太多了。

首先，过滤掉零：

xs = filter(lambda a: a != 0, xs)

然后，将积极因素过滤到一个列表中，将负面信息过滤到另一个列表中：

for num in xs:
    if num > 0:
        positives.append(num)
    elif num < 0:
        negatives.append(num)

那么，为什么要费心第一次过滤呢？在这个循环中，零不会进入任何一个列表；它们自然会被过滤掉。

您不必要地对negatives数组进行排序。只有当它包含奇数个元素时，才需要这样做。并且您不需要通过检查它是否包含任何元素来保护它是否包含奇数元素的测试。

没有正值和1负值似乎是一个奇怪的特例。如果让代码超过这一点，那么单个奇数就会从负数组中弹出，不留下正值和负值，这似乎不是那么“特殊”的特例。

简化代码：

def solution(xs):
    negatives = [num for num in xs if num < 0]
    positives = [num for num in xs if num > 0]

    if len(negatives) % 2 != 0:
        negatives.sort()
        negatives.pop()

    if positives or negatives:
        product = 1
        for x in positives + negatives:
            product *= x

        return str(product)

    return '0'

这应该与您的原始代码相同(完成时不传递一些边缘情况)，但是应该稍微快一些。

您真的需要对negatives数组进行排序吗？这是一个O(N \log N)操作。您只需要从数组中删除最小的震级数，并找到并删除可以在O(N)时间内完成的值。

边缘案例

[-4]的非空子集的最大乘积是多少？

我已经读过，如果数组中只有一个负数，您应该返回0，但我也看到应该返回负值。

在这种情况下返回零似乎不合理，因为唯一的非空子集是[-4]，最大乘积是-4。

但是[-4, 0]呢？0 > -4和-4 * 0 > -4都是，因此最大的产品不再是-4。

修改留给学生的代码。