2022/06/24

Leetcode Note: Go - Binary Watch

Binary Watch - LeetCode
https://leetcode.com/problems/binary-watch/

  • Go 言語で取り組んだメモ

所感

  • 受け取った数値の個数を使って表現可能な時刻文字列の配列を return する
  • 以下の数値のみ有効という指定
    • H: 8, 4, 2, 1
    • M: 32, 16, 8, 4, 2, 1
  • フォーマットに注意
    • OK: 1:00, 10:02
    • NG: 01:00, 10:2
  • 例: turnedOn = 1 なら …
    • return ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
    • H or M の値を 1つ 使うことで表現可能な時刻リスト
  • 例: turnedOn = 9 なら …
    • return []
    • 9 という数値

回答

golang backtracking - LeetCode Discuss
https://leetcode.com/problems/binary-watch/discuss/1594418/golang-backtracking

var ans []string
var arr = []int{8, 4, 2, 1, 32, 16, 8, 4, 2, 1}

func readBinaryWatch(turnedOn int) []string {
	ans = []string{}
	backtrack(turnedOn, 0, 0, 0)
	return ans
}

func backtrack(turnedOn int, H int, M int, k int) {

	if turnedOn == 0 {
		Hs, Ms := strconv.Itoa(H), strconv.Itoa(M)
		if M < 10 {
			Ms = "0" + Ms
		}
		ans = append(ans, Hs+":"+Ms)
		return
	}

	for i := k; i < 10; i++ {
		h, m := H, M

		if i < 4 {
			h += arr[i]
		} else {
			m += arr[i]
		}

		if h < 12 && m < 60 {
			backtrack(turnedOn-1, h, m, i+1)
		}

	}
}

再帰

See Also