将数组拆分为大致相等的块

问题描述

当每个块的总和近似相等时，如何将数组拆分为两个块?

How split array into two chunks, when sum of every chunk is approximately equal?

>>> foo([10, 1, 1, 1])
[[10], [1, 1, 1]]
>>> foo([2, 5, 9, 5, 1, 1])
[[2, 5], [9, 5, 1, 1]]
>>> foo([9, 5, 5, 8, 2, 2, 18, 8, 3, 9, 4])
[[9, 5, 5, 8, 2, 2], [18, 8, 3, 9, 4]]
>>> foo([17, 15, 2, 18, 7, 20, 3, 20, 12, 7])
[[17, 15, 2, 18, 7], [20, 3, 20, 12, 7]]
>>> foo([19, 8, 9, 1, 14, 1, 16, 4, 15, 5])
[[19, 8, 9, 1], [14, 1, 16, 4, 15, 5]]

推荐答案

类似的事情:

def foo(lst):
    total_sum = sum(lst)
    i = 1
    while sum(lst[:i]) < total_sum / 2:  # iterate over the list slices until we hit the "middle"
        if sum(lst[:i+1]) >= total_sum / 2:  # also make sure that we won't go further
            break

        i += 1

    return [lst[:i], lst[i:]]

测试:

[[10], [1, 1, 1]]                         # 10 + 3
[[2, 5], [9, 5, 1, 1]]                    # 7 + 16
[[9, 5, 5, 8, 2, 2], [18, 8, 3, 9, 4]]    # 31 + 42
[[17, 15, 2, 18, 7], [20, 3, 20, 12, 7]]  # 59 + 62
[[19, 8, 9, 1], [14, 1, 16, 4, 15, 5]]    # 37 + 55

这篇关于将数组拆分为大致相等的块的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！