iT邦幫忙

2021 iThome 鐵人賽

DAY 15
0
Software Development

算法30天系列 第 15

Day. 15 Bulls and Cows

Leetcode #299. Bulls and Cows

這一題簡稱1A2B,是一款猜數字的遊戲,簡單介紹一下玩法!
電腦會出一組數字,簡稱secret。玩家要輸入一組同位數的數字,簡稱guess。
當玩家猜出secret就贏了,如果沒猜對會回傳提示。

ex1.
Input: secret = "1234", guess = "1240"
output: 2A1B

guess前面的12跟secret完全相同,我們就用2A表示,後面4的數值在secret裡面也有,但位置不一樣,用1B表示

ex2.
Input: secret = "1234", guess = "0000"
Output: "0A0B"

註: guess的長度跟secret相同


防雷
防雷
防雷


這一題可以用map來解~
先定義一個map,去記數字出現的次數
因為secret跟guess的長度是一樣,所以我們不用去管兩邊長度問題。
跑一個迴圈只要兩邊位置跟數字都相同,a++
如果不相同,判斷secret的數值在map是否小於0,是的話b++,guess的數值在map是否大於0,是的話b++,最後secret的數值++,guess的數值--。

什麼意思?來看一下執行流程

ex: secret = "0011", guess = "1100"

當跑到index 2,第三個數值的時候,我們來看一下map的值。

* secret的數值在map裡面都加1 guess的值都減1
map: {
    0: 2
    1: -2
}

secret第三個數值是1
來map裡面找,發現是負值,證明guess之前的值有1,所以B+1。
最後把map[1]++,就剩下-1,並不會重複計算。

最後迴圈跑完,map剛好就會清0!
回傳: 0A4B

程式:

func getHint(secret string, guess string) string {
	book := map[byte]int{}
	var a, b int

	for i := 0; i < len(secret); i++ {
		sNum := secret[i]
		gNum := guess[i]
		if sNum == gNum {
			a++
			continue
		}

		if book[sNum] < 0 {
			b++
		}

		if book[gNum] > 0 {
			b++
		}

		book[sNum]++
		book[gNum]--
	}

	return fmt.Sprintf("%vA%vB", a, b)
}

明天講Graph~


上一篇
Day.14 Hash map II
下一篇
Day. 16 Graph
系列文
算法30天30

尚未有邦友留言

立即登入留言