java - 确定二进制数的间隙长度

Question

我正在尝试做以下练习(在 Codility 上找到):

我采用的方法是使用指针。例如。 25 的二进制表示是 11001。我们从 i = 0、j = 1 和一个跟踪间隙长度的变量 gLength = 0 开始。

如果第 i 个索引为 1，则检查第 j 个索引。如果第 j 个索引为 0，则增加 gLength。如果第 j 个索引为 1，则检查 gLength 是否大于 0。如果是，则我们需要将此长度存储在 ArrayList 中，因为我们已到达间隙的末端。递增 i 和 j，然后重复。

这是代码中的方法:

public static int solution(int N) {
    String binaryStr = Integer.toBinaryString(N);
    // pointers
    int i = 0;
    int j = 1;
    // length of gap
    int gLength = 0;

    while (j < binaryStr.length() && i < j) {
        if (binaryStr.charAt(i) == 1) {
            if (binaryStr.charAt(j) == 0) {
                gLength++; // increment length of gap 
            } else if (binaryStr.charAt(j) == 1) {
                // if the digit at the j'th position is the end of a gap, add the gap size to list. 
                if (gLength > 0)
                    gapLengths.add(gLength);
                i++; // increment i pointer
            }
        } else {
            i++; // increment i pointer
        }
        j++; // increment j pointer
    }

    Collections.sort(gapLengths);
    // Line 45 (ERROR)
    int maxGap = gapLengths.get(gapLengths.size() - 1);
    return maxGap;
}

我收到以下错误:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at java.util.ArrayList.elementData(ArrayList.java:400)
at java.util.ArrayList.get(ArrayList.java:413)
at Codility.solution(Codility.java:45)
at Codility.main(Codility.java:15)

我已经在评论中第 45 行的位置做了标记。在进一步调查(使用调试器)之后，我发现我得到了错误，因为似乎没有长度被添加到 ArrayList。有人知道为什么吗？

我希望这很清楚，如果不清楚请告诉我。我不确定这个方法是否会像要求的那样在 O(log n) 时间内执行，但现在我只想让一些东西工作——然后我会考虑它的时间复杂度方面。

非常感谢您的帮助。

Answer 1

问题是 if (binaryStr.charAt(i) == 1)。您正在将 char 与 int 进行比较。

替换:

if (binaryStr.charAt(i) == 1)

和

if (binaryStr.charAt(j) == 0)

与:

if (binaryStr.charAt(i) == '1')

和

if (binaryStr.charAt(j) == '0')

编辑:(正如 Andy 所指出的)

在执行 int maxGap = gapLengths.get(gapLengths.size() - 1); 之前，您需要检查 if gapLengths.size() > 0 以使确保您在 ArrayList 中至少有 1 个元素。