4 
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;
}

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

4

1 回答 1

5

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

1 -> 11
11 -> 21

现在你需要计算1211.

你先去争取1，你已经知道了11。

你遇到的2。你没有这个，所以计算12并将其添加到地图中：

2 -> 12

您遇到11的 ，同样，您在地图中具有21。

连接这些，你得到

111221

和新地图

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

编辑：您只寻找连续相同的数字，所以只保留那些在地图上。

于 2012-05-28T09:00:33.187 回答