Bulls and Cows

• Easy
• tag: Strings
• Similar: Word Pattern, Isomorphic Strings

题目就是secret和guess2个string, 位置对/字符也对的叫bull, 字符对/位置不对的叫cow.

思路

• 既然是2个String, 常用的体型就是Strstr/wordPattern/DP.
• 我先找了题目给的例子找一下规律. 感觉想法很简单, one-pass. 当前char不同的话, 就在对应的arr里面加1, 同时guess里面的char对应的位置也加1. 如果当前char相同, 直接Bull counter++. 等到loop结束, 就过一遍arr, cow就是arr里面每一个字符在secret里的个数, 以及guess里面的个数的较小值.

idea 1

• 由于要记录每一个char在secret/guest各自出现的次数, 从而统计结束后, 返回非0的较小值.
• 代码如下:

public String getHintTTT(String secret, String guess) {
    if (secret == null || guess == null || secret.length() == 0 || guess.length() == 0)  return null;
    int[][] Cow = new int[10][2];
    int[] Bull = new int[10];
    for (int i = 0; i < secret.length(); ++i) {
      char cs = secret.charAt(i);
      char cg = guess.charAt(i);
      if (cs == cg) {
        Bull[cs-'0']++;
      }
      else {
        Cow[cs-'0'][0]++;
        Cow[cg-'0'][1]++;
      }
    }
    int cntB = 0, cntC = 0;
    for (int b : Bull) {
      cntB += b;
    }
    for (int[] c : Cow) {
      if (c[0]> 0) {
        //int cnt = c[0] - c[1] >= 0 ? c[1] : c[0];
        cntC += Math.min(c[0], c[1]);
      }
    }

    StringBuilder sb = new StringBuilder();
    sb.append(cntB+"A"+cntC+"B");
    return sb.toString();
  }

idea 2: 什么叫做消元法? 牛

• 看了discuss之后才发现上面的想法太弱了.
• 为什么要记录统计值? 这里需要的是累加mismatch的char的个数就行了. 例如'a'在secret里面有2个, guess里面有5个, 那么返回2. 反之, 也是2.
• 霸气的方法, 只用1D array即可.
• 代码如下:

public String getHint(String secret, String guess) {
    int[] count = new int[10];
    int bulls = 0, cows = 0;
    for (int i = 0; i < secret.length(); ++i) {
      int s = secret.charAt(i) - '0';
      int g = guess.charAt(i) - '0';
      if (s == g) {
        bulls++;
      }
      else {
        if (count[s] < 0) {  // 若之前已经在guess里面有过至少1个s, 那么就要加一个cow
          cows++;           // 这里要好好理解. 为什么<0就加一次.
        }
        if (count[g] > 0) {  // 若之前已经在secret里面有过至少1个g, 那么就要加一个cow
          cows++;
        }
        count[s]++;  // +1表示secret里面出现过该char
        count[g]--;  // -1表示guess里面出现了一次这个char
      }
    }
    return bulls+"A"+cows+"B";
  }