LeetCode Note Java 00299：Bulls and Cows

發表於 更新於 分類於 ， ， ， 閱讀次數： Disqus： 文章字數： 440 所需閱讀時間 ≈ 2 分鐘

情境題：猜數字，輸入答案跟猜的數字，回傳幾 A (數字對位置也對) 幾 B (數字對位置錯)。

題目

Bulls and Cows Medium

You are playing the Bulls and Cows game with your friend.

You write down a secret number and ask your friend to guess what the number is. When your friend makes a guess, you provide a hint with the following info:

The number of “bulls”, which are digits in the guess that are in the correct position.
The number of “cows”, which are digits in the guess that are in your secret number but are located in the wrong position. Specifically, the non-bull digits in the guess that could be rearranged such that they become bulls.
Given the secret number secret and your friend’s guess guess, return the hint for your friend’s guess.

The hint should be formatted as “xAyB”, where x is the number of bulls and y is the number of cows. Note that both secret and guess may contain duplicate digits.

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String getHint(String secret, String guess) {
        int a = 0, b = 0; // A 的數目與 B 的數目
        HashMap<Character, Integer> map = new HashMap<>(); // 數字, 數量
        for (int i = 0; i < secret.length(); i++) {
          char valueS = secret.charAt(i), valueG = guess.charAt(i);
          if (valueS == valueG) { // 完全正確就不做額外計數
            a++;
          } else { // B 的計數不太好想，要考慮相同數字的數字差
            if (map.getOrDefault(valueS, 0) < 0) { // 表示這個數字在另一條出現過相同的了，而且保證是再次相遇，不會做多餘的計算
              b++;
            }
            if (map.getOrDefault(valueG, 0) > 0) {
              b++;
            }
            map.put(valueS, map.getOrDefault(valueS, 0) + 1); // 每個不完全相同的數字都要計數
            map.put(valueG, map.getOrDefault(valueG, 0) - 1); // 兩條計數的方向相反，這樣一加一減才能用大於或小於 0 當作分界
          }
        }
        return a + "A" + b + "B";
    }
}

檢討

在比較序列時，這種共用 map 或 array 來相反計數 (一加一減) 的方式滿常見的，但有時候我邏輯會跟不上，只能多做題目強迫做這種思考了。

參考資料

One pass Java solution