二元数组，面试题

Question

我一直在练习一些 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 个。

有人可以帮助我理解。我知道它很简单，但不知何故我不明白。

谢谢！

Answer 1

让我们从这里开始：

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。总结一下我的思考过程，真正的问题是确定一个范围，让位翻转会给你带来最大的积极变化，换句话说，"Find a range that has the most 0's and the least 1's"

我们查看示例输入，发现位 0 是 1，因此我们已经排除了它。位 1 和位 2 为 0，这迫使我们将其置于我们的范围内。第 3 位为 1，但接下来的两位，第 4 位和第 5 位为零，这意味着包括第 3、4 和 5 位将具有净增益。查看第 6 位和第 7 位，它们 "cancel each other out"，意味着包括或排除它们并不重要。

总结一下，我们的范围从第 1 位开始，到第 5 位结束（含）。

翻转之后，我们剩下

1 1 1 0 1 1 1 0

或6个1，这是样本输出

如有任何其他问题，请随时留下。这种方法是 "human approach"，我们可以用这么小的输入大小来做。运行手动通过小样本量编写算法以找到最佳范围需要更多步骤。

Answer 2

暂时忘掉数组，你有二进制数：

1 0 0 1 0 0 1 0

你的任务是找到左右索引，比如：

1 0 0 1 0 0 1 0
  ^       ^
  left    right

当你反转 left/right 之间的每一位并计算最终 number/array 中的个数 (1) 时，找到 left/right 个索引的最大数量 1 的组合

在这个特定的例子中，如果我们取左 1，右 5，最终数组将是

0 1 2 3 4 5 6 7 (indexes)
1 0 0 1 0 0 1 0 (original array)
1 1 1 0 1 1 1 0 (I've inverted, 1st, 2nd, 3rd, 4th, 5th)

现在，我们如何计算它。第一种方法通常是蛮力，尝试所有可能的 left/right 组合并找到最大值：

public static void main(final String s[]) {
    final int[] d = {1, 0, 0, 1, 0, 0, 1, 0};
    int max = getOnes(d);
    for (int left = 0; left < (d.length - 1); left++) {
        for (int right = (left + 1); right < d.length; right++) {
            invert(d, left, right); // flip bits
            max = Math.max(max, getOnes(d));
            invert(d, left, right); // reverse flipping
        }
    }
    System.out.println(max);
}

static int getOnes(final int[] d) {
    int cnt = 0;
    for (final int i : d) cnt += i;
    return cnt;
}

static void invert(final int[] d, final int left, final int right) {
    for (int i = left; i <= right; i++) d[i] = (1 - d[i]);
}

下一步是优化这个解决方案，这里有几个提示：

左索引为 0 或序列中第一个零的索引
右索引是数组长度为 1 或序列的最后一个零
您不需要实际翻转数组中的位来计算 1 的数量，只需计算 0 即可
这个数字不需要从头重新计算，调整即可

二元数组，面试题

binary array, interview questions

java

arrays

algorithm

binary-data