奇偶校验 - 递归 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

我设法迭代地编写了它，但是我的递归超出了边界：

  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.

不使用 static 变量，我建议如下：

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

解释：

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

这正是您需要的逻辑：

如果第一个字符是 '1' 并且 String 的其余字符的奇偶校验为 1（即奇数个 '1'），则整个 String 的奇偶校验为 0。

如果第一个字符是 '1' 并且 String 的结果的奇偶校验为 0（即偶数个 '1's, the wholeString` 的奇偶校验为 1.

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

奇偶校验 - 递归 java

Parity - Recursion java

java

recursion

parity