LeetCode 38. 外观数列（易）

动态规划，正向循环，更新保留每次first_str，作为下一次迭代的字符串,遍历字符串数组，如果前一个和后一个相同则继续，记录相同的个数count + 1，不相同，则更新前面相同的临时temp以及重置count = 1。 最后一个数要分情况单独讨论更新temp，并初始化所有与之相关的参数。方便下一次迭代。

题目

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

1
2
3
4
5
6
1.     1       # 一个1
2.     11      # 描述第1行：一个1
3.     21      # 描述第2行：两个1
4.     1211    # 描述第3行：一个2和两个1
5.     111221  # 描述第4行：一个1和一个2和两个1
6.     312211  # 描述第5行：三个1和两个2和一个1
1 被读作  "one 1"  ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2",  "one 1" （"一个二" ,  "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。

题目的意思是对序列前一个数进行报数，数列第一项不是1吗，那第二项就报第一项的有1个1，输出11，然后第三项就在第二项的基础上报数，第二项是11，第三项不就是2个1么，然后输出21。

示例

示例 1:

1
2
输入: 1
输出: "1"

示例 2: 

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

考察知识点

字符串

核心思想

方案一、从第一个数开始推到，一直推导到第n个数字。

大佬题解

方案二、动态规划

动态规划，正向循环，更新保留每次first_str，作为下一次迭代的字符串，遍历字符串数组，如果前一个和后一个相同则继续，记录相同的个数count + 1，不相同，则更新前面相同的临时temp以及重置count = 1。
最后一个数要分情况单独讨论更新temp，并初始化所有与之相关的参数。方便下一次迭代。

❤ 注意：注意数组的越界问题。

大佬题解

Python版本

方案一的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
    def countAndSay(self, n: int) -> str:
        if n == 1:
            return "1"
        if n == 2:
            return "11"

        res = ["1", "1"]
        for _ in range(3, n+1):  # 遍历到第n+1，处理第n行的输出，得到的是第n行描述。
            num = 0  # 代表该数字重复次数
            new_res = []
            previous_char = ""
            current_char = ""
            # is_break = True
            # 统计每一个数字出现了多少次  5. 111221 6. 312211
            for _index, _value in enumerate(res):
                current_char = _value
                if _index == 0:  #这是第一个字符
                    previous_char = _value
                    num += 1
                    continue
                else:  
                    if current_char == previous_char:  # 又遇到数字相同的情况
                        num += 1  # 出现次数加1
                    else:  # 否则之前的数字的统计结束了，放进去。并更新这次的数字为新的previous_char及其num。
                        new_res = new_res + [str(num), str(previous_char)]
                        previous_char = current_char
                        num = 1

                    if _index == len(res) - 1:
                        new_res = new_res + [str(num), str(current_char)]
                    
            res = new_res
        return ''.join(res)

print("leet code accept!!!")
Input = [1, 4, 5, 6]
Answer = ["1", "1211", "111221", "312211"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.countAndSay(Input[i])
        print(reslut==Answer[i])

执行用时 :64 ms, 在所有 Python3 提交中击败了10.27%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了24.31%的用户

方案一的更简洁的实现

活用While，代码更加简洁。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def countAndSay(self, n: int) -> str:
        def next_num(tmp):
            res = ""
            i = 0
            tmp_n = len(tmp)
            while i < tmp_n:
                count = 1
                while i < tmp_n - 1 and tmp[i] == tmp[i+1]:  # 使用while直到遇到不同再添加，tmp[i] != tmp[i+1]时，意味着到这个数字后面再无重复。
                    count += 1
                    i += 1
                res += (str(count) + tmp[i])  # 此处添加
                i += 1  # 从下一个位置开始
            return res
        res = "1"
        for i in range(1, n):
            res = next_num(res)
        return res

执行用时 :48 ms, 在所有 Python3 提交中击败了31.57%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了26.41%的用户

方案二的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution2:
    def countAndSay(self, n: int) -> str:
        first_str=''
        # count记录了连续相同的数
        count=1
        temp=''
        while(n>0):
            if first_str=='':
                first_str='1'
                n-=1
                continue
            if len(set(first_str))==1:
                first_str=str(len(first_str)*int(first_str[0]))+first_str[0]
                n-=1
                continue
            # 这样写循环虽然很繁琐，但是思路还是挺清晰的
            for index in range(len(first_str)):
                # 如果两个相邻的数相等
                if first_str[index+1]==first_str[index]:
                    # 如果为最后两个数，例如 1,1
                    if (index+1)==len(first_str)-1:
                        count+=1
                        temp+=str(count)+first_str[index]
                        first_str=temp
                        n-=1
                        temp=''
                        count=1
                        break
                    # 不为最后两个数
                    else:
                        count+=1
                 # 如果两个相邻的数不相等
                else:
                    # 如果最后两个数不相等，例如 2,1
                    if(index+1)==len(first_str)-1:
                        temp+=str(count)+first_str[index]
                        # 因为最后一个字符肯定为 1
                        first_str=temp+'11'
                        n-=1
                        temp=''
                        count=1
                        break
                    # 不是最后两个数，且相邻两个数不等，重新计数
                    else:
                        temp+=str(count)+first_str[index]
                        count=1
        return first_str

执行用时 :44 ms, 在所有 Python3 提交中击败了44.07%的用户
内存消耗 :13.1 MB, 在所有 Python3 提交中击败了26.58%的用户