给定一个大小为n的数组，包含0和1以及两次运算，找出使所有元素都为0的最小运算次数

Question

给定一个大小为n的数组，包含0和1以及两次运算，找出使所有元素都为0的最小运算次数。

操作：

> < li>

如果第(I ^ 1)个元素为1，并且从第(I ^ 2)个到所有连续元素为0或不存在(如果I ^ 2 = n)，则翻转第I个元素。(0

例如，上述操作适用于:

在这个元素上

|

V   

1100年

或

在这个元素上

  |

  V   

1011

n

例如，输入： 1，0，0，0

产量:15

解释：

1000 -

Answer 1

在除全为< code>0的数组之外的任何数组上，只有两种操作是可能的。翻转第n个元素，或者翻转数组中最后一个< code>1之前的元素。< br >我们不需要考虑仅第一个元素为< code>1的边缘情况，因为我们可以在数组的开头添加任意数量的零，这不会改变结果，即< code>[1，0，0，0]和< code>[0，1，0，0，0]需要相同数量的最小操作才能全部变为< code > 0。< br >这意味着在< code>0的每个序列上< br >这些观察的结果是，我们实际上有一个非常类似于二进制的数字系统，每个操作都可以看作是将一个数递增或递减1，这意味着对于每个< code>0和< code>1序列，都有一个等价的二进制数和十进制数，即该数与0之间的步数。< br >我已经找到了这个系统和二进制之间的关系，它是这样的:< br >如果我们从头到尾迭代数组，并翻转< code>1之后的每个元素，我们将得到等价的二进制。这个操作需要就地完成，这意味着我们在迭代时改变数组本身，并且每次迭代的结果都会影响下一次迭代。我没有证明为什么这是正确的，也许有人可以提供证明。

尽管如此，算法本身很简单。这是用python编写的：

a = [1, 0, 0, 0]

# convert to equivalent binary
for i in range(1, len(a)):
    a[i] = int(not a[i]) if a[i-1] == 1 else a[i]

# convert to decimal
bin_str = ''.join(map(str, a))
print(int(bin_str, 2))