解读Leetcode题目之"Count and Say"

Leetcode算法题目第38题《Count and Say》(又名《Look and Say》)的难度为Easy,但是题目本身并不是太容易理解其表达的意思。甚至在讨论区(Discuss)有很多人质疑题目有严重问题,但也可以看到有人在讨论区发言说题目很清楚。很不幸的,我也属于看了几遍题目说”WTF”的人,不过最后我总算搞清楚了,解答也被接受了(Accepted)。 其实,Youtube上有一段视频,传奇数学家John H Conway首次遇到该题目时也很懵逼,所以不用怀疑自己的智商。

Look-and-Say Numbers(feat John Conway)

题目顾名思义,核心就是计数(Count)并说出来(Say), 搞清楚怎么计数以及怎么说就理解题目了。下面通过几个例子来说明:

1 : “1” –> 1为初始计数,直接Say出来,即为“1”2 : “11” –> 2需要从1开始计数,而1为”1”:有1个”1”(计数为1,即“11”) 3 : “21” –> 3需要从2开始计数,而2为”11”:有2个”1”(计数为2, 即“21”) 4 : “1211” –> 4需要从3开始计数,而3为”21”:有1个”2”(计数为1, 即“21”),加1个”1”(计数为1, 即“11”), 合并结果为“1211”5: “111221” –> 5需要从4开始计数,而4为”1211”:有1个”1”(计数为1, 即“11”),加1个”2”(计数为1, 即“12”), 加2个”1”(计数为2,即“21”),合并结果为“111221”

附上我的答案:

func countAndSay(n int) string {
	var say string
	for i := 1; i <= n; i++ {
		if i == 1 {
			say = "1"
		} else {
			var rs string
			j := 0
			k := 0
			for {
				v := say[j]
				for k = j + 1; k < len(say); k++ {
					if say[k] != v {
						break
					}
				}
				s := fmt.Sprintf("%d%s", k-j, string(v))
				rs += s
				j = k
				if j >= len(say) {
					break
				}
			}
			say = rs
		}
	}
	return say
}