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

Question

计算长度为n的字符串长度为4的子序列,可以被9整除.

例如,如果输入字符串是9999,则cnt = 1

我的方法与Brute Force类似,需要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).