java - 奇偶校验 - 递归java

Question

我遇到奇偶校验器问题:二进制字符串是仅包含“0”和“1”字符的字符串。二进制的奇偶校验字符串定义如下。如果字符“1”在此字符串中出现的次数为偶数时，奇偶校验为0；如果是奇数，则奇偶校验为 1。例如“101”的奇偶校验为 0，则“10110”的奇偶校验为1，“001001101”的奇偶校验为0。编写一个函数，使用签名

public static int parity(String binaryStr)
//no changes are allowed & only use recursive solution, no loops allowed

我设法迭代地编写它，但是我的递归超出了 outOfboundries:

  public static int parity(String binaryStr) {
    int counter = 0;
    for (int i = 0; i < binaryStr.length () ; i++) {
        if (binaryStr.charAt (i) == 49) {
            counter++;
        }
    }
    if ( counter % 2 == 0 ) {
        return 0;
    }
    else {
        return 1;
    }
}

递归:

private static int index = 0;
private static int ans = 0;

private static int parity(String binaryStr) {
    if ( index == binaryStr.length ()-1 ) {
        if ( ans % 2 == 0 ) {
            return 0;
        }
        else {
            return 1;
        }
    }
    else if ( binaryStr.charAt (index) == '1' ) {
        ans++;
        return parity (binaryStr.substring (index++));
    }
    return  parity (binaryStr.substring (index++));
}

请帮我改正

Answer 1

代码的主要问题是将 binaryStr.substring (index++) 传递给递归调用，该调用传递原始 String 而不是子字符串。因此你会得到无限递归。您可以使用++index。

我建议不要使用静态变量:

private static int parity(String binaryStr) {
    if (binaryStr.length() == 0) {
        return 0;
    } else {
        return ((binaryStr.charAt(0) == '0') ? 0 : 1) ^ parity(binaryStr.substring(1));
    }
}

说明:

按位异或(^)的两个操作数相等，则返回0。如果一个操作数为0，另一个操作数为1，则返回1。

这正是您需要的逻辑:

如果第一个字符是“1”，并且 String 的其余部分具有奇偶校验 1(即奇数个“1”)，则整个 String 的奇偶校验为0.

如果第一个字符是“1”并且String的结果具有奇偶校验0(即偶数个“1”，则整个String`的奇偶校验为 1。

如果第一个字符为“0”，则整个String 的奇偶校验与String 其余部分的奇偶校验相同。