Skip to content

Commit 4c121e6

Browse files
author
lucifer
committed
feat: cpp
1 parent ac5f912 commit 4c121e6

File tree

4 files changed

+145
-57
lines changed

4 files changed

+145
-57
lines changed

‎problems/61.Rotate-List.md

Lines changed: 82 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -26,27 +26,30 @@ https://leetcode-cn.com/problems/rotate-list/
2626
```
2727

2828
## 快慢指针法
29+
2930
### 前置知识
30-
- 求单链表的倒数第N个节点
31+
32+
- 求单链表的倒数第 N 个节点
3133

3234
### 思路一
35+
3336
1. 采用快慢指
3437
2. 快指针与慢指针都以每步一个节点的速度向后遍历
35-
3. 快指针比慢指针先走N步
36-
4. 当快指针到达终点时，慢指针正好是倒数第N个节点
38+
3. 快指针比慢指针先走 N 步
39+
4. 当快指针到达终点时，慢指针正好是倒数第 N 个节点
3740

3841
### 思路一代码
3942

4043
- 伪代码
4144

4245
```js
43-
快指针 = head
44-
慢指针 = head
45-
while(快指针.next){
46-
if(N-- <= 0){
47-
慢指针 = 慢指针.next
48-
}
49-
快指针 = 快指针.next
46+
快指针 = head;
47+
慢指针 = head;
48+
while (快指针.next) {
49+
if (N-- <= 0) {
50+
慢指针 = 慢指针.next;
51+
}
52+
快指针 = 快指针.next;
5053
}
5154
```
5255

@@ -55,31 +58,33 @@ while(快指针.next){
5558
JS Code:
5659

5760
```js
58-
let slow = fast = head
59-
while(fast.next){
60-
if(k-- <= 0){
61-
slow = slow.next
62-
}
63-
fast = fast.next
61+
let slow = (fast = head);
62+
while (fast.next) {
63+
if (k-- <= 0) {
64+
slow = slow.next;
65+
}
66+
fast = fast.next;
6467
}
6568
```
6669

6770
### 思路二
68-
1. 获取单链表的倒数第N + 1 与倒数第N个节点
69-
2. 将倒数第N + 1个节点的next指向null
70-
3. 将链表尾节点的next指向head
71-
4. 返回倒数第N个节点
7271

73-
例如链表 A -> B -> C -> D -> E右移2位，依照上述步骤为：
72+
1. 获取单链表的倒数第 N + 1 与倒数第 N 个节点
73+
2. 将倒数第 N + 1 个节点的 next 指向 null
74+
3. 将链表尾节点的 next 指向 head
75+
4. 返回倒数第 N 个节点
76+
77+
例如链表 A -> B -> C -> D -> E 右移 2 位，依照上述步骤为：
78+
7479
1. 获取节点 C 与 D
7580
2. A -> B -> C -> null, D -> E
7681
3. D -> E -> A -> B -> C -> nul
77-
4. 返回节点D
82+
4. 返回节点 D
7883

79-
> 注意：假如链表节点长度为len，
80-
则右移K位与右移动 k % len的效果是一样的
81-
就像是长度为1000米的环形跑道，
82-
你跑1100米与跑100米到达的是同一个地点
84+
> 注意：假如链表节点长度为 len，
85+
> 则右移 K 位与右移动 k % len 的效果是一样的
86+
> 就像是长度为 1000 米的环形跑道，
87+
> 你跑 1100 米与跑 100 米到达的是同一个地点
8388
8489
### 思路二代码
8590

@@ -94,30 +99,31 @@ while(fast.next){
9499
return 倒数第k个节点
95100
```
96101

97-
- 语言支持: JS, JAVA, Python, Go, PHP
102+
- 语言支持: JS, JAVA, Python, CPP, Go, PHP
98103

99104
JS Code:
100105

101106
```js
102-
var rotateRight = function(head, k) {
103-
if(!head || !head.next) return head
104-
let count = 0, now = head
105-
while(now){
106-
now = now.next
107-
count++
107+
var rotateRight = function (head, k) {
108+
if (!head || !head.next) return head;
109+
let count = 0,
110+
now = head;
111+
while (now) {
112+
now = now.next;
113+
count++;
114+
}
115+
k = k % count;
116+
let slow = (fast = head);
117+
while (fast.next) {
118+
if (k-- <= 0) {
119+
slow = slow.next;
108120
}
109-
k = k % count
110-
let slow = fast = head
111-
while(fast.next){
112-
if(k-- <= 0){
113-
slow = slow.next
114-
}
115-
fast = fast.next
116-
}
117-
fast.next = head
118-
let res = slow.next
119-
slow.next = null
120-
return res
121+
fast = fast.next;
122+
}
123+
fast.next = head;
124+
let res = slow.next;
125+
slow.next = null;
126+
return res;
121127
};
122128
```
123129

@@ -169,11 +175,11 @@ class Solution:
169175
i = -1
170176
p2 = head
171177
i += 1
172-
178+
173179
while p2.next:
174180
p1 = p1.next
175181
p2 = p2.next
176-
182+
177183
if p1.next:
178184
tmp = p1.next
179185
else:
@@ -183,6 +189,35 @@ class Solution:
183189
return tmp
184190
```
185191

192+
CPP Code:
193+
194+
```cpp
195+
class Solution {
196+
int getLength(ListNode *head) {
197+
int len = 0;
198+
for (; head; head = head->next, ++len);
199+
return len;
200+
}
201+
public:
202+
ListNode* rotateRight(ListNode* head, int k) {
203+
if (!head) return NULL;
204+
int len = getLength(head);
205+
k %= len;
206+
if (k == 0) return head;
207+
auto p = head, q = head;
208+
while (k--) q = q->next;
209+
while (q->next) {
210+
p = p->next;
211+
q = q->next;
212+
}
213+
auto h = p->next;
214+
q->next = head;
215+
p->next = NULL;
216+
return h;
217+
}
218+
};
219+
```
220+
186221
Go Code:
187222
188223
```go

‎problems/62.unique-paths.md

Lines changed: 18 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -105,15 +105,14 @@ Python3 Code:
105105

106106
```python
107107
class Solution:
108-
108+
109109
@lru_cache
110110
def uniquePaths(self, m: int, n: int) -> int:
111111
if m == 1 or n == 1:
112112
return 1
113113
return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)
114114
```
115115

116-
117116
## 关键点
118117

119118
- 排列组合原理
@@ -123,7 +122,7 @@ class Solution:
123122

124123
## 代码
125124

126-
代码支持 JavaScript，Python3
125+
代码支持 JavaScript，Python3, CPP
127126

128127
JavaScript Code:
129128

@@ -166,6 +165,22 @@ class Solution:
166165
return dp[n - 1]
167166
```
168167

168+
CPP Code:
169+
170+
```cpp
171+
class Solution {
172+
public:
173+
int uniquePaths(int m, int n) {
174+
vector<int> dp(n + 1, 0);
175+
dp[n - 1] = 1;
176+
for (int i = m - 1; i >= 0; --i) {
177+
for (int j = n - 1; j >= 0; --j) dp[j] += dp[j + 1];
178+
}
179+
return dp[0];
180+
}
181+
};
182+
```
183+
169184
**复杂度分析**
170185
171186
- 时间复杂度：$$O(M * N)$$

‎problems/63.unique-paths-ii.md

Lines changed: 24 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -76,9 +76,9 @@ class Solution:
7676
if i == 0 and j == 0: return 1
7777
return dfs(i - 1, j) + dfs(i, j - 1)
7878
return dfs(m - 1, n - 1)
79-
```
80-
81-
> lru_cache(None) 可以看成一个哈希表，key 是函数参数， value 是函数的返回值，因此纯函数都可使用 lru_cache(None) 通过空间换时间的方式来优化性能。
79+
```
80+
81+
> lru_cache(None) 可以看成一个哈希表，key 是函数参数， value 是函数的返回值，因此纯函数都可使用 lru_cache(None) 通过空间换时间的方式来优化性能。
8282
8383
代码大概是：
8484

@@ -129,7 +129,7 @@ class Solution:
129129

130130
## 代码
131131

132-
代码支持 Python3
132+
代码支持: Python3, CPP
133133

134134
Python3 Code:
135135

@@ -152,6 +152,26 @@ class Solution:
152152
return dp[-1]
153153
```
154154

155+
CPP Code:
156+
157+
```cpp
158+
class Solution {
159+
public:
160+
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
161+
int M = obstacleGrid.size(), N = obstacleGrid[0].size();
162+
vector<int> memo(N, 0);
163+
memo[N - 1] = 1;
164+
for (int i = M - 1; i >= 0; --i) {
165+
for (int j = N - 1; j >= 0; --j) {
166+
if (obstacleGrid[i][j] == 1) memo[j] = 0;
167+
else memo[j] += j == N - 1 ? 0 : memo[j + 1];
168+
}
169+
}
170+
return memo[0];
171+
}
172+
};
173+
```
174+
155175
**复杂度分析**
156176
157177
- 时间复杂度：$$O(M * N)$$

‎problems/66.plus-one.md

Lines changed: 21 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -101,7 +101,7 @@ result[1] ...... result[result.length - 1] = 0
101101
102102
## 代码
103103
104-
代码支持：Python3，JS, Go, PHP
104+
代码支持：Python3，JS, CPP, Go, PHP
105105
106106
Python3 Code：
107107
@@ -133,6 +133,24 @@ var plusOne = function (digits) {
133133
};
134134
```
135135

136+
CPP Code:
137+
138+
```cpp
139+
class Solution {
140+
public:
141+
vector<int> plusOne(vector<int>& A) {
142+
int i = A.size() - 1, carry = 1;
143+
for (; i >= 0 && carry; --i) {
144+
carry += A[i];
145+
A[i] = carry % 10;
146+
carry /= 10;
147+
}
148+
if (carry) A.insert(begin(A), carry);
149+
return A;
150+
}
151+
};
152+
```
153+
136154
Go code:
137155
138156
```go
@@ -179,8 +197,8 @@ class Solution {
179197

180198
**复杂度分析**
181199

182-
- 时间复杂度：O(N)
183-
- 空间复杂度：O(1)
200+
- 时间复杂度：$$O(N)$$
201+
- 空间复杂度：$$O(1)$$
184202

185203
## 相关题目
186204

0 commit comments

Comments
 (0)