TapeEquilibrium - Python

Question

我正在通过 Codility 学习，并且正在做这课程。

所以我一开始想到的基本解决方案是：

#SOLUTION 1
def solution(A):

    diff = []
    for x in range(1,len(A)):
        first_half = sum(A[:x])
        second_half = sum(A[x:])
        diff.append(abs(first_half - second_half))
    return min(diff)

我在“正确”方面得分为 100%，但在“表现”方面得分为 0%。

所以我想也许我的问题是循环中的 diff.append 的问题。

然后我尝试使用这样的列表理解：

#SOLUTION 2
def solution(A):

    result = min((abs(sum(A[:x]) - sum(A[x:])) for x in range(1,len(A))))
    return result

我还尝试从循环中删除 min() 和 abs()，所以我尝试使用纯数学：

#SOLUTION 3
def solution(A):

result = [sum(A[:x]) - sum(A[x:]) if (sum(A[:x]) - sum(A[x:])) > 0 else sum(A[:x])*-1 - sum(A[x:])*-1 for x in range(1,len(A))]
return abs(min(result))

但是，我的绩效再次为 0%。所有解都有 O(N * N)。

所以我的问题可能是在循环内使用 sum()...提高代码性能的最佳方法是什么？

PS：这不是一个重复的问题，这个问题与关于 Codility 课程的其他问题相同，但我的解决方案不同。如果可能的话，我也更喜欢使用纯 Python 来实现该解决方案。

Answer 1

您可以尝试一下这种方法，看看性能是否有一些提升？ （只要测试一下，就都通过了出色）

当我们沿着列表移动时，这应该只是

O(n)

，每个循环都索引 头和尾。

def solution(A):
    heads = A[0]
    tails = sum(A[1:])

    diff = abs(heads - tails)

    for index in range(1, len(A)-1):
        heads += A[index]
        tails -= A[index]
        if abs(heads -tails) < diff:
            diff = abs(heads - tails)
    return diff 

Answer 2

经过 Codility 测试 - 任务得分、正确性和性能均为 100%：

from itertools import accumulate

def solution(A):
    x = list(accumulate(reversed(A)))[::-1]
    out = min(abs(a - b) for a, b in zip(accumulate(A), x[1:]))
    return out

Answer 3

使用 Python 的简单易用的解决方案，它给出了 100%

def solution(A):
    # Implement your solution here
    total = sum(A[0:len(A)])
    left_sum = A[0]
    right_sum = total-left_sum
    minium = abs(right_sum-left_sum)
    for i in range(1,len(A)-1):
        left_sum = left_sum + A[i]
        right_sum = total-left_sum
        if minium > abs(right_sum-left_sum):
            minium = abs(right_sum -left_sum)
    return(minium)