快捷導(dǎo)航

Python?itertools中accumulate函數(shù)用法及使用運用詳細講解

更新時間：2025年02月15日 14:01:58 作者：何等樣仁

這篇文章主要介紹了Python的itertools庫中的accumulate函數(shù),該函數(shù)可以計算累積和或通過指定函數(shù)進行累積運算,文中通過代碼將用法介紹的非常詳細,需要的朋友可以參考下

1.1前言：

本文將詳細講解itertools中的accumulate，accumulate函數(shù)可以在前綴和中運用，否則就需要每次移動的時候維護一個前綴和，大家如果不知道前綴和也可以先了解一下前綴和，前綴和可以解決數(shù)組區(qū)間和查詢問題、矩陣區(qū)域和查詢問題、連續(xù)子數(shù)組和問題、最大子段和問題、最大子矩陣和問題這里，但是如果大家不太了解前綴和也可以放心食用，因為運用這個累加函數(shù)其實十分簡單。

1.2定義：

itertools. accumulate(iterable[,function,*,initial = None])

創(chuàng)建一個返回累積匯總值或來自其他雙目運算函數(shù)的累積結(jié)果的迭代器。function 默認為加法運算。 function 應(yīng)當接受兩個參數(shù)，即一個累積匯總值和一個來自 iterable 的值。如果提供了 initial 值，將從該值開始累積并且輸出將比輸入可迭代對象多一個元素。

大家也可以自行實現(xiàn)前綴和，第一種是簡易寫法，這種寫法其實已經(jīng)滿足很多前綴和的題目了，

pre_num = [0]
#由于為了滿足前綴和的性質(zhì)第一個數(shù)一定要置零才能滿足所有的數(shù)都可以由兩個前綴和來表示
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)

##結(jié)果：<itertools.accumulate object at 0x00000193FA04D990>

如果要返回元素的值還需要如下操作:

temp = list(itertools.accumulate([1,2,3,4,5,6], initial = 0))

1.3衍生用法：

剛才我們也提到了accumulate里面有個參數(shù)是function，這個函數(shù)默認是累加方法，但是用戶也可以自己自己設(shè)定方法，比如max , min,等其他。

data = [3, 4, 6, 2, 1, 9, 0, 7, 5, 8]
list(accumulate(data, max))              # 運行最大值
##結(jié)果[3, 4, 6, 6, 6, 9, 9, 9, 9, 9]

list(accumulate(data, operator.mul))     # 運行乘積
##結(jié)果[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))
##結(jié)果[1000, 960, 918, 874, 828, 779, 728, 674, 618, 559, 497]

1.3Leetcode的實際運用:

Eg1:使數(shù)組元素全部相等的最少操作次數(shù)：

給你一個正整數(shù)數(shù)組 nums 。同時給你一個長度為 m 的整數(shù)數(shù)組 queries 。第 i 個查詢中，你需要將 nums 中所有元素變成 queries[i] 。你可以執(zhí)行以下操作任意次：

將數(shù)組里一個元素增大或者減小 1 。

請你返回一個長度為 m 的數(shù)組 answer ，其中 answer[i]是將 nums 中所有元素變成 queries[i] 的最少操作次數(shù)。

注意，每次查詢后，數(shù)組變回最開始的值。

示例 1：

輸入：nums = [3,1,6,8], queries = [1,5]

輸出：[14,10]

解釋：第一個查詢，我們可以執(zhí)行以下操作：
- 將 nums[0] 減小 2 次，nums = [1,1,6,8] 。
- 將 nums[2] 減小 5 次，nums = [1,1,1,8] 。
- 將 nums[3] 減小 7 次，nums = [1,1,1,1] 。
第一個查詢的總操作次數(shù)為 2 + 5 + 7 = 14 。
第二個查詢，我們可以執(zhí)行以下操作：
- 將 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] 。
第二個查詢的總操作次數(shù)為 2 + 4 + 1 + 3 = 10 。

#題解參考萬能的靈神：

本題采用數(shù)組排序后，二分找q的位置，其中藍色的面積+綠色的面積即為答案，并且本題可以采用前綴和優(yōu)化：

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 ans

Eg2:執(zhí)行操作頻率分數(shù)最大：（注意本題和上題十分類似，只是本題是前綴和+滑動窗口）

給你一個下標從 0 開始的整數(shù)數(shù)組 nums 和一個整數(shù) k 。你可以對數(shù)組執(zhí)行至多 k 次操作：

從數(shù)組中選擇一個下標 i ，將 nums[i] 增加或者減少 1 。
最終數(shù)組的頻率分數(shù)定義為數(shù)組中眾數(shù)的頻率。

請你返回你可以得到的最大頻率分數(shù)。眾數(shù)指的是數(shù)組中出現(xiàn)次數(shù)最多的數(shù)。一個元素的頻率指的是數(shù)組中這個元素的出現(xiàn)次數(shù)。

示例 1：

輸入：nums = [1,2,6,4], k = 3

輸出：3

解釋：我們可以對數(shù)組執(zhí)行以下操作：
- 選擇 i = 0 ，將 nums[0] 增加 1 。得到數(shù)組 [2,2,6,4] 。
- 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數(shù)組 [2,2,6,3] 。
- 選擇 i = 3 ，將 nums[3] 減少 1 ，得到數(shù)組 [2,2,6,2] 。
元素 2 是最終數(shù)組中的眾數(shù)，出現(xiàn)了 3 次，所以頻率分數(shù)為 3 。3 是所有可行方案里的最大頻率分數(shù)。l

靈神題解：數(shù)組排序后，要變成一樣的數(shù)必然在一個連續(xù)子數(shù)組中，那么用滑動窗口來做，枚舉子數(shù)組的右端點 right，然后維護子數(shù)組的左端點 left。根據(jù)中位數(shù)貪心，最優(yōu)做法是把子數(shù)組內(nèi)的元素都變成子數(shù)組的中位數(shù)，操作次數(shù)如果超過 k，就必須移動左端點。求出數(shù)組的前綴和，就可以 O(1) 算出操作次數(shù)了，

from itertools import accumulate

class Solution:
    def maxFrequencyScore(self, nums: List[int], k: int) -> int:
        #前綴和的知識，注意前綴和s[0] == 0 這樣定義有一個好處就是任意子數(shù)組包括前綴哦都可以表示為兩個前綴和的差
        #中位數(shù)貪心，將所有元素變?yōu)閚ums的中位數(shù)是最優(yōu)
        nums.sort()##最開始忘了要排序
        pre_sum = list(accumulate(nums, initial = 0))
        #由于第一個數(shù)字是零所以整個長度就是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

總結(jié)

到此這篇關(guān)于Python itertools中accumulate函數(shù)用法及使用運用詳細講解的文章就介紹到這了,更多相關(guān)Python itertools中accumulate函數(shù)用法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: