Skip to content

Commit 67bae26

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0413. Arithmetic Slices
1 parent 528370c commit 67bae26

File tree

8 files changed

+195
-4
lines changed

8 files changed

+195
-4
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -179,6 +179,7 @@
179179
- [买卖股票的最佳时机含手续费](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README.md)
180180
- [单词拆分](./solution/0100-0199/0139.Word%20Break/README.md)
181181
- [接雨水](./solution/0000-0099/0042.Trapping%20Rain%20Water/README.md)
182+
- [等差数列划分](./solution/0400-0499/0413.Arithmetic%20Slices/README.md)
182183
- [礼物的最大价值](./lcof/面试题47.%20礼物的最大价值/README.md)
183184
- [最小路径和](./solution/0000-0099/0064.Minimum%20Path%20Sum/README.md)
184185
- [解码方法](./solution/0000-0099/0091.Decode%20Ways/README.md)

‎README_EN.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -173,6 +173,7 @@ Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](h
173173
- [Best Time to Buy and Sell Stock with Transaction Fee](./solution/0700-0799/0714.Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Transaction%20Fee/README_EN.md)
174174
- [Word Break](./solution/0100-0199/0139.Word%20Break/README_EN.md)
175175
- [Trapping Rain Water](./solution/0000-0099/0042.Trapping%20Rain%20Water/README_EN.md)
176+
- [Arithmetic Slices](./solution/0400-0499/0413.Arithmetic%20Slices/README_EN.md)
176177
- [Minimum Path Sum](./solution/0000-0099/0064.Minimum%20Path%20Sum/README_EN.md)
177178
- [Decode Ways](./solution/0000-0099/0091.Decode%20Ways/README_EN.md)
178179
- [Longest Increasing Subsequence](./solution/0300-0399/0300.Longest%20Increasing%20Subsequence/README_EN.md)

‎solution/0400-0499/0413.Arithmetic Slices/README.md

Lines changed: 72 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,27 +40,97 @@ A = [1, 2, 3, 4]
4040
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
4141
</pre>
4242

43-
4443
## 解法
4544

4645
<!-- 这里可写通用的实现逻辑 -->
4746

47+
动态规划法。
48+
49+
设 `dp[i]` 表示以 i 结尾的数组构成的等差数列的个数。
50+
51+
如果 `nums[i] + nums[i - 2] ≠ nums[i - 1] * 2`，说明以 i 结尾的数组无法构成等差数列，`dp[i] = 0`；否则 `dp[i] = 1 + dp[i - 1]`。
52+
53+
结果返回 dp 数组所有元素之和即可。
54+
4855
<!-- tabs:start -->
4956

5057
### **Python3**
5158

5259
<!-- 这里可写当前语言的特殊实现逻辑 -->
5360

5461
```python
55-
62+
class Solution:
63+
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
64+
n = len(nums)
65+
dp = [0] * n
66+
for i in range(2, n):
67+
if nums[i] + nums[i - 2] == (nums[i - 1] << 1):
68+
dp[i] = 1 + dp[i - 1]
69+
return sum(dp)
5670
```
5771

5872
### **Java**
5973

6074
<!-- 这里可写当前语言的特殊实现逻辑 -->
6175

6276
```java
77+
class Solution {
78+
public int numberOfArithmeticSlices(int[] nums) {
79+
int n = nums.length;
80+
int[] dp = new int[n];
81+
for (int i = 2; i < n; ++i) {
82+
if (nums[i] + nums[i - 2] == (nums[i - 1] << 1)) {
83+
dp[i] = 1 + dp[i - 1];
84+
}
85+
}
86+
int res = 0;
87+
for (int e : dp) {
88+
res += e;
89+
}
90+
return res;
91+
}
92+
}
93+
```
94+
95+
### **C++**
96+
97+
```cpp
98+
class Solution {
99+
public:
100+
int numberOfArithmeticSlices(vector<int>& nums) {
101+
int n = nums.size();
102+
vector<int> dp(n, 0);
103+
for (int i = 2; i < n; ++i) {
104+
if (nums[i] + nums[i - 2] == (nums[i - 1] * 2)) {
105+
dp[i] = 1 + dp[i - 1];
106+
}
107+
}
108+
int res = 0;
109+
for (auto e : dp) {
110+
res += e;
111+
}
112+
return res;
113+
}
114+
};
115+
```
63116
117+
### **Go**
118+
119+
```go
120+
func numberOfArithmeticSlices(nums []int) int {
121+
n := len(nums)
122+
dp := make([]int, n)
123+
for i := 2; i < n; i++ {
124+
if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
125+
dp[i] = 1 + dp[i-1]
126+
}
127+
}
128+
res := 0
129+
for _, e := range dp {
130+
res += e
131+
}
132+
return res
133+
}
64134
```
65135

66136
### **...**

‎solution/0400-0499/0413.Arithmetic Slices/README_EN.md

Lines changed: 66 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,21 +38,85 @@
3838
<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
3939
</ul>
4040

41-
4241
## Solutions
4342

43+
Dynamic programming.
44+
4445
<!-- tabs:start -->
4546

4647
### **Python3**
4748

4849
```python
49-
50+
class Solution:
51+
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
52+
n = len(nums)
53+
dp = [0] * n
54+
for i in range(2, n):
55+
if nums[i] + nums[i - 2] == (nums[i - 1] << 1):
56+
dp[i] = 1 + dp[i - 1]
57+
return sum(dp)
5058
```
5159

5260
### **Java**
5361

5462
```java
63+
class Solution {
64+
public int numberOfArithmeticSlices(int[] nums) {
65+
int n = nums.length;
66+
int[] dp = new int[n];
67+
for (int i = 2; i < n; ++i) {
68+
if (nums[i] + nums[i - 2] == (nums[i - 1] << 1)) {
69+
dp[i] = 1 + dp[i - 1];
70+
}
71+
}
72+
int res = 0;
73+
for (int e : dp) {
74+
res += e;
75+
}
76+
return res;
77+
}
78+
}
79+
```
80+
81+
### **C++**
82+
83+
```cpp
84+
class Solution {
85+
public:
86+
int numberOfArithmeticSlices(vector<int>& nums) {
87+
int n = nums.size();
88+
vector<int> dp(n, 0);
89+
for (int i = 2; i < n; ++i) {
90+
if (nums[i] + nums[i - 2] == (nums[i - 1] * 2)) {
91+
dp[i] = 1 + dp[i - 1];
92+
}
93+
}
94+
int res = 0;
95+
for (auto e : dp) {
96+
res += e;
97+
}
98+
return res;
99+
}
100+
};
101+
```
55102
103+
### **Go**
104+
105+
```go
106+
func numberOfArithmeticSlices(nums []int) int {
107+
n := len(nums)
108+
dp := make([]int, n)
109+
for i := 2; i < n; i++ {
110+
if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
111+
dp[i] = 1 + dp[i-1]
112+
}
113+
}
114+
res := 0
115+
for _, e := range dp {
116+
res += e
117+
}
118+
return res
119+
}
56120
```
57121

58122
### **...**

‎solution/0400-0499/0413.Arithmetic Slices/Solution.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
class Solution {
2+
public:
3+
int numberOfArithmeticSlices(vector<int>& nums) {
4+
int n = nums.size();
5+
vector<int> dp(n, 0);
6+
for (int i = 2; i < n; ++i) {
7+
if (nums[i] + nums[i - 2] == (nums[i - 1] * 2)) {
8+
dp[i] = 1 + dp[i - 1];
9+
}
10+
}
11+
int res = 0;
12+
for (auto e : dp) {
13+
res += e;
14+
}
15+
return res;
16+
}
17+
};

‎solution/0400-0499/0413.Arithmetic Slices/Solution.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
func numberOfArithmeticSlices(nums []int) int {
2+
n := len(nums)
3+
dp := make([]int, n)
4+
for i := 2; i < n; i++ {
5+
if nums[i]-nums[i-1] == nums[i-1]-nums[i-2] {
6+
dp[i] = 1 + dp[i-1]
7+
}
8+
}
9+
res := 0
10+
for _, e := range dp {
11+
res += e
12+
}
13+
return res
14+
}

‎solution/0400-0499/0413.Arithmetic Slices/Solution.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
class Solution {
2+
public int numberOfArithmeticSlices(int[] nums) {
3+
int n = nums.length;
4+
int[] dp = new int[n];
5+
for (int i = 2; i < n; ++i) {
6+
if (nums[i] + nums[i - 2] == (nums[i - 1] << 1)) {
7+
dp[i] = 1 + dp[i - 1];
8+
}
9+
}
10+
int res = 0;
11+
for (int e : dp) {
12+
res += e;
13+
}
14+
return res;
15+
}
16+
}

‎solution/0400-0499/0413.Arithmetic Slices/Solution.py

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
class Solution:
2+
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
3+
n = len(nums)
4+
dp = [0] * n
5+
for i in range(2, n):
6+
if nums[i] + nums[i - 2] == (nums[i - 1] << 1):
7+
dp[i] = 1 + dp[i - 1]
8+
return sum(dp)

0 commit comments

Comments
 (0)