38. 报数

Posted on In Views: Disqus:
LeetCode刷题系列。

描述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1
2
3
4
5
1.     1
2.     11
3.     21
4.     1211
5.     111221

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

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

注意：整数顺序将表示为一个字符串。

示例 1:

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

示例 2:

1
2
输入: 4
输出: "1211"

提示1

The following are the terms from n=1 to n=10 of the count-and-say sequence:

1
2
3
4
5
6
7
8
9
10
 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
10.     13211311123113112211

提示2

To generate the nthn^{th} term, just count and say the n−1th{n-1}^{th} term.

来源：力扣（LeetCode）
链接：count and say

解题思路

这道题题目比较难以理解，初看让人有点一头雾水，如果理解了，题目本身还是比较简单的。所以先来理解以下题意。

所谓的报数序列是通过以下规则进行映射的，第一条映射规则：1约定为1，然后第二条规则，也就是后面进行递推的规则，对于2，则是对于2之前的整数1的所映射的序列1进行报数：一个一的结果:11，然后3的话则是对2所映射的序列11进行报数：两个一的结果：21，然后以此类推。从1到10的结果可以看提示1。

理解了题意以后，解题的关键可以参考提示2，对于第n个整数所映射的序列的求解，其实是对第n-1个整数的序列进行计数并且报数，看样子可以用递归来实现。

递归实现见解法一。

既然能够递归实现，通常也可以采用迭代的方式实现。

显然，我们每次需要往字符串中插入的有数字target的个数counter和数字target本身，我们定义两个字符串指针并分配空间tmp和result，在判断了边界情况，即n=1以后，我们的大循环从 2 到 n，在大循环内部我们再依次遍历映射后的报数序列，注意这里循环的起始已经结束条件，每次统计相邻的数字相邻的个数：counter++;i++，然后一旦相邻的数字不同了，我们就需要把统计到的个数counter和数字target插入字符串，遍历完了要注意最后一个counter和target是没有插入的，我们需要在外部进行插入。最后在把缓存的字符串tmp复制到我们要返回的字符串result中，然后再次遍历即可。这里面要注意int 和 char之间的转化，具体可以再看代码当中的注释。

代码

解法一

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
48
char* helper(char *s, int n)
{
    
    
    
    //处理递归退出条件
    if(n == 1)
    {
        return s;
    }
    
    //处理下一个数的情况
    else
    {
       //如果s不为空，遍历输入的s，尝试改为for循环，好像比较难，因为不知道ch数组会是多长
        while (*s!='\0')
        {
            //设置计数器
            int count = 1;
            //开列返回的字符数组
            char ch[10000];
            //因为不知道数组具体有多长，用指针表示更加方便，并且数组和指针还是有区别的，这里如果直接用malloc申请一片空间，后面将会出错
            char* p = ch;
            
            //如果上一个整数的映射序列有相同的元素则count++，同时字符串的指针也相应后移
            while (*s==*(s+1))
            {
                count++;
                s++;
            }
            
            //修改返回字符串中的值，报数的个数
            *p++ = (char)(count+'0');
            //修改返回字符串中的值，报数的整数类别
            *p++ = *s++;
        }
        //递归函数调用
        return helper(ch, n - 1);
    }
    
}

char * countAndSay(int n)
{
    return helper("1", n);
}


解法二

#define Len 4500

char * countAndSay(int n)
{
    //全局数组空间分配
    char* result = (char *)malloc(sizeof(char) * Len);
    char* tmp = (char *)malloc(sizeof(char) * Len);
           
    //返回的数组的初始化，以1的报数映射进行初始化
    result[0] = '1';
    result[1] = '\0';
    
        
    //判断边界条件
    if(n ==  1)
    {
       return result;
    }
    
    //对于不同的n进行逐个处理
    for (int len = 2; len <= n; len++)
    {
        //声明待插入的目标数字result的首字符
        char target = result[0];
        //初始化n-1整数的映射序列长度
        int pre_len = 0;
        //初始化计数器
        int counter = 0;
        
        //遍历n-1整数的映射序列
        for (int i = 0; i < strlen(result); )
        {
            //统计相邻的数字相邻的个数
            if(result[i] == target)
            {
                counter++;
                i++;
            }
            
            //如果不相同则把统计到的个数count和数字target插入字符串，此处注意每次插入都要pre_len++，且在插入完毕以后将计数器counter归零，并且更新target值
            else
            {
                tmp[pre_len++] = counter + '0';
                tmp[pre_len++] = target;
                counter = 0;
                target = result[i];
            }
        }
        
        //最后一个counter和target是没有插入的，我们需要在外部进行插入
        
        tmp[pre_len++] = counter + '0';
        tmp[pre_len++] = target;
        tmp[pre_len] = '\0';
        
        //把缓存的字符串复制到我们以前那个字符串，这时也会更新strlen(result)的长度
        strcpy(result, tmp);
    }
    
    //退出循环首先释放内存
    free(tmp);
    
    //返回结果
    return result;
}

- [Java和C，尾递归，0ms](https://leetcode-cn.com/problems/count-and-say/solution/javahe-cwei-di-gui-0ms-by-heator/)

- [不用直接推的100%并且只使用两个数组](https://leetcode-cn.com/problems/count-and-say/solution/bu-yong-da-biao-de-100-by-hai-gen/)