C++ 中的算术切片
c++server side programmingprogramming
假设我们有一个数字序列，如果它至少包含三个元素，并且任何两个连续元素之间的差相同，则该序列称为算术序列。例如，这些是算术序列:[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], A[p + 1], ..., A[Q - 1], A[Q] 是算术的，则数组 A 的切片 (P, Q) 称为算术的。该函数应该找到数组 A 中的算术切片的数量。
因此，如果输入为 [1,2,3,4]，则输出将为 3，因为元素为 [1,2,3], [2,3,4] 和 [1,2,3,4]
为了解决这个问题，我们将遵循以下步骤 −
- ret := 0, n := A 的大小，创建一个大小为 n 的数组 dp
- for i in range 2 to n – 1
- if a[i] – a[i – 1] = a[i – 1] – a[i – 2]，则
- dp[i] := 1 + dp[i - 1]
- 将 ret 增加 dp[i]
- if a[i] – a[i – 1] = a[i – 1] – a[i – 2]，则
- return 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
