0038._count_and_say.md

Links:

1. https://leetcode.com/problems/count-and-say/
2. https://leetcode-cn.com/problems/count-and-say/

Tags

1. 字符串

注意

题目的dislike比like多而且题目描述不清晰

Solution 1

看见1就说1个1，看见n个1就说n个1,看见1个2就说1个2。

itertools.groupby: Make an iterator that returns consecutive keys and groups from the iterable

可见，itertools.groupby帮我们把连续的、相同的数字都放在同一个列表中。这些列表的各自的长度就是数字的个数。也就是说groupby帮我们数了。

from itertools import groupby

class Solution:
    def countAndSay(self, n):
        result = '1'
        for i in range(1, n):
            result = ''.join([str(len(list(g))) + k for k, g in groupby(result)])
        return result

Solution2

Count and say分为两步：

1. count: 下一个人要count上一个人的数字中连续的数字的个数

2. say: 说出'个数 + 连续的数字'

3. 外循环： 3.1 要count多少轮？有多少个人就有多少轮。所以是n轮。第一轮默认为1, 从第二轮开始， 所以n-1轮。 3.2 初始化next_person, count， num。 num为prev_person[0]。 为内循环做准备

4. 内循环： 4.1 count and say 上一个人报的数。

class Solution:
    def countAndSay(self, n):
        prev_person = '1'

        for i in range(1, n):
            next_person = ''
            num = prev_person[0]
            count = 1

            for j in range(1, len(prev_person)):
                if prev_person[j] == num:
                    count += 1
                else:
                    next_person += str(count) + num
                    num = prev_person[j]
                    count = 1

            next_person += str(count) + num     
            prev_person = next_person    

        return prev_person

---

Go

func countAndSay(n int) string {
    if n == 1 {
        return "1"
    }

	prev := "1"

	for i := 1; i < n; i++ {
		next := ""
		num := string(prev[0])
		count := 1

		for j := 1; j < len(prev); j++ {
			if string(prev[j]) == num {
				count++
			} else {
				next += strconv.Itoa(count) + num
				num = string(prev[j])
				count = 1
			}
		}

		next += strconv.Itoa(count) + num
		prev = next
	}

	return string(prev)
}

---

Go，使用strings.Builder省点内存

func countAndSay(n int) string {
	if n == 1 {
		return "1"
	}

	prev := "1"
	var b strings.Builder

	for i := 1; i < n; i++ {
		next := ""
		num := string(prev[0])
		count := 1

		for j := 1; j < len(prev); j++ {
			if string(prev[j]) == num {
				count++
			} else {
				b.WriteString(strconv.Itoa(count) + num)
				next += b.String()
				b.Reset()
				num = string(prev[j])
				count = 1
			}
		}

		b.WriteString(strconv.Itoa(count) + num)
		next += b.String()
		b.Reset()

		prev = next
	}

	return string(prev)
}