leetcode_413 等差數列劃分

語言: CN / TW / HK

要求

如果一個數列 至少有三個元素 ,並且任意兩個相鄰元素之差相同,則稱該數列為等差數列。

例如,[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數列。\ 給你一個整數陣列 nums ,返回陣列 nums 中所有為等差陣列的 子陣列 個數。

子陣列 是陣列中的一個連續序列。

示例 1: 輸入:nums = [1,2,3,4] 輸出:3 解釋:nums 中有三個子等差陣列:[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。 示例 2: 輸入:nums = [1] 輸出:0

提示:

  • 1 <= nums.length <= 5000
  • -1000 <= nums[i] <= 1000

核心程式碼

python class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: n = len(nums) if n < 3: return 0 res = 0 for l in range(0,n - 2): k,different = 2,nums[l + 1] - nums[l] for r in range(l + 2,n): if nums[r] - nums[r - 1] == different: k += 1 else: break if k - 2 >= 1: res += k -2 return res

另一 解法

python class Solution: def numberOfArithmeticSlices(self, nums: List[int]) -> int: dp = [0 for _ in range(len(nums))] for i in range(2,len(nums)): if nums[i] - nums[i -1] == nums[i - 1] - nums[i - 2]: dp[i] = dp[i - 1] + 1 return sum(dp)

image.png

重點問題

解題思路:

第一種解法:我們使用迴圈的方式,第一層迴圈迴圈元素,第二層迴圈,迴圈等差數列,陣列遞增的程度,[2,3,4],[2,3,4,5],[2,3,4,5,6],break,我們的k變成了5,5最開始湊不成等差數列的2,得到的就是能成的等差數列的個數,這個方法比較簡單。第二種解法:使用的是動態規劃的思想,看到按照規律統計子陣列個數這一類的問題,很快地可以想到用動態規劃來解決。定義陣列dp,維度與輸入A一致,dp[i]表示以A[i]結尾的等差子陣列的個數,dp陣列中的元素全部初始化為零,因為以A[i]結尾的等差子陣列的個數最少為零。從第三個數字開始遍歷陣列,如果遇到以該陣列結尾的連續三個元素是等差的,那麼說明發現新的等差子陣列,或者原有的等差子陣列繼續延長。這時,以A[i]結尾的等差陣列的個數為以A[i-1]結尾的等差子陣列的個數加一,簡單的例子就可以說明。可以獲得遞推關係式:dp[i] = dp[i-1] + 1,最終,返回dp陣列中所有元素和即可。