查找第n个报数序列元素

Question

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

1被念作“one 1”或者11。 11被念作“two 1s”或者21。 21被念作“one 2, then one 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;
}

对于这个问题，是否有更好的解决方案？ 请提供一些建议/提示。 提前感谢。

- Luv

Answer 1

你可以使用动态规划。经过一段时间后，你会遇到已经计算过的子字符串。你可以保留一个已计算序列的映射表：

1 -> 11
11 -> 21

现在你需要计算1211。

首先你需要计算1，它的值为11。

然后你遇到了2，因为之前没有出现过，所以需要计算12并将其添加到映射表中：

2 -> 12

你遇到了11，再次提醒你在地图中把它标记为21。将它们串联起来得到：

111221

和新地图相关的内容

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

编辑：您只需要寻找连续的相同数字，因此只需在映射中保留这些数字。

- Luchian Grigore

---

这个的时间复杂度会是多少？ - Luv

@Luv 应该接近线性，但不确定。 - Luchian Grigore

你如何在一个数组中使用字符串作为索引，我的意思是说可能会产生冲突，否则空间复杂度会很高。 - Luv

@Luv 我不会使用数组，而是使用某种搜索树。C语言没有内置的哈希机制支持。 - Luchian Grigore

说实话，我不认为这是正确的答案，因为当你知道要寻找“111”时，你已经知道答案是“31”，所以在这里不需要缓存。真正有趣的是，在某个时刻，这个字符串会重复出现，并且有一个（相对）恒定的扩展速度。 - windmaomao