資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++中的算術切片
假設我們有一串數字，如果它至少包含三個元素，並且任何兩個連續元素之間的差值相同，則稱其為算術序列。例如，這些是算術序列：[1, 3, 5, 7, 9]，[7, 7, 7, 7]，[3, -1, -5, -9]，但以下序列不是算術序列：[1, 1, 2, 5, 7]
現在給定一個包含N個數字的零索引陣列A。給定陣列的切片是任何整數對(P, Q)，使得0 <= P < Q < N。這裡陣列A的切片(P, Q)被稱為算術切片，如果序列：A[P]，A[p + 1]，...，A[Q - 1]，A[Q]是算術的。該函式應該找到陣列A中算術切片的數量。
因此，如果輸入類似於[1,2,3,4]，則輸出將為3，因為元素為[1,2,3]，[2,3,4]和[1,2,3,4]
為了解決這個問題，我們將遵循以下步驟：
- ret := 0, n := A的大小，建立一個大小為n的陣列dp
- 對於範圍從2到n – 1的i
- 如果a[i] – a[i – 1] = a[i – 1] – a[i – 2]，則
- dp[i] := 1 + dp[i - 1]
- 將ret增加dp[i]
- 如果a[i] – a[i – 1] = a[i – 1] – a[i – 2]，則
- 返回ret
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ret = 0;
int n = A.size();
vector <int> dp(n);
for(int i = 2; i < n; i++){
if(A[i] - A[i - 1] == A[i - 1] - A[i - 2]){
dp[i] = 1 + dp[i - 1];
ret += dp[i];
}
}
return ret;
}
};
main(){
vector<int> v = {1,2,3,4};
Solution ob;
cout << (ob.numberOfArithmeticSlices(v));
}輸入
[1,2,3,4]
輸出
3
更新於：2020年4月30日
177 次瀏覽
廣告