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

1 は「1 つの 1」または 11 として読み取られます。11 は「2 つの 1」または 21 として読み取られます。21 は「1 つの 2、次に 1 つの 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 に答える