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

Question

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

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

我的方法类似于 Brute Force 并且需要 O(n^3)。还有比这更好的方法吗？

Answer 1

如果你想检查一个数是否能被9整除，你最好看看here .

我将简要描述该方法:

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 的 table 。

因此，假设计算模数为 O(1)，则整体运行时间为 O(n)。