題目：如果一個(gè)數(shù)列至少有三個(gè)元素，并且任意兩個(gè)相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。例如，以下數(shù)列為等差數(shù)列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下數(shù)列不是等差數(shù)列。
1, 1, 2, 5, 7
數(shù)組 A 包含 N 個(gè)數(shù)，且索引從 0 開始。該數(shù)組子序列將劃分為整數(shù)序列 (P0, P1, ..., Pk)，P 與 Q 是整數(shù)且滿足 0 ≤ P0 < P1 < ... < Pk < N。如果序列 A[P0]，A[P1]，...，A[Pk-1]，A[Pk] 是等差的，那么數(shù)組 A 的子序列 (P0，P1，…，PK) 稱為等差序列。值得注意的是，這意味著 k ≥ 2。函數(shù)要返回?cái)?shù)組 A 中所有等差子序列的個(gè)數(shù)。輸入包含 N 個(gè)整數(shù)。每個(gè)整數(shù)都在 -231 和 231-1 之間，另外 0 ≤ N ≤ 1000。保證輸出小于 231-1。

來源：https://leetcode-cn.com/problems/arithmetic-slices-ii-subsequence/

法一：自己的代碼 時(shí)間復(fù)雜度是(1 + n) * n / 2 即n方

思路：依次遍歷A中的每個(gè)數(shù)，dp[i][k]表示以A[i]結(jié)尾公差為k（k != 0），長度至少為2的等差數(shù)列的個(gè)數(shù)-1，寫dp轉(zhuǎn)移方程之前，最重要的是要明確dp方程的定義。不同的dp轉(zhuǎn)移方程直接決定了不同的方法。

from collections import defaultdict
from typing import List
class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        size = len(A)
        # 注意這里，內(nèi)部是個(gè)可變對(duì)象，不能直接乘，類似與[[0,1]] * 5這種，改一個(gè)就全改了
        # dp = [defaultdict(lambda: -1)] * size
        dp = []
        # 生成dp
        for i in range(size):
            dp.append(defaultdict(lambda: -1))
        ans = 0
        for i in range(1,size):
            # m是為了記錄公差為0的等差數(shù)列的長度
            m = 1
            for j in range(i):
                # k是公差
                k = A[i] - A[j]
                # 如果公差存在于以A[j]結(jié)尾的數(shù)列中，且公差不為0，則必定可以構(gòu)成長為3的等差數(shù)列
                if k in dp[j].keys():
                    if k != 0:
                        # 這兩行是關(guān)鍵，
                        # 注意這里的兩個(gè)1，第一個(gè)1是為了補(bǔ)上dp[j][k]中從-1到0的那一次，同ans = ans + dp[j][k] + 1中的這個(gè)1
                        # 第二個(gè)1表示由A[j] A[i]構(gòu)成的數(shù)列，同下面m +=1的這個(gè)1
                        dp[i][k] = (dp[j][k] + 1) +1 + dp[i][k]
                        # 加1是因?yàn)椋跏贾凳菑?1開始加的，如2:0表示公差為2，但它是長度為2的等差數(shù)列，
                        # 所以加1是為了抵消從-1加1到0的那一次，因?yàn)樗呀?jīng)構(gòu)成了長度為2的等差數(shù)列，只不過以前長度無法達(dá)到3，現(xiàn)在達(dá)到了
                        # 這里之所以分開寫是因?yàn)椋琩p[i][k]表示的是  以A[i]結(jié)尾的長度為2的等差數(shù)列的個(gè)數(shù)-1  所以dp[j][k]+1就是在A[j]后
                        # 添加A[i]后，以A[j] A[i]結(jié)尾的等差數(shù)列的個(gè)數(shù)
                        ans = ans + dp[j][k] + 1
                    else:
                        m += 1
                else:
                    dp[i][k] += 1
            # 如果有公差為0的數(shù)列無法使用上述方法，直接記錄數(shù)列的長度用歸納法求解
            ans += (2 ** m - (m+1))
        # for i in dp:
        #     print(i)
        print(len(A), len(set(A)))
        return ans
if __name__  == '__main__':
    duixiang = Solution()
    # a = duixiang.numberOfArithmeticSlices([1,1,1,1,1])
    # a = duixiang.numberOfArithmeticSlices([79,20,64,28,67,81,60,58,97,85,92,96,82,89,46,50,15,
    #                                            2,36,44,54,2,90,37,7,79,26,40,34,67,64,28,60,89,46,
    #                                            31,9,95,43,19,47,64,48,95,80,31,47,19,72,99,28,46,
    #                                            13,9,64,4,68,74,50,28,69,94,93,3,80,78,23,80,43,49,
    #                                            77,18,68,28,13,61,34,44,80,70,55,85,0,37,93,40,47,
    #                                            47,45,23,26,74,45,67,34,20,33,71,48,96])
    # a = duixiang.numberOfArithmeticSlices([2,2,-1,2,5,8])
    # a = duixiang.numberOfArithmeticSlices([1,2,3,4,5])
    # a = duixiang.numberOfArithmeticSlices([6,6,8,10])
    a = duixiang.numberOfArithmeticSlices([4,4,3,4,5,6])
    # a = duixiang.numberOfArithmeticSlices([3,4,5,6,7])
    print(a)

View Code

總結(jié)

以上是生活随笔為你收集整理的446等差数列划分II-子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。