python - 使用python翻转数组中的位

Question

给定一个包含 N 个元素的整数数组:d[0], d[1], ... d[N - 1]。 您最多可以在数组上执行一次移动:选择任意两个整数 [L, R]，然后翻转第 L 和之间(包括在内)的所有元素R 第位。 L 和 R 代表标记您决定翻转的段边界的位的最左边和最右边的索引。

在最终的位串中，您可以获得的最大1 位数(用S 表示)是多少？

'翻转'有点意思是，0 转换为 1，1 转换为 0 (0->1，1->0)。

输入格式:一个整数N，下一行包含N位，用空格分隔:d[0] d[1] ... d [N - 1]

输出:S

约束:

1 <= N <= 100000,
d[i] can only be 0 or 1 ,
0 <= L <= R < n ,

示例输入:

8

1 0 0 1 0 0 1 0 

示例输出:6

解释:

我们可以通过执行以下任一操作在给定的二进制数组中获得最多 6 个:

Flip [1, 5] ==> 1 1 1 0 1 1 1 0

Answer 1

清理并制作 Pythonic

arr1 = [1, 0, 0, 1, 0, 0, 1, 0]
arr2 = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr3 = [0,0,0,1,1,0,1,0,1,1,0,0,1,1,1]


def maximum_ones(arr):
    """
    Returns max possible number of ones after flipping a span of bit array
    """  

    total_one = 0
    net = 0
    maximum = 0
    for bit in arr:
        if bit:
            total_one += 1
            net -= 1
        else:
            net += 1
        maximum = max(maximum, net)
        if net < 0:
            net = 0
    return total_one + maximum

print(maximum_ones(arr1))
print(maximum_ones(arr2))
print(maximum_ones(arr3))

输出:

6
14
11

如果我们想要 L 和 R 索引

这个不太确定。它可能会变得更清洁。

arr1 = [1, 0, 0, 1, 0, 0, 1, 0]
arr2_0 = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr2_1 = [1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr2_2 = [1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
arr3 = [0,0,0,1,1,0,1,0,1,1,0,0,1,1,1]


def maximum_ones(arr):
    """
    Returns max possible number of ones after flipping a span of bit array
    and the (L,R) indices (inclusive) of such a flip
    """ 
    total_one = 0
    net = 0
    maximum = 0
    L = R = 0
    started_flipping = False
    for i, bit in enumerate(arr):
        if bit:
            total_one += 1
            net -= 1
        else:
            net += 1
            if not started_flipping:
                started_flipping = True
                L = i
        if net > maximum:
            maximum = net
            R = i
        if net < 0:
            net = 0
            if i < R:
                L = i
    return (total_one + maximum, (L,R))

print(maximum_ones(arr1))
print(maximum_ones(arr2_0))
print(maximum_ones(arr2_1))
print(maximum_ones(arr2_2))
print(maximum_ones(arr3))

输出:

(6, (1, 5))
(14, (1, 16))
(14, (2, 16))
(14, (3, 16))
(11, (0, 2))

第一次迭代

如果您想了解思维过程的演变，这就是我原来的内容。在这里，我基本上是在音译我在纸上想到的内容。

本质上，我们遍历数组并开始翻转位(好吧，不是真的)，跟踪两个单独数组中的累积翻转零和累积翻转一，以及整数计数器中的总翻转数。如果给定索引处翻转的 1 和 0 之间的差异 - “净值” - 降至零以下，我们将在该索引处将累积计数“重置”为零(但没有别的)。在此过程中，我们还会跟踪已达到的最大净值以及出现该值的指数。因此，总数就是我们看到的总数 1，加上最大索引处的净值。

arr = [1, 0, 0, 1, 0, 0, 1, 0]
total_one = 0
one_flip =  [0 for _ in range(len(arr))]
zero_flip = [0 for _ in range(len(arr))]

# deal with first element of array
if arr[0]:
    total_one += 1
else:
    zero_flip[0] = 1

maximum = dict(index=0,value=0) #index, value
i = 1
# now deal with the rest
while i < len(arr):
    # if element is 1 we definitely increment total_one, else, we definitely flip
    if arr[i]:
        total_one += 1
        one_flip[i] = one_flip[i-1] + 1
        zero_flip[i] = zero_flip[i-1]
    else:
        zero_flip[i] = zero_flip[i-1] + 1
        one_flip[i] = one_flip[i-1]

    net = zero_flip[i] - one_flip[i]
    if net > 0:
        if maximum['value'] < net:
            maximum['value'] = net
            maximum['index'] = i
    else: # net == 0, we restart counting our "net"
        one_flip[i] = 0
        zero_flip[i] = 0

    i += 1

maximum_flipped = total_one - one_flip[maximum['index']] + zero_flip[maximum['index']]

结果:

print(total_one, -one_flip[maximum['index']], zero_flip[maximum['index']] )
print(maximum_flipped)
print('________________________________________________')
print(zero_flip, arr, one_flip, sep='\n')
print('maximum index', maximum['index'])

输出:

3 -1 4
6
________________________________________________
[0, 1, 2, 2, 3, 4, 4, 5]
[1, 0, 0, 1, 0, 0, 1, 0]
[0, 0, 0, 1, 1, 1, 2, 2]
maximum index 5

if

arr = [1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0 , 1]

6 -4 12
14
________________________________________________
[0, 1, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 10, 11, 12, 12]
[1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1]
[0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 5]
maximum index 16

最后，如果

arr = [0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]

8 0 3
11
________________________________________________
[1, 2, 3, 3, 3, 4, 4, 5, 5, 0, 1, 2, 2, 0, 0]
[0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1]
[0, 0, 0, 1, 2, 2, 3, 3, 4, 0, 0, 0, 1, 0, 0]
maximum index 2

太好了，现在把它拆开，伙计们!