7

長さ n の文字列の 9 で割り切れる長さ 4 の部分列を数えること。

たとえば、入力文字列が 9999 の場合、cnt=1

私のアプローチはブルート フォースに似ており、O(n^3) を使用します。これよりも優れたアプローチはありますか?

4

4 に答える 4

5

数値が 9 で割り切れるかどうかを調べたい場合は、こちらをご覧ください。

その方法を簡単に説明します。

checkDividedByNine(String pNum) :
If pNum.length < 1
   return false
If pNum.length == 1
   return toInt(pNum) == 9;
Sum = 0
For c in pNum:
    Sum += toInt(pNum)
return checkDividedByNine(toString(Sum))

したがって、実行時間を O(n^3) 未満に短縮できます。

編集: 非常に高速なアルゴリズムが必要な場合は、9 で割り切れる場合、可能な 4 桁の数字ごとに保存するために前処理を使用できます (メモリに 10000 かかります)。

EDIT 2: より良いアプローチ: 動的プログラミングを使用できます:

長さ N の文字列 S の場合:

D[i,j,k] = 文字列 S[i..N] 内の長さ j のサブシーケンスの数で、その値はモジュロ 9 == k です。

ここで、0 <= k <= 8、1 <= j <= 4、1 <= i <= N です。

D[i,1,k] = simply count the number of elements in S[i..N] that = k(mod 9).
D[N,j,k] = if j==1 and (S[N] modulo 9) == k, return 1. Otherwise, 0.
D[i,j,k] = max{ D[i+1,j,k], D[i+1,j-1, (k-S[i]+9) modulo 9]}.

そして、D[1,4,0​​] を返します。

テーブルのサイズは N x 9 x 4 です。

したがって、モジュロの計算に O(1) かかると仮定すると、全体の実行時間は O(n) になります。

于 2012-08-07T21:05:33.060 に答える
0

ルックアップ テーブルを使用する上記の方法に基づいて、上記の問題の完全な作業コードを次に示します。

int fun(int h)
{
return (h/10 + h%10);
}

int main()
{
int t;
scanf("%d",&t);
int i,T;
for(T=0;T<t;T++)
{
    char str[10001];
    scanf("%s",str);        
    int len=strlen(str);
    int arr[len][5][10];
    memset(arr,0,sizeof(int)*(10*5*len));

    int j,k,l;
        for(j=0;j<len;j++)
            {
              int y;
                y=(str[j]-48)%10;
                arr[j][1][y]++;
            }



        //printarr(arr,len);    





        for(i=len-2;i>=0;i--)   //represents the starting index of the string
            {


                    int temp[5][10];
                    //COPYING ARRAY
                    int a,b,c,d;
                    for(a=0;a<=4;a++)
                    for(b=0;b<=9;b++)
                    temp[a][b]=arr[i][a][b]+arr[i+1][a][b];


            for(j=1;j<=4;j++)   //represents the length of the string
                {
                for(k=0;k<=9;k++)   //represents the no. of ways to make it
                    {

                        if(arr[i+1][j][k]!=0)
                          {
                          for(c=1;c<=4;c++)
                            {
                              for(d=0;d<=9;d++)
                                 {
                            if(arr[i][c][d]!=0)
                                 {
                                int h,r;
                                r=j+c;
                                if(r>4)
                                continue;
                                h=k+d;                      
                                h=fun(h);
                                if(r<=4)
                                  temp[r][h]=( temp[r][h]+(arr[i][c][d]*arr[i+1][j][k]))%1000000007;
                              }}}
                        }






                    //copy back from temp array

                    }
                }
                for(a=0;a<=4;a++)
                    for(b=0;b<=9;b++)
                    arr[i][a][b]=temp[a][b];
            }








printf("%d\n",(arr[0][1][9])%1000000007);


}


    return 0;
}
于 2012-08-08T14:01:00.450 に答える