2020-05-07 2e8119fe2db1ec7e0d264a8aa4051319 99+ 1 分钟 0.2 k 0次访问

leetcode-外观数列

一、题目

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：

1
11
21
1211
111221
1 被读作 “one 1” (“一个一”) , 即 11。
11 被读作 “two 1s” (“两个一”）, 即 21。
21 被读作 “one 2”, “one 1” （”一个二” , “一个一”) , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。

注意：整数序列中的每一项将表示为一个字符串。

示例 1:

输入: 1
输出: “1”
解释：这是一个基本样例。

示例 2:

输入: 4
输出: “1211”
解释：当 n = 3 时，序列是 “21”，其中我们有 “2” 和 “1” 两组，”2” 可以读作 “12”，也就是出现频次 = 1 而值 = 2；类似 “1” 可以读作 “11”。所以答案是 “12” 和 “11” 组合在一起，也就是 “1211”。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-and-say

二、思路

理论推导

数列的第n项中的结果是由其前一项第n-1项的表达式决定的，第n项中表达式中的数字序列应该是每两个作为一组描述组合a₁a₂，表示前一项中对应位置是a₁个a₂(数字是从右往左排列)。
由此，第6项读第5项111221，3个1，2个2，1个1，推导出第6项就是312211。

规律与结论

通过上述理论，总结出一些规律：

数列中每一项数字的个数一定是2的倍数，因为每一项都是对前一项的描述，而每一组描述都需要两个字符来完成，把数字中每一个数位上的数字看作字符，最终的总字符一定是偶数。
如果第n项数字序列是a₁a₂a₃…a_m共m个数字，其中不重复的有k个，(如第5项111221中数字一共有6个，不重复数字是1、2，k等于2），要表示前一项的k个不重复数字，后一项至少需要2k个字符。

由此得出的结论：

如果数列第n项是An=a₁a₂a₃a₄a₅a₆…a_n-1a_n，则可以知道前一项A_n-1是由a₂a₄a₆…a_n组成，因此a₂≠a₄，a₄≠a₆，以此类推，否则矛盾。例如111321131221中偶数位置数字分别是1、3、1、3、2、1，相邻的两个数字一定不相等，否则如果是111121131221，则前面四个数1111表示前一项对应的两个数字就是11，而又由描述组合的规则来看，要表示这两个数，下一项应该要用21来表示，而不是1111，所以就会矛盾，所以可知每一项的数字序列中，最多会连续出现相同的数字的数目是3个，不会有连续四个数字相同。
任何一项的数字序列中，只能由1、2、3三个字符中的若干个排列组成

三、代码实现

>folded main.go

// 递归解法
func countAndSay(n int) string {
	// 基础情况
	if n == 1 {
		return "1"
	}

	// 得到第n-1项的字符串
	pstr := countAndSay(n - 1)

	return say(pstr)
}

func say(prev string) string {
	if len(prev) == 0 {
		return ""
	}
	// 获取字符的重复个数
	n := getCharCount(prev)
	
	// 递归调用
	return strconv.Itoa(n) + string(prev[0]) + say(prev[n:])
}

func getCharCount(str string) int {
	count := 1
	ch := str[0]
	for i := 1; i < len(str); i++ {
		if str[i] == ch {
			count++
		} else {
			break
		}
	}
	return count
}