HackerRank循环二进制字符串题目遇运行时错误，已过4用例求助

嘿，我帮你分析下你遇到的问题——你在HackerRank的循环二进制字符串问题上碰到的运行时错误，主要是两个关键坑导致的，而且你的算法效率也有优化空间，咱们一步步拆解解决：

问题出在哪？ #

看你的代码，两个核心问题直接引发了运行时错误：

1. 整数溢出：你用Integer.parseInt(rightrotate(s, i), 2)把旋转后的二进制字符串转成整数，但HackerRank的测试用例肯定包含长度超过31位的字符串。Integer的范围是-2^31到2^31-1，超过这个长度的二进制数转成Integer会直接抛出NumberFormatException，这就是大部分测试用例失败的原因。
2. 浮点数精度误差：你用Math.pow(2, j)计算2的幂，返回的是double类型。当j超过53时，double没法精确表示所有整数，会导致arr[i] % Math.pow(2,j)的结果完全错误；而且整数和浮点数做取模操作本身就容易有精度问题。
   另外，你的双层循环时间复杂度是O(n²)，如果测试用例的字符串很长（比如1e5长度），还会触发超时问题。

其实咱们可以换个更聪明的思路：一个数能被2^j整除，本质就是它的二进制表示末尾有j个连续的0。根本不需要把二进制字符串转成整数，直接统计每个循环移位后的字符串末尾有多少个连续0，取最大值就行！

修正方案 #

核心思路 #

• 先判断字符串是不是全0：如果是，直接返回字符串长度，因为全0的数可以被2^n整除。
• 把原字符串拼接成s + s：这样所有循环移位后的字符串，都是这个拼接字符串里长度为n的子串，省去了反复旋转字符串的麻烦。
• 遍历每个可能的移位对应的子串，统计其末尾连续0的数量，记录最大值。

基础版修正代码 #

public static int maximumPower(String s) {
    int n = s.length();
    
    // 处理全0的特殊情况
    boolean allZeros = true;
    for (char c : s.toCharArray()) {
        if (c != '0') {
            allZeros = false;
            break;
        }
    }
    if (allZeros) {
        return n;
    }
    
    // 拼接字符串，包含所有循环移位的可能
    String doubled = s + s;
    int maxZeros = 0;
    
    for (int i = 0; i < n; i++) {
        int currentZeros = 0;
        // 从当前子串的末尾往前数连续的0
        for (int j = i + n - 1; j >= i; j--) {
            if (doubled.charAt(j) == '0') {
                currentZeros++;
            } else {
                break;
            }
        }
        if (currentZeros > maxZeros) {
            maxZeros = currentZeros;
        }
    }
    
    return maxZeros;
}

// 你的旋转方法可以保留，但现在用不到了
public static String leftrotate(String str, int d) {
    return str.substring(d) + str.substring(0, d);
}

public static String rightrotate(String str, int d) {
    return leftrotate(str, str.length() - d);
}

进阶优化（应对超大输入） #

上面的代码时间复杂度还是O(n²)，如果遇到非常长的字符串（比如10万字符）会超时。我们可以预处理一个后缀连续0数组，把时间复杂度降到O(n)：

public static int maximumPower(String s) {
    int n = s.length();
    
    // 检查全0情况
    boolean allZeros = true;
    for (char c : s.toCharArray()) {
        if (c != '0') {
            allZeros = false;
            break;
        }
    }
    if (allZeros) {
        return n;
    }
    
    String doubled = s + s;
    int[] suffixZeros = new int[2 * n];
    
    // 从后往前计算每个位置开始的连续0数量
    suffixZeros[2 * n - 1] = doubled.charAt(2 * n - 1) == '0' ? 1 : 0;
    for (int i = 2 * n - 2; i >= 0; i--) {
        if (doubled.charAt(i) == '0') {
            suffixZeros[i] = suffixZeros[i + 1] + 1;
        } else {
            suffixZeros[i] = 0;
        }
    }
    
    int maxZeros = 0;
    for (int i = 0; i < n; i++) {
        // 当前子串的末尾是i+n-1，最多取n个0（子串长度限制）
        int current = Math.min(suffixZeros[i + n - 1], n);
        if (current > maxZeros) {
            maxZeros = current;
        }
    }
    
    return maxZeros;
}

为什么这个方法管用？ #

• 拼接s+s后，任何循环移位的字符串都是其中长度为n的子串，比如右移k位的字符串对应doubled.substring(n - k, 2n - k)，省去了每次旋转字符串的操作。
• 统计子串末尾的连续0数量，就是这个移位后的二进制数能被2^j整除的最大j值，完全符合题目的要求。
• 预处理后缀数组后，每个位置的连续0数量可以O(1)获取，整体效率大幅提升，能轻松应对超大输入的测试用例。

内容的提问来源于stack exchange，提问作者Nalin Nishant