java - leetcode中bulls和cows算法详解

Question

算法在这里:https://discuss.leetcode.com/topic/28463/one-pass-java-solution .

public static String getHint(String secret, String guess) {
        int bulls = 0;
        int cows = 0;
        int[] numbers = new int[10];
        for (int i = 0; i<secret.length(); i++) {
            int s = Character.getNumericValue(secret.charAt(i));
            int g = Character.getNumericValue(guess.charAt(i));
            if (s == g) bulls++;
            else {
                if (numbers[s] < 0){
                    cows++;
                }
                if (numbers[g] > 0){
                    cows++;
                }
                numbers[s] ++;
                numbers[g] --;
            }
        }
        return bulls + "A" + cows + "B";
    }

但是这部分怎么理解:

numbers[s] ++;
numbers[g] --;

为什么它用负数来计算猜测的次数，用正数来计算 secret 。

Answer 1

numbers 数组跟踪两个数组中出现的不匹配 数字。 numbers 数组中的每个条目最初都是 0，表示该数字在两个数组中都没有出现过。正项表示该数字在 secret 数组中出现的次数多于在 guess 数组中出现的次数。负数表示该数字在 guess 数组中出现的次数多于在 secret 数组中出现的次数。

因此，当算法在 secret 数组中看到一个数字时，它会增加 numbers 数组中的相应条目。如果该条目在递增之前恰好为负数，则意味着该数字已经出现在 guess 数组中，因此 cows 计数会增加。

同样，当算法在 guess 数组中看到一个数字时，它会减少 numbers 数组中的相应条目。如果该条目在递减之前恰好为正，则意味着该数字已经出现在 secret 数组中，因此 cows 计数会增加。