我一直在练习一些 java 面试编码问题,我在下面遇到了这个问题。
You are given an integer array with N elements: d[0], d[1], ... d[N - 1]. You can perform AT MOST one move on the array: choose any two integers [L, R], and flip all the elements between (and including) the L-th and R-th bits. L and R represent the left-most and right-most index of the bits marking the boundaries of the segment which you have decided to flip.
What is the maximum number of '1'-bits (indicated by S) which you can obtain in the final bit-string?
'Flipping' a bit means, that a 0 is transformed to a 1 and a 1 is transformed to a 0 (0->1,1->0). Input Format An integer N Next line contains the N bits, separated by spaces: d[0] d[1] ... d[N - 1]
在下面的部分中,问题是用一个例子来解释的,我无法理解这个例子的结果。这里的问题是我应该先理解问题,然后再尝试解决问题。
Solution given:
Output: S
Constraints: 1 <= N <= 100000 d[i] can only be 0 or 1 0 <= L <= R < n
Sample Input: 8 1 0 0 1 0 0 1 0
Sample Output: 6
Explanation:
We can get a maximum of 6 ones in the given binary array by performing either of the following operations: Flip [1, 5] ==> 1 1 1 0 1 1 1 0
我不明白示例输出是 6 以及我们如何在给定的二进制数组中获得最多 6 个。
有人可以帮助我理解。我知道它非常简单,但不知何故我不明白。
谢谢!
最佳答案
让我们从这里开始:
In the part below, the question is explained with an example and I am not able to understand the results of the example. The problem here is I should understand the question first and then I can try solving for the problem.
您正在尝试在连续范围内应用单个位移位操作,您的目标是最大化数组中 1 的数量。
查看大小为 8 的样本输入
1 0 0 1 0 0 1 0
我们注意到有 5 个 0。 super 总结我的思考过程,真正的问题是确定一个范围,位翻转将为您带来最大的积极变化,换句话说,“找到一个具有最多 0 和最少 1 的范围”
我们查看示例输入,发现位 0 是 1,因此我们已经排除了它。位 1 和位 2 为 0,这迫使我们将其置于我们的范围内。第 3 位为 1,但接下来的两位,第 4 位和第 5 位为零,这意味着包括第 3、4 和 5 位将具有净增益。查看第 6 位和第 7 位,它们“相互抵消”,这意味着包含或排除它们并不重要。
总结一下,我们的范围从第 1 位开始,到第 5 位结束(含)。
翻转后,我们剩下
1 1 1 0 1 1 1 0
或 6 个 1,这是示例输出
请随时留下任何进一步的问题。这种方法是一种“人类方法”,我们可以用如此小的输入大小来完成。在手动运行小样本后,编写算法来找到最佳范围需要更多步骤。
关于java - 二元数组,面试题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37444645/