38. 外观数列

难度：简单

题目

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

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

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

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

第一项是数字 1

描述前一项，这个数是 1 即 “一个 1 ”，记作 11

描述前一项，这个数是 11 即 “两个 1 ” ，记作 21

描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211

描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221

示例 1:

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

示例 2:

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

Reference

题解

基本思路： 根据定义进行计算即可，注意次数部分可能超过10，而数字部分不会超过10。

代码如下：

char * toStr(int n)
{
    char *ret = (char *)memset(malloc(sizeof(char) * 10), 0, sizeof(char) * 10), temp;
    int i = 0, head = 0, tail;
    while (n)
    {
        ret[i] = n % 10 + '0';
        n /= 10;
        i++;
    }
    tail = i - 1;
    while(head < tail)
    {
        temp = ret[head];
        ret[head] = ret[tail];
        ret[tail] = temp;
    }
    return ret;
}

char * countAndSay(int n){
    if (n == 1)
    {
        char *ret = (char *)malloc(sizeof(char) * 2);
        ret[0] = '1';
        ret[1] = 0;
        return ret;
    }
    char *rec = countAndSay(n - 1), *cur = rec, flag = *cur, *temp = NULL,
         *ret = (char *)memset(malloc(sizeof(char) * (strlen(rec) * 2 + 1)), 0, sizeof(char) * (strlen(rec) * 2 + 1)), *retcur = ret;
    int counter = 0;
    while(*cur)
    {
        if (*cur == flag)
            counter++;
        else
        {
            temp = toStr(counter);
            strcpy(retcur, temp);
            while(*retcur)
                retcur++;
            *retcur = flag;
            *retcur++;
            flag = *cur;
            counter = 1;
            free(temp);
        }
        cur++;
    }
    temp = toStr(counter);
    strcpy(retcur, temp);
    while (*retcur)
        retcur++;
    *retcur = flag;
    free(temp);
    free(rec);
    return ret;
}

评论