未分類

Bulls and Cows

Go, HashTable, LeetCode

Bulls and Cows

You are playing the following Bulls and Cows game with your friend: You write down a number and ask your friend to guess what the number is. Each time your friend makes a guess, you provide a hint that indicates how many digits in said guess match your secret number exactly in both digit and position (called “bulls”) and how many digits match the secret number but locate in the wrong position (called “cows”). Your friend will use successive guesses and hints to eventually derive the secret number.

For example:

1
2
Secret number:  "1807"
Friend's guess: "7810"

Hint: 1 bull and 3 cows. (The bull is 8, the cows are 0, 1 and 7.)
Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and B to indicate the cows. In the above example, your function should return “1A3B”.

Please note that both secret number and friend’s guess may contain duplicate digits, for example:

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

In this case, the 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow, and your function should return “1A1B”.
You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.

提示 解題應用
HashTable HashMap

Default:

1
2
3
func getHint(secret string, guess string) string {
}

解答思路:

Bulls and Cows其實就是俗稱的猜數字，以前上課無聊時常常在玩，規則如果不懂可以去看看維基百科對猜數字的解說，這邊就不再轉貼過來，總之就是一開始先遍歷一次被猜的數字，統計出各個數字共出現多少次(用HashMap紀錄)，接著才遍歷要猜的數字，如果從要猜的數字取出的位置、值與被猜的數字相符就將A+1，而如果只有值相符而位置不符則將B+1，並記得上述兩種情況都要將該數的統計次數-1，唯一要注意的是當出現A的情況(位置與值皆相符)卻發現該數的統計次數已經歸0了，這時就要將B-1(也就是將該數剩餘的次數讓給A優先)如下:

1
2
3
4
5
Secret: "1122"  "1"出現次數: 2, "2"出現次數: 2
Guess:  "1222"
Result: "ABA "  "1"剩餘次數: 1, "2"剩餘次數: 0
Result: "AXA "  "1"剩餘次數: 1, "2"剩餘次數: 1
Result: "AXAA"  "1"剩餘次數: 1, "2"剩餘次數: 0  3A0B

在理解了會碰上的狀況並處理之後，最後猜數字就算不限於4個數字可拉長至更多位數，其做法仍舊不變一樣能順利給出答案。

程式碼解說:

一開始初始化HashMap用來儲存各個數字分別出現的次數，接著遍歷被猜的數字並做統計，如果從要猜的數字取出的值存在於HashMap中且位置與被猜的數字相符就將A+1，不過如先前思路所提到該數萬一統計次數已經歸0了，此時就要將B-1再把該數剩餘的次數加回1(也就是將該數剩餘的次數讓給A優先)，而如果只有值存在於HashMap中(位置不符)且數剩餘的次數大於0就將B+1，記得上述情況都要將該數的統計次數-1，最後待A、B結果出來便分別將其轉為字串型別才向上做回傳

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var A int
var B int
hashMap := make(map[rune]int)
for _, v := range secret {
	hashMap[v]++
}
for i, v := range guess {
	count, exist := hashMap[v]
	if exist {
		if v == rune(secret[i]) {
			if count <= 0 {
				B--
				hashMap[v]++
			}
			A++
		} else if count > 0 {
			B++
		}
		hashMap[v]--
	}
}
return strconv.Itoa(A) + "A" + strconv.Itoa(B) + "B"

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func getHint(secret string, guess string) string {
	var A int
	var B int
	hashMap := make(map[rune]int)
	for _, v := range secret {
		hashMap[v]++
	}
	for i, v := range guess {
		count, exist := hashMap[v]
		if exist {
			if v == rune(secret[i]) {
				if count <= 0 {
					B--
					hashMap[v]++
				}
				A++
			} else if count > 0 {
				B++
			}
			hashMap[v]--
		}
	}
	return strconv.Itoa(A) + "A" + strconv.Itoa(B) + "B"
}

總結:

Bulls and Cows其實就是俗稱的猜數字，給一組被猜的數字與一組要猜的數字要回傳是?A?B，一開始先遍歷一次被猜的數字，統計出各個數字共出現多少次(用HashMap紀錄)，接著才遍歷要猜的數字，如果從要猜的數字取出的位置、值與被猜的數字相符就將A+1，而如果只有值相符而位置不符則將B+1，並記得上述兩種情況都要將該數的統計次數-1，唯一要注意的是當出現A的情況(位置與值皆相符)卻發現該數的統計次數已經歸0了，這時就要將B-1(也就是將該數剩餘的次數讓給A優先)，在理解了會碰上的狀況並處理之後，最後猜數字就算不限於4個數字可拉長至更多位數，其做法仍舊不變一樣能順利給出答案。

分享到