-
Notifications
You must be signed in to change notification settings - Fork 110
/
413. Arithmetic Slices.cpp
172 lines (155 loc) · 4.97 KB
/
413. Arithmetic Slices.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//DP
//Runtime: 212 ms, faster than 5.27% of C++ online submissions for Arithmetic Slices.
//Memory Usage: 149.1 MB, less than 6.25% of C++ online submissions for Arithmetic Slices.
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
vector<vector<int>> dp(n, vector(n, INT_MIN));
int ans = 0;
for(int w = 2; w <= n; w++){
for(int l = 0; l+w-1 < n; l++){
int r = l+w-1;
//base case
if(w == 2){
// cout << l << ", " << r << endl;
dp[l][r] = A[r] - A[l];
}else{
if((dp[l+1][r] != INT_MIN) && (dp[l+1][r] == dp[l][r-1])){
/*
[l...r] is valid only if
windows of size w-1 are valid,
and the two windows' common differences are same
*/
dp[l][r] = dp[l+1][r]+1;
}
if(dp[l][r] != INT_MIN){
// cout << l << ", " << r << endl;
ans++;
}
}
}
}
return ans;
}
};
//Approach #2 Better Brute Force
//time: O(N^2), space: O(1)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int ans = 0;
int n = A.size();
for(int l = 0; l+2 < n; l++){
int d = A[l+1] - A[l];
//looking at [l...l+2], [l...l+3], [l...l+4], [l...n-1]
for(int r = l+2; r < n; r++){
//only check last pair to determine if a slice is valid
if(A[r] - A[r-1] == d){
ans++;
}else{
//skip all [l...r+1], ... [l...n-1] if [l...r] is invalid
break;
}
}
}
return ans;
}
};
//Recursion?
//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Arithmetic Slices.
//Memory Usage: 8 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
//time: O(N), space: O(N)
class Solution {
public:
int sum = 0;
int slices(vector<int>& A, int i){
if(i < 2) return 0;
int ap = 0;
if(A[i] - A[i-1] == A[i-1] - A[i-2]){
/*
A[0...i]'s subsequence's count is that of A[0...i-1] + 1
*/
ap = 1 + slices(A, i-1);
sum += ap;
}else{
slices(A, i-1);
}
// cout << i << ", " << ap << ", " << sum << endl;
return ap;
};
int numberOfArithmeticSlices(vector<int>& A) {
slices(A, A.size()-1);
return sum;
}
};
//1-D DP
//Runtime: 4 ms, faster than 45.89% of C++ online submissions for Arithmetic Slices.
//Memory Usage: 7.5 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
//time: O(N), space: O(N)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
vector<int> dp(n);
int ans = 0;
for(int r = 2; r < n; r++){
if(A[r] - A[r-1] == A[r-1] - A[r-2]){
/*
dp[r-1] : count of arithmetic slices ending at r-1
suppose these are [r-k...r-1], ..., [r-3...r-1]
dp[r] : [r-k...r], ..., [r-3...r], its count is then be dp[r-1]+1
*/
dp[r] = dp[r-1] + 1;
ans += dp[r];
}
}
return ans;
}
};
//O(1) space DP
//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Arithmetic Slices.
//Memory Usage: 7.4 MB, less than 100.00% of C++ online submissions for Arithmetic Slices.
//time: O(N), space: O(1)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
int dp = 0;
int ans = 0;
for(int r = 2; r < n; r++){
if(A[r] - A[r-1] == A[r-1] - A[r-2]){
//we only need last dp value
dp += 1;
ans += dp;
}else{
//need to reset dp value!
dp = 0;
}
}
return ans;
}
};
//Approach #6 Using Formula
//time: O(N), space: O(1)
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
int n = A.size();
int count = 0;
int ans = 0;
for(int r = 2; r < n; r++){
if(A[r] - A[r-1] == A[r-1] - A[r-2]){
//length of consecutive arithmetic slice is count+2
count++;
}else{
//an slice of length count+2 can generate (count+1) * count/2 differenct subslices
ans += (count+1) * count/2;
//need to reset its value!
count = 0;
}
}
//handle last iteration
return (ans += (count+1) * count/2);
}
};