煙臺(tái)seo關(guān)鍵詞排名優(yōu)化英文
跳轉(zhuǎn)匯總鏈接
👉🔗算法題匯總鏈接
1.2 等差數(shù)列劃分
🔗題目鏈接
如果一個(gè)數(shù)列 至少有三個(gè)元素 ，并且任意兩個(gè)相鄰元素之差相同，則稱該數(shù)列為等差數(shù)列。例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差數(shù)列。
給你一個(gè)整數(shù)數(shù)組 nums ，返回?cái)?shù)組 nums 中所有為等差數(shù)組的子數(shù)組個(gè)數(shù)。 子數(shù)組是數(shù)組中的一個(gè)連續(xù)序列。
- 狀態(tài)表示：
- dp[i] 表示以 i 位置為結(jié)尾的等差數(shù)列的子數(shù)組個(gè)數(shù)。
- 狀態(tài)轉(zhuǎn)移方程：
- 等差數(shù)列只需要判斷三個(gè)數(shù)字就能確定，我們?cè)O(shè) i-2、i-1 和 i 位置為 a、b、c，當(dāng) c 的加入能形成等差數(shù)列時(shí)，dp[i] 位置的數(shù)（等差子數(shù)組個(gè)數(shù)）需要加上 abc 這個(gè)子數(shù)組，也就是在 dp[i-1] 的基礎(chǔ)上加一即可。得到狀態(tài)轉(zhuǎn)移方程如下，
dp[i] = if(c-b == b-a), dp[i-1]+1 if(c-b != b-a), 0 - 初始化
- 把頭兩位置零，vector 的初始化就是 0，所以可以不用管。
- 填表順序
- 從左往右。
- 返回值
- dp 表內(nèi)所有值的和。
🐎代碼如下：
class Solution {
public:int numberOfArithmeticSlices(vector<int>& nums) {size_t n = nums.size();vector<int> dp(n);size_t sum = 0;for(size_t i = 2; i < n; i++){dp[i] = nums[i]-nums[i-1] == nums[i-1]-nums[i-2] ? dp[i-1] + 1 : 0;sum += dp[i];}return sum;}
};
🥰如果本文對(duì)你有些幫助，歡迎👉 點(diǎn)贊 收藏 關(guān)注，你的支持是對(duì)作者大大莫大的鼓勵(lì)！！(????) 若有差錯(cuò)懇請(qǐng)留言指正~~