[关闭]
@NewWorld 2016-04-10T11:31:55.000000Z 字数 4058 阅读 1697

LeetCode: Bulls and Cows

LeetCode

论文暂告一段落，闲着无聊到 LeetCode 刷刷题，蛤蛤蛤。

题目链接：Bulls and Cows

题目大意如下：

先给出一个数字串secret，再给出一个长度一样的猜测数字串guess。

对guess某个位置上的数字，若在secret串中的相同位置上存在相同的数字，则输出 1A，若有两个这种情况，则输出 2A；

当猜测数字串中除去完全匹配上位置的数字外，还有只猜中数字的情况，则猜中一个记为 1B，猜中两个记为 2B，secret中的数字不能被计数超过一次。

example 1 :
Secret number: "1807"
Friend's guess: "7810"
Output: 1A3B

example 2 :
Secret number: "1123"
Friend's guess: "0111"
Output: 1A1B



为了达到 excited 的效果，当然是挑 easy 做，第一版代码如下:

  1. // Version 汪
  2. public static String getHint1(String secret, String guess) {
  3.         Set<Integer> indexListA = new HashSet<>();
  4.         Set<Integer> indexListB = new HashSet<>();
  6.         int length = guess.length();
  8.         for (int i=0; i<length; i++) {
  9.             if ((secret.charAt(i)^guess.charAt(i)) == 0) {
  10.                 indexListA.add(i);
  11.             }
  12.         }
  14.         for (int i=0; i<length; i++) {
  15.             if (indexListA.contains(i)) {
  16.                 continue;
  17.             }
  18.             for (int j=0; j<length; j++) {
  19.                 if (indexListA.contains(j) || indexListB.contains(j)) {
  20.                     continue;
  21.                 }
  22.                 if ((secret.charAt(i)^guess.charAt(j)) == 0) {
  23.                     indexListB.add(j);
  24.                     break;
  25.                 }
  26.             }
  27.         }
  29.         return indexListA.size()+"A"+indexListB.size()+"B";
  30.     }

将运行过程分为了两部分，第一部分针对完全匹配的情况，第二部分针对只猜对数字的情况。提交以后运行效果惨不忍睹，与主流运行效果形成了强烈的反差（一开始可是用的 ArrayList）。进行改进，琢磨着去掉老是去 HashSet 中进行查询的行为，得到第二版：

  1. // Version 吐
  2. public static String getHint2(String secret, String guess) {
  3.         char[] secrets = secret.toCharArray();
  4.         char[] guesses = guess.toCharArray();
  6.         int numA = 0, numB = 0;
  7.         int length = guess.length();
  9.         for (int i=0; i<length; i++) {
  10.             if (secrets[i] == guesses[i]) {
  11.                 numA++;
  12.                 secrets[i] = 'a';
  13.                 guesses[i] = 'a';
  14.             }
  15.         }
  17.         for (int i=0; i<length; i++) {
  18.             if (secrets[i] == 'a') {
  19.                 continue;
  20.             }
  21.             for (int j=0; j<length; j++) {
  22.                 if (guesses[j] == 'a') {
  23.                     continue;
  24.                 }
  25.                 if (secrets[i] == guesses[j]) {
  26.                     numB++;
  27.                     secrets[i] = 'a';
  28.                     guesses[j] = 'a';
  29.                     break;
  30.                 }
  31.             }
  32.         }
  34.         return numA+"A"+numB+"B";
  35.     }

主要是将字符串转为了一个字符数组，在字符数组中动手脚，标记已经匹配过的数字。然而提交后运行效果还是不理想。接着改进，发现第一部分发现完全匹配后，完全可以将匹配上的的数字丢弃掉，得到第三版：

  1. // Version 3
  2. public static String getHint3(String secret, String guess) {
  3.         char[] secrets = secret.toCharArray();
  4.         char[] guesses = guess.toCharArray();
  6.         int numA = 0, numB = 0;
  7.         int length = guesses.length;
  9.         for (int i=0; i<length; i++) {
  10.             while (secrets[i] == guesses[i]) {
  11.                 numA++;
  12.                 if (i == length-1) {
  13.                     length--;
  14.                     break;
  15.                 }
  16.                 secrets[i] = secrets[--length];
  17.                 guesses[i] = guesses[length];
  18.             }
  19.         }
  21.         if (length == 0) {
  22.             return numA+"A0B";
  23.         }
  25.         for (int i=0; i<length; i++) {
  26.             for (int j=0; j<length; j++) {
  27.                 if (guesses[j] == 'a') {
  28.                     continue;
  29.                 }
  30.                 if (secrets[i] == guesses[j]) {
  31.                     numB++;
  32.                     secrets[i] = 'a';
  33.                     guesses[j] = 'a';
  34.                     break;
  35.                 }
  36.             }
  37.         }
  39.         return numA+"A"+numB+"B";
  40.     }

这样在完全匹配后，同时减少了 secret 串和 guess 串的长度，后面的查找次数被缩短了。突然发现，既然第一部分可以丢弃数字，第二部分也可以丢弃，得到第四版：

  1. // Version 4
  2. public static String getHint4(String secret, String guess) {
  3.         char[] secrets = secret.toCharArray();
  4.         char[] guesses = guess.toCharArray();
  6.         int numA = 0, numB = 0;
  7.         int length = guesses.length;
  9.         for (int i=0; i<length; i++) {
  10.             while (secrets[i] == guesses[i]) {
  11.                 numA++;
  12.                 if (i == length-1) {
  13.                     length--;
  14.                     break;
  15.                 }
  16.                 secrets[i] = secrets[--length];
  17.                 guesses[i] = guesses[length];
  18.             }
  19.         }
  21.         if (length == 0) {
  22.             return numA+"A0B";
  23.         }
  25.         int lengthS = length;
  26.         for (int i=0; i<length; i++) {
  27.             for (int j=0; j<lengthS; j++) {
  28.                 if (secrets[j] == guesses[i]) {
  29.                     numB++;
  30.                     lengthS--;
  31.                     if (lengthS == 0) {
  32.                         return numA+"A"+numB+"B";
  33.                     }
  34.                     secrets[j] = secrets[lengthS];
  35.                     break;
  36.                 }
  37.             }
  38.         }
  40.         return numA+"A"+numB+"B";
  41.     }

主要的改进就是在第二部分中丢弃 secret 串中已经匹配上的数字。这次提交后击败了30%左右的 javasubmissions，然而和第一仍然相差甚远。一定还有更好的方法，接着思索，发现在第二部分的时候已经不需要顾忌数字在串中的位置了，那么，叮！直接计算每个串中数字出现的次数，然后取较小就行。而且关键是数字只有 0-9，哈哈，那就好办了。

  1. // Versino 5
  2. public static String getHint5(String secret, String guess) {
  3.         char[] secrets = secret.toCharArray();
  4.         char[] guesses = guess.toCharArray();
  6.         int numA = 0, numB = 0;
  7.         int length = guesses.length;
  9.         for (int i=0; i<length; i++) {
  10.             while (secrets[i] == guesses[i]) {
  11.                 numA++;
  12.                 if (i == length-1) {
  13.                     length--;
  14.                     break;
  15.                 }
  16.                 secrets[i] = secrets[--length];
  17.                 guesses[i] = guesses[length];
  18.             }
  19.         }
  21.         if (length == 0) {
  22.             return numA+"A0B";
  23.         }
  25.         int[] countS = new int[10];
  26.         int[] countG = new int[10];
  27.         for (int i=0; i<length; i++) {
  28.             countS[secrets[i]-'0']++;
  29.             countG[guesses[i]-'0']++;
  30.         }
  31.         for (int i=0; i<countS.length; i++){
  32.             numB += countS[i] > countG[i] ? countG[i] : countS[i];
  33.         }
  35.         return numA+"A"+numB+"B";
  36.     }

麻蛋，猛然发现其实可以这样，不折腾...
运行效果与第五版相同。果然还是太 naive 啊。

  1. // Version 6
  2. public static String getHint6(String secret, String guess) {
  3.         char[] secrets = secret.toCharArray();
  4.         char[] guesses = guess.toCharArray();
  6.         int numA = 0, numB = 0;
  7.         int length = guesses.length;
  9.         for (int i = 0; i < length; i++) {
  10.             if (secrets[i] == guesses[i]) {
  11.                 numA++;
  12.             }
  13.         }
  15.         int[] countS = new int[10];
  16.         int[] countG = new int[10];
  17.         for (int i = 0; i < length; i++) {
  18.             countS[secrets[i] - '0']++;
  19.             countG[guesses[i] - '0']++;
  20.         }
  21.         for (int i = 0; i < countS.length; i++) {
  22.             numB += countS[i] > countG[i] ? countG[i] : countS[i];
  23.         }
  25.         return numA + "A" + (numB - numA) + "B";
  26.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注