生活随笔
收集整理的這篇文章主要介紹了
LeetCode 413 等差数列划分
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目描述
如果一個數列至少有三個元素，并且任意兩個相鄰元素之差相同，則稱該數列為等差數列。
例如，以下數列為等差數列
:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下數列不是等差數列。
1, 1, 2, 5, 7
數組 A 包含 N 個數，且索引從
0開始。數組 A 的一個子數組劃分為數組
(P
, Q
)，P 與 Q 是整數且滿足
0<=P
<Q
<N 。
如果滿足以下條件，則稱子數組
(P
, Q
)為等差數組：
元素 A
[P
], A
[p
+ 1], ..., A
[Q
- 1], A
[Q
] 是等差的。并且 P
+ 1 < Q 。
函數要返回數組 A 中所有為等差數組的子數組個數。
題解
動態規劃
:dp
[i
]表示以i位置的數為結尾中形成等差數列的個數的集合。則每次如果A
[i
]、A
[i?
1]、A
[i?
2]
形成一個等差數列，則這個A
[i
]有可能由和之前i
-1位置為結尾形成的所有等差數列分別拼接而成，所以計算集
合的值時要加上dp
[i?
1]、dp
[i
-1]、dp
[i?
1]。最后統計所有結尾的等差數量sum即可。
代碼
class Solution
{
public
:int numberOfArithmeticSlices(vector
<int>& A
) {int len
=A
.size();if (!len
||len
==1||len
==2) return 0;int res
=0,tmp
=0;for (int i
=2;i
<A
.size();i
++){if (A
[i
]-A
[i
-1]==A
[i
-1]-A
[i
-2]) tmp
=tmp
+1;else tmp
=0;res
+=tmp
;}return res
;}
};
總結
以上是生活随笔為你收集整理的LeetCode 413 等差数列划分的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
