algorithm - 计算长度为 4 可被 9 整除的子序列

Question

计算长度为 n 的字符串中长度为 4 且可被 9 整除的子序列。

例如如果输入字符串是 9999 那么 cnt=1

我的方法类似于蛮力并采用 O(n^3)。还有比这更好的方法吗？

Answer 1

如果你想检查一个数字是否能被 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)。

编辑： 如果您需要非常快速的算法，您可以使用预处理来保存每个可能的 4 位数字，如果它可以被 9 整除。（这将花费您 10000 的内存）

编辑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)。

Answer 2

假设子序列必须由连续的数字组成，您可以从左到右扫描，跟踪读取的最后 4 位数字的顺序。这样，您可以进行线性扫描并应用除法规则。

如果数字不一定是连续的，那么您可以使用查找表进行一些调整。这个想法是，您可以创建一个名为的 3D 数组table，它table[i][j][k]是i直到索引的数字总和的数量，j使得总和k在除以 9 时留下余数。表本身的大小为 45n（i从 0 到 4，j去从 0 到n-1，k从 0 到 8)。

对于递归，每个table[i][j][k]条目都依赖于从 0 到 8table[i-1][j-1][x]的table[i][j-1][x]所有x条目。由于每个条目更新都需要恒定的时间（至少相对于 n 而言），这应该会为您提供 O(n) 运行时。

Answer 3

这个怎么样：

/*NOTE: The following holds true, if the subsequences consist of digits in contagious locations */ 

public int countOccurrences (String s) {
    int count=0;
    int len = s.length();
    String subs = null;
    int sum;

    if (len < 4)
        return 0;
    else {
        for (int i=0 ; i<len-3 ; i++) {
            subs = s.substring(i, i+4);
            sum = 0;

            for (int j=0; j<=3; j++) {
                sum += Integer.parseInt(String.valueOf(subs.charAt(j)));
            }

            if (sum%9 == 0)
                count++;
        }           
        return count;
    }   
}

Answer 4

这是基于上述使用查找表的方法的上述问题的完整工作代码

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