c - 找到第 n 个 count-and-say 序列元素

Question

Given a problem, the count-and-say sequence is the sequence of integers beginning as     follows:
1, 11, 21, 1211, 111221, ...

1 读作“一 1”或 11。11 读作“两个 1”或 21。21 读作“一个 2，然后一个 1”或 1211。给定一个整数 n，生成第 n 个序列。

我通过扫描每个字符串并相应地生成下一个字符串来制定解决方案时间为 O(nm)其中 m 是最大字符串的长度n 是给定的数字

代码在这里

void countnsay(char str[][1000],int n)
{
int i=1,k;
int j=0;
while(i<=(n-1))
{
//scan str[i-1]
j=0;
k=0;        //for building the new string array 
while(j<strlen(str[i-1]) )
    {
    char c=str[i-1][j];
    int cnt=1;

    while(c==str[i-1][++j])
    cnt++;

    str[i][k++]=cnt+48;
    str[i][k++]=c;

    }
str[i][k]='\0';
i++;

}
printf("%s",str[n-1]);  
}




int main()
{
int n=5;
char str[1000][1000];
strcpy(str[0],"1");
countnsay(str,n);
return 0;
}

这个问题有更好的解决方案吗？请给出一些建议/提示。提前致谢

Answer 1

您可以使用动态规划。一段时间后，您将遇到已经计算过的现有子字符串。您可以保留已计算序列的映射:

1 -> 11
11 -> 21

现在您需要计算 1211。

您首先选择 1，您已经知道它是 11。

您遇到 2。你没有这个，所以计算 12 并将它添加到 map 中:

2 -> 12

您遇到 11，在您的 map 中同样显示为 21。

连接这些，你得到

111221

和新 map

1 -> 11
11 -> 21
2 -> 12

编辑:您只查找连续的相同数字，因此只保留 map 中的数字。