Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit41656d1

Browse files
Update
1 parent3e39d7f commit41656d1

8 files changed

+366
-23
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -281,6 +281,7 @@
281281
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
282282
|[0141.环形链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0141.环形链表.md)|链表|简单|**快慢指针/双指针**|
283283
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)|链表|中等|**快慢指针/双指针**|
284+
|[0143.重排链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0143.重排链表.md)|链表|中等|**快慢指针/双指针** 也可以用数组，双向队列模拟，考察链表综合操作的好题|
284285
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)|树|中等|**递归****迭代/栈**|
285286
|[0145.二叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0145.二叉树的后序遍历.md)|树|困难|**递归****迭代/栈**|
286287
|[0151.翻转字符串里的单词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0151.翻转字符串里的单词.md)|字符串|中等|**模拟/双指针**|
@@ -339,6 +340,7 @@
339340
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|
340341
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)|链表|中等|**模拟**|
341342
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md)|孤岛问题|中等|**bfs****dfs**|
343+
|[0844.比较含退格的字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0844.比较含退格的字符串.md)|字符串|简单|**栈****双指针优化** 使用栈的思路但没有必要使用栈|
342344
|[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md)|数组|中等|**双指针**|
343345
|[1002.查找常用字符](https://github.com/youngyangyang04/leetcode/blob/master/problems/1002.查找常用字符.md)|栈|简单|**栈**|
344346
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|哈希表|简单|**哈希表/数组**|

‎pics/143.重排链表.png

115 KB
Loading

‎problems/0042.接雨水.md

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -170,7 +170,13 @@ public:
170170

171171
那么本题使用单调栈有如下几个问题：
172172

173-
1. 使用单调栈内元素的顺序
173+
1. 首先单调栈是按照行方向来计算雨水，如图：
174+
175+
<imgsrc='../pics/42.接雨水2.png'width=600> </img></div>
176+
177+
知道这一点，后面的就可以理解了。
178+
179+
2. 使用单调栈内元素的顺序
174180

175181
从大到小还是从小打到呢？
176182

@@ -183,7 +189,7 @@ public:
183189
<imgsrc='../pics/42.接雨水4.png'width=600> </img></div>
184190

185191

186-
2. 遇到相同高度的柱子怎么办。
192+
3. 遇到相同高度的柱子怎么办。
187193

188194
遇到相同的元素，更新栈内下表，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
189195

@@ -197,7 +203,7 @@ public:
197203
<imgsrc='../pics/42.接雨水5.png'width=600> </img></div>
198204

199205

200-
3. 栈里要保存什么数值
206+
4. 栈里要保存什么数值
201207

202208
是用单调栈，其实是通过 长 * 宽 来计算雨水面积的。
203209

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
2+
#链接
3+
4+
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
5+
6+
##思路
7+
8+
```
9+
class Solution {
10+
public:
11+
int largestRectangleArea(vector<int>& heights) {
12+
int sum = 0;
13+
for (int i = 0; i < heights.size(); i++) {
14+
int left = i;
15+
int right = i;
16+
for (; left >= 0; left--) {
17+
if (heights[left] < heights[i]) break;
18+
}
19+
for (; right < heights.size(); right++) {
20+
if (heights[right] < heights[i]) break;
21+
}
22+
int w = right - left - 1;
23+
int h = heights[i];
24+
sum = max(sum, w * h);
25+
}
26+
return sum;
27+
}
28+
};
29+
```
30+
31+
如上代码并不能通过leetcode，超时了，因为时间复杂度是O(n^2)。

‎problems/0143.重排链表.md

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
2+
#思路
3+
4+
本篇将给出三种C++实现的方法
5+
6+
* 数组模拟
7+
* 双向队列模拟
8+
* 直接分割链表
9+
10+
##方法一
11+
12+
把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表。
13+
14+
代码如下：
15+
16+
```
17+
class Solution {
18+
public:
19+
void reorderList(ListNode* head) {
20+
vector<ListNode*> vec;
21+
ListNode* cur = head;
22+
if (cur == nullptr) return;
23+
while(cur != nullptr) {
24+
vec.push_back(cur);
25+
cur = cur->next;
26+
}
27+
cur = head;
28+
int i = 1;
29+
int j = vec.size() - 1;
30+
int count = 0; // 计数，用来取前面，取后面
31+
while (i <= j) {
32+
if (count % 2 == 0) {
33+
cur->next = vec[j];
34+
j--;
35+
} else {
36+
cur->next = vec[i];
37+
i++;
38+
}
39+
cur = cur->next;
40+
count++;
41+
}
42+
if (vec.size() % 2 == 0) {
43+
cur->next = vec[i];
44+
cur = cur->next;
45+
}
46+
cur->next = nullptr; // 注意结尾
47+
}
48+
};
49+
```
50+
51+
##方法二
52+
53+
把链表放进双向队列，然后通过双向队列一前一后弹出数据，来构造新的链表。这种方法比操作数组容易一些，不用双指针模拟一前一后了
54+
```
55+
class Solution {
56+
public:
57+
void reorderList(ListNode* head) {
58+
deque<ListNode*> que;
59+
ListNode* cur = head;
60+
if (cur == nullptr) return;
61+
62+
while(cur->next != nullptr) {
63+
que.push_back(cur->next);
64+
cur = cur->next;
65+
}
66+
67+
cur = head;
68+
int count = 0;
69+
ListNode* node;
70+
while(que.size()) {
71+
if (count % 2 == 0) {
72+
node = que.back();
73+
que.pop_back();
74+
} else {
75+
node = que.front();
76+
que.pop_front();
77+
}
78+
count++;
79+
cur->next = node;
80+
cur = cur->next;
81+
}
82+
cur->next = nullptr;
83+
}
84+
};
85+
```
86+
87+
##方法三
88+
89+
将链表分割成两个链表，然后把第二个链表反转，之后在通过两个链表拼接成新的链表。
90+
91+
如图：
92+
93+
<imgsrc='../pics/143.重排链表.png'width=600> </img></div>
94+
95+
这种方法，比较难，平均切割链表，看上去很简单，真正代码写的时候有很多细节，同时两个链表最后拼装整一个新的链表也有一些细节需要注意！
96+
97+
代码如下：
98+
99+
```
100+
class Solution {
101+
private:
102+
ListNode* reverseList(ListNode* head) {
103+
ListNode* temp; // 保存cur的下一个节点
104+
ListNode* cur = head;
105+
ListNode* pre = NULL;
106+
while(cur) {
107+
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
108+
cur->next = pre; // 翻转操作
109+
// 更新pre 和 cur指针
110+
pre = cur;
111+
cur = temp;
112+
}
113+
return pre;
114+
}
115+
116+
public:
117+
void reorderList(ListNode* head) {
118+
if (head == nullptr) return;
119+
// 使用快慢指针法，将链表分成长度均等的两个链表head1和head2
120+
// 如果总链表长度为奇数，则head1相对head2多一个节点
121+
ListNode* fast = head;
122+
ListNode* slow = head;
123+
while (fast && fast->next && fast->next->next) {
124+
fast = fast->next->next;
125+
slow = slow->next;
126+
}
127+
ListNode* head1 = head;
128+
ListNode* head2;
129+
head2 = slow->next;
130+
slow->next = nullptr;
131+
132+
// 对head2进行翻转
133+
head2 = reverseList(head2);
134+
135+
// 将head1和head2交替生成新的链表head
136+
ListNode* cur1 = head1;
137+
ListNode* cur2 = head2;
138+
ListNode* cur = head;
139+
cur1 = cur1->next;
140+
int count = 0;
141+
while (cur1 && cur2) {
142+
if (count % 2 == 0) {
143+
cur->next = cur2;
144+
cur2 = cur2->next;
145+
} else {
146+
cur->next = cur1;
147+
cur1 = cur1->next;
148+
}
149+
count++;
150+
cur = cur->next;
151+
}
152+
if (cur2 != nullptr) {
153+
cur->next = cur2;
154+
}
155+
if (cur1 != nullptr) {
156+
cur->next = cur1;
157+
}
158+
}
159+
};
160+
```

‎problems/0219.存在重复元素II.md

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,22 @@ public:
3030
};
3131
```
3232

33+
代码精简之后
34+
35+
```
36+
class Solution {
37+
public:
38+
bool containsNearbyDuplicate(vector<int>& nums, int k) {
39+
unordered_map<int, int> map;
40+
for (int i = 0; i < nums.size(); i++) {
41+
if (map.find(nums[i]) != map.end() && i - map[nums[i]] <= k) return true;
42+
map[nums[i]] = i;
43+
}
44+
return false;
45+
}
46+
};
47+
```
48+
3349

3450
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
3551

‎problems/0222.完全二叉树的节点个数.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@ https://leetcode-cn.com/problems/count-complete-tree-nodes/
2121

2222
依然可以使用递归法和迭代法来解决。
2323

24-
这道题目的递归法和求二叉树的深度写法类似， 而迭代法：二叉树层序遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
24+
这道题目的递归法和求二叉树的深度写法类似， 而迭代法，[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
2525

2626
递归遍历的顺序依然是后序（左右中）。
2727

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp