0

我正在为一家名为 Code Nation 的公司进行测试，遇到了这个问题，该问题要求我计算数字 k 在子矩阵 M[n][n] 中出现的次数。现在有一个例子这样说输入。

5
1 2 3 2 5
36

M[i][j]是计算a[i]*a[j] 在计算轮我可以计算的。

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

现在我必须计算 36 在 M 的子矩阵中出现了多少次。

答案是 5。

我无法理解如何计算这个子矩阵。如何表示？ 我有一种天真的方法，导致了许多我认为没有一个是正确的矩阵。

其中之一是 Submatrix[i][j]

1 2 3  2  5
3 9 18 24 39
6 18 36 60 99
15 33 69 129 228
33 66 129 258 486

这是通过将 0,0 之前的所有数字添加到 i,j

在这 36 中没有出现 5 次，所以我知道这是不正确的。如果你可以用一些伪代码来备份它，那将是锦上添花。

感谢帮助

[编辑]：参考以下链接 1 链接 2

4

1 回答 1

1

我的猜测是你必须计算 M 的多少子矩阵的总和等于 36。

这是 Matlab 代码：

a=[1,2,3,2,5];
n=length(a);
M=a'*a;
count = 0;
for a0 = 1:n
    for b0 = 1:n
        for a1 = a0:n
            for b1 = b0:n
                A = M(a0:a1,b0:b1);
                if (sum(A(:))==36)
                    count = count + 1;
                end
            end
        end
    end
end
count

这打印出 5。

所以你正确地计算了 M，但是你必须考虑 M 的每个子矩阵，例如，M 是

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

所以一个可能的子矩阵是

1,2,3
2,4,6
3,6,9

如果你把所有这些加起来，那么总和就等于 36。

ctheory 上有一个答案，它为此提供了 O(n^3) 算法。

于 2015-03-15T09:29:19.170 回答