给出了一个长度为n的数组。求子数组元素的乘积之和。
解释
长度为3的数组A=[2,3,4]。
因为,对于以模1000000007计算的较长的子数组,乘积可以更大。
对于所有可能长度的子数组,即1,2,3,....,n,求这些和的有效方法是什么,其中n是数组的长度。
有一种相当简单的方法:
构造术语(1+a[i]*x)
:
P = (1 + A[0] * x) * (1 + A[1] * x) * (1 + A[2] * x)...*(1 + A[n-1] * x)
如果我们打开括号,我们会得到多项式
P = 1 + B[1] * x + B[2] * x^2 + ... + B[n] * x^n
第k个系数b[k]等于长度为k-的集合的乘积之和,例如b[n]=a[0]*a[1]*a[2]*...a[n-1],b[2]=a[0]*a[1]+a[0]*a[2]+...+a[n-2]*a[n-1]
等等。
(1+2)(1+3)(1+4) = 60
60 - 1 = 59
59 - (2 + 3 + 4) = 50 = 24 + 26 - as your example shows
问题内容: 给出了长度为 n 的数组。查找子数组元素的乘积之和。 说明 数组 A* = 长度 3的 [2,3,4] 。 * 长度为 2的 子数组= [2,3],[3,4],[2,4] [2,3] 中元素的乘积= 6 [3,4] 中元素的乘积= 12 [2,4] 中元素的乘积= 8 长度 2 = 6 + 12 + 8 = 26的子数组的总和 同样,对于长度 3 ,Sum = 24 因此,乘积以模 1
给定一个数组,我应该在线性时间内计算以下和: 我最天真的实现是O(n3): 我不知道该怎么办。我尝试了很多算法,但它们最多只能是O(n*log(n)),但我应该在线性时间内解决它。还有,我不明白,有没有一种数学方法可以只看一个数组,然后告诉上面的和的结果?
例如:如果数组是[9,8,7,6,5,4,3,1,2,2],它应该返回46(长度为7的子数组[9,8,7,6,5,4,3]和长度为2的子数组[2,2]之和)。不能组合[9,8,7,6,5,4,3]和[1,2,2],因为这将产生长度为10的非素数的连续子数组(幂等性)。 有谁能解释一下如何使用DP来解决这类问题吗?多谢了。
我在一次采访中遇到了以下问题。 给定一个数组,您需要找到所有元素小于给定值 k 的子数组 ,例如 现在,值小于 4 的子数组是: 注意{4}是如何重复的,但没有考虑两次。现在,代码应该返回不同子阵列的计数 在本例中为3. 另一个示例: 不同的子阵列: 我的方法是找到小于给定值k(即O(n^2))的子阵列,然后将其插入类似无序集的内容中以删除重复项。 有没有解决这个问题的有效方法?
我有这个问题: 您将获得一个整数 A 和一个整数 k 的数组。您可以将 A 的元素递减到 k 次,目标是生成一个元素都相等的连续子数组。返回可以用这种方式生成的最长的连续子数组的长度。 例如,如果 A 是 [1,7,3,4,6,5] 并且 k 是 6,那么您可以生成 [1,7,3,4-1,6-1-1-1,5-1-1] = [1,7,3,3,3,3],因此您将返回 4。 最佳解决方案是什么?
给定一个整数N和一个长度为N的数组,该数组由0到N-1的整数组成,可能包含也可能不包含所有整数,也可能包含重复数。查找一个从索引i到索引j的子数组(i, j),使其包含数组中的所有整数,并且具有最小长度。输出是这样一个子数组的长度 示例:A=[2,1,1,3,2,1,1,3],因此最小子数组长度=3,因为A[2]到A[4]包含所有数字 我的想法: 维护一个计数器数组和两个索引开始和结束,其中包含数