Python程序：求数组中等间距元素之和

假设有一个大小为n的数组'nums'，包含正整数。还有一个数组'queries'，包含整数对(pi, qi)。对于'queries'数组中的每个查询，答案将是数组nums[j]中数字的和，其中pi <= j < n 且(j - pi)能被qi整除。我们必须返回所有此类查询的答案，如果答案是一个很大的值，我们返回答案模10^9 + 7。

因此，如果输入类似于nums = [2, 3, 4, 5, 6, 7, 8, 9, 10]，queries = [(2, 5), (7, 3), (6, 4)]，则输出将为[13, 9, 8]。

为了解决这个问题，我们将遵循以下步骤：

  • A := nums

  • Q := queries

  • n := nums的长度

  • M := 10^9 + 7

  • m := (n ^ 0.5) + 2的整数部分

  • P := 一个新的列表，包含A列表m次。

  • 对于i从1到m，执行：

    • 对于j从n-1到-1递减，执行：

      • 如果i+j < n，则

        • P[i, j] := (P[i, j]+P[i, i+j]) mod M

  • 对于Q中的每个值b, k，执行：

    • 如果k < m，则

      • 返回[P[k, b]的索引值]

    • 否则

      • 返回[sum(A[b到k]) mod M]

示例

让我们来看下面的实现，以便更好地理解：

def solve(A, Q):
   n, M = len(A), 10**9+7
   m = int(n**0.5)+2
   P = [A[:] for _ in range(m)]
   for i in range(1,m):
      for j in range(n-1,-1,-1):
         if i+j < n:
            P[i][j] = (P[i][j]+P[i][i+j]) % M
   return [P[k][b] if k < m else sum(A[b::k]) % M for b, k in Q]

print(solve([2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]))

输入

[2, 3, 4, 5, 6, 7, 8, 9, 10], [(2, 5), (7, 3), (6, 4)]

输出

[13, 9, 8]

更新于：2021年10月8日

274 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告