[数据结构与算法]力扣 [38] [中等] [外观数列]

38. 外观数列

难度中等737收藏分享切换为英文接收动态反馈

给定一个正整数?n?，输出外观数列的第?n?项。

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

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n)?是对?countAndSay(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"

要?描述?一个数字字符串，首先要将字符串分割为?最小?数量的组，每个组都由连续的最多?相同字符?组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串?"3322251"?的描述如下图：

示例 1：

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

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

• 1 <= n <= 30

?--------------------------------分割线-------------------------------

老规矩，看到所求项跟前面的项有关，想到用递归或动态规划。此处选择用动态规划，空间换时间，把所有项算出来。

重点难点：

1. 字符串长度：n值为20开始，字符串长度就变得很大，所以上来直接给MAXLEN 为10000

2. 根据上一个字符串，推算下一个字符串，使用双指针，统计相同字符个数，然后个数和对应字符写到下一个字符串中。

直接贴代码

#define MAXCNT (31)
#define MAXLEN (10000)

void GetNextStr(char *PreStr, char *NextStr){
    int cnt = 0 ;
    int idx = 0;
    char c = 0;
    char *p = NULL;
    char *q = NULL;
    
    p=PreStr;
    //双指针
    while((*p) != '\0'){
        q = p+1;
        cnt = 1;
        while(((*q)==(*p))&&((*q)!='\0')){
            q++;
            cnt++;
        }
        NextStr[idx++] = '0' + cnt;
        NextStr[idx++] = (*p);
        p=q;
    }
    NextStr[idx++] = '\0';
}

char * countAndSay(int n){
    int i;
    char *result[MAXCNT] = {NULL};
    for(i=0;i<MAXCNT;i++){
        result[i] = (char *)malloc(MAXLEN);
    }
    //动态规划
    result[1]="1";
    for(i=2;i<=n;i++){
        GetNextStr(result[i-1],result[i]);
    }
    return result[n];
}

过程中写了一个bug，定位了半个小时。。。哎，低级错误

?