代码收藏家 Python –itertools中accumulate函数详细讲解
1.1前言：
本文将详细讲解itertools中的accumulate，accumulate函数可以在前缀和中运用，否则就需要每次移动的时候维护一个前缀和，大家如果不知道前缀和也可以先了解一下前缀和，前缀和可以解决数组区间和查询问题、矩阵区域和查询问题、连续子数组和问题、最大子段和问题、最大子矩阵和问题这里，但是如果大家不太了解前缀和也可以放心食用，因为运用这个累加函数其实十分简单。
1.2定义：
itertools. accumulate(iterable[,function,*,initial = None])
创建一个返回累积汇总值或来自其他双目运算函数的累积结果的迭代器。function 默认为加法运算。 function 应当接受两个参数，即一个累积汇总值和一个来自 iterable 的值。如果提供了 initial 值，将从该值开始累积并且输出将比输入可迭代对象多一个元素。
大家也可以自行实现前缀和，第一种是简易写法，这种写法其实已经满足很多前缀和的题目了，
pre_num = [0]
#由于为了满足前缀和的性质第一个数一定要置零才能满足所有的数都可以由两个前缀和来表示
for idx,x in enumerate(nums):
pre_num.append(pre_num[idx] + x)
accumulate大致相当于：
def accumulate(iterable, function=operator.add, *, initial=None):
'Return running totals'
# accumulate([1,2,3,4,5]) → 1 3 6 10 15
# accumulate([1,2,3,4,5], initial=100) → 100 101 103 106 110 115
# accumulate([1,2,3,4,5], operator.mul) → 1 2 6 24 120
iterator = iter(iterable)
total = initial
if initial is None:
try:
total = next(iterator)
except StopIteration:
return
yield total
for element in iterator:
total = function(total, element)
yield total值得注意的是如下用法放回的是地址而不是元素的值
temp = itertools.accumulate([1,2,3,4,5,6], initial = 0)
##结果：<itertools.accumulate object at 0x00000193FA04D990>如果要返回元素的值还需要如下操作:
temp = list(itertools.accumulate([1,2,3,4,5,6], initial = 0))1.3衍生用法：
刚才我们也提到了accumulate里面有个参数是function，这个函数默认是累加方法，但是用户也可以自己自己设定方法，比如max , min,等其他。
data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
list(accumulate(data, max)) # 运行最大值
##结果[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]
list(accumulate(data, operator.mul)) # 运行乘积
##结果[3, 12, 72, 144, 144, 1296, 0, 0, 0, 0]
##题目： 分期偿还利率 5% 总额 1000 的货款，每年还款 10 次，每次 90
update = lambda balance, payment: round(balance * 1.05) - payment
list(accumulate(repeat(90, 10), update, initial=1_000))
##结果[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]1.3Leetcode的实际运用:
Eg1:使数组元素全部相等的最少操作次数：
给你一个正整数数组 nums 。同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：
1 。请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。
注意，每次查询后，数组变回最开始的值。
示例 1：
输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：
– 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
– 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
– 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
第一个查询的总操作次数为 2 + 5 + 7 = 14 。
第二个查询，我们可以执行以下操作：
– 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
– 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
– 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
– 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。
#题解参考万能的灵神：
本题采用数组排序后，二分找q的位置，其中蓝色的面积+绿色的面积即为答案，并且本题可以采用前缀和优化：
class Solution:
def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
nums.sort()
n = len(nums)
s = list(accumulate(nums,initial = 0)) ##前缀和
ans = []
for q in queries:
j = bisect_left(nums, q)
left = q * j - s[j] #蓝色面积
right = s[n] - s[j] - q*(n - j) #绿色的面积
ans.append(left + right)
return ansEg2:执行操作频率分数最大：（注意本题和上题十分类似，只是本题是前缀和+滑动窗口）
给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你可以对数组执行 至多 k 次操作：
i ，将 nums[i] 增加 或者 减少 1 。请你返回你可以得到的 最大 频率分数。众数指的是数组中出现次数最多的数。一个元素的频率指的是数组中这个元素的出现次数。
示例 1：
输入：nums = [1,2,6,4], k = 3
输出：3
解释：我们可以对数组执行以下操作：
– 选择 i = 0 ，将 nums[0] 增加 1 。得到数组 [2,2,6,4] 。
– 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,3] 。
– 选择 i = 3 ，将 nums[3] 减少 1 ，得到数组 [2,2,6,2] 。
元素 2 是最终数组中的众数，出现了 3 次，所以频率分数为 3 。3 是所有可行方案里的最大频率分数。l
灵神题解：数组排序后，要变成一样的数必然在一个连续子数组中，那么用滑动窗口来做，枚举子数组的右端点 right，然后维护子数组的左端点 left。根据中位数贪心，最优做法是把子数组内的元素都变成子数组的中位数，操作次数如果超过 k，就必须移动左端点。求出数组的前缀和，就可以 O(1) 算出操作次数了，
from itertools import accumulate
class Solution:
def maxFrequencyScore(self, nums: List[int], k: int) -> int:
#前缀和的知识，注意前缀和s[0] == 0 这样定义有一个好处就是任意子数组包括前缀哦都可以表示为两个前缀和的差
#中位数贪心，将所有元素变为nums的中位数是最优
nums.sort()##最开始忘了要排序
pre_sum = list(accumulate(nums, initial = 0))
#由于第一个数字是零所以整个长度就是n + 1
def distance_sum(left , right) -> int:
mid = ( right + left ) // 2
left_sum = nums[mid] * (mid - left) - (pre_sum[mid] - pre_sum[left])
right_sum = pre_sum[right+1] - pre_sum[mid+1] - (right - mid) * nums[mid]
return left_sum + right_sum
left = ans = 0 #滑动窗口
for right in range(len(nums)):
while distance_sum(left,right) > k :
left += 1
ans = max(ans,right - left + 1)
return ans作者：何等样仁
