資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學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 次瀏覽
廣告