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

Commitd989622

Browse files
Update
1 parentf913dc3 commitd989622

19 files changed

+476
-40
lines changed

‎README.md

Lines changed: 13 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,13 @@
2828
*[算法分析中的空间复杂度，你真的会了么？](https://mp.weixin.qq.com/s/sXjjnOUEQ4Gf5F9QCRzy7g)
2929
*[刷leetcode的时候，究竟什么时候可以使用库函数，什么时候不要使用库函数，过来人来说一说](https://leetcode-cn.com/circle/article/E1Kjzn/)
3030

31+
* 数组
32+
*[必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
33+
*[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
34+
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
35+
*[数组：滑动窗口拯救了你](https://mp.weixin.qq.com/s/UrZynlqi4QpyLlLhBPglyg)
36+
*[数组：这个循环可以转懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
37+
*[数组：总结篇](https://mp.weixin.qq.com/s/LIfQFRJBH5ENTZpvixHEmg)
3138
* 链表
3239
*[关于链表，你该了解这些！](https://mp.weixin.qq.com/s/ntlZbEdKgnFQKZkSUAOSpQ)
3340
*[链表：听说用虚拟头节点会方便很多？](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
@@ -46,13 +53,6 @@
4653
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
4754
*[双指针法：一样的道理，能解决四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
4855

49-
* 数组
50-
*[必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
51-
*[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
52-
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
53-
*[数组：滑动窗口拯救了你](https://mp.weixin.qq.com/s/UrZynlqi4QpyLlLhBPglyg)
54-
*[数组：这个循环可以转懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
55-
*[数组：总结篇](https://mp.weixin.qq.com/s/LIfQFRJBH5ENTZpvixHEmg)
5656

5757
* 字符串
5858
*[字符串：这道题目，使用库函数一行代码搞定](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
@@ -110,6 +110,9 @@
110110
*[二叉树：递归函数究竟什么时候需要返回值，什么时候不要返回值？](https://mp.weixin.qq.com/s/6TWAVjxQ34kVqROWgcRFOg)
111111
*[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)
112112
*[二叉树：构造一棵最大的二叉树](https://mp.weixin.qq.com/s/1iWJV6Aov23A7xCF4nV88w)
113+
*[本周小结！（二叉树系列三）](https://mp.weixin.qq.com/s/JLLpx3a_8jurXcz6ovgxtg)
114+
*[二叉树：合并两个二叉树](https://mp.weixin.qq.com/s/3f5fbjOFaOX_4MXzZ97LsQ)
115+
*[二叉树：二叉搜索树登场！](https://mp.weixin.qq.com/s/vsKrWRlETxCVsiRr8v_hHg)
113116

114117

115118

@@ -233,6 +236,7 @@
233236
|[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)| 数组|中等|**双指针**|
234237
|[0020.有效的括号](https://github.com/youngyangyang04/leetcode/blob/master/problems/0020.有效的括号.md)| 栈|简单|**栈**|
235238
|[0021.合并两个有序链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0021.合并两个有序链表.md)|链表|简单|**模拟**|
239+
|[0024.两两交换链表中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0024.两两交换链表中的节点.md)|链表|中等|**模拟**|
236240
|[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)|数组|简单|**暴力****快慢指针/快慢指针**|
237241
|[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md)|数组|简单|**暴力****双指针/快慢指针/双指针**|
238242
|[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md)|字符串|简单|**KMP**|
@@ -326,7 +330,8 @@
326330
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|
327331
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)|链表|中等|**模拟**|
328332
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md)|孤岛问题|中等|**bfs****dfs**|
329-
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|栈|简单|**栈**|
333+
|[1002.查找常用字符](https://github.com/youngyangyang04/leetcode/blob/master/problems/1002.查找常用字符.md)|栈|简单|**栈**|
334+
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|哈希表|简单|**哈希表/数组**|
330335
|[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**双指针**|
331336
|[ 剑指Offer58-I.翻转单词顺序](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**模拟/双指针**|
332337
|[剑指Offer58-II.左旋转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer58-II.左旋转字符串.md)|字符串|简单|**反转操作**|

‎pics/1002.查找常用字符.png

118 KB
Loading
44.4 KB
Loading
61.5 KB
Loading
60.4 KB
Loading
35.5 KB
Loading

‎pics/42.接雨水4.png

37 KB
Loading

‎pics/42.接雨水5.png

63.6 KB
Loading

‎pics/98.验证二叉搜索树.png

51 KB
Loading

‎problems/0015.三数之和.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,8 @@ https://leetcode-cn.com/problems/3sum/
2222

2323
#思路
2424

25+
**注意[0， 0， 0， 0] 这组数据**
26+
2527
##哈希解法
2628

2729
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，其实这个思路是正确的，但是我们有一个非常棘手的问题，就是题目中说的不可以包含重复的三元组。
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
2+
3+
##题目地址
4+
5+
##思路
6+
7+
这道题目正常模拟就可以了。
8+
9+
建议使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。
10+
11+
对虚拟头结点的操作，还不熟悉的话，可以看这篇[链表：听说用虚拟头节点会方便很多？](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)。
12+
13+
接下来就是交换相邻两个元素了，**此时一定要画图，不画图，操作多个指针很容易乱，而且要操作的先后顺序**
14+
15+
初始时，cur指向虚拟头结点，然后进行如下三步：
16+
17+
<imgsrc='../pics/24.两两交换链表中的节点1.png'width=600> </img></div>
18+
19+
操作之后，链表如下：
20+
21+
22+
<imgsrc='../pics/24.两两交换链表中的节点2.png'width=600> </img></div>
23+
24+
看这个可能就更直观一些了：
25+
26+
27+
<imgsrc='../pics/24.两两交换链表中的节点3.png'width=600> </img></div>
28+
29+
对应的C++代码实现如下：
30+
31+
```
32+
class Solution {
33+
public:
34+
ListNode* swapPairs(ListNode* head) {
35+
ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
36+
dummyHead->next = head; // 将虚拟头结点指向head，这样方面后面做删除操作
37+
ListNode* cur = dummyHead;
38+
while(cur->next != nullptr && cur->next->next != nullptr) {
39+
ListNode* tmp = cur->next; // 记录临时节点
40+
ListNode* tmp1 = cur->next->next->next; // 记录临时节点
41+
42+
cur->next = cur->next->next; // 步骤一
43+
cur->next->next = tmp; // 步骤二
44+
cur->next->next->next = tmp1; // 步骤三
45+
46+
cur = cur->next->next; // cur移动两位，准备下一轮交换
47+
}
48+
return dummyHead->next;
49+
}
50+
};
51+
```
52+
时间复杂度：O(n)
53+
空间复杂度：O(1)
54+
55+
##拓展
56+
57+
**这里还是说一下，大家不必太在意leetcode上执行用时，打败多少多少用户，这个就是一个玩具，非常不准确。**
58+
59+
做题的时候自己能分析出来时间复杂度就可以了，至于leetcode上执行用时，大概看一下就行。
60+
61+
上面的代码我第一次提交执行用时8ms，打败6.5%的用户，差点吓到我了。
62+
63+
心想应该没有更好的方法了吧，也就O(n)的时间复杂度，重复提交几次，这样了：
64+
65+
<imgsrc='../pics/24.两两交换链表中的节点.png'width=600> </img></div>
66+
67+
所以，不必过于在意leetcode上这个统计。
68+
69+
70+

‎problems/0028.实现strStr().md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -108,7 +108,7 @@ next数组就是一个前缀表（prefix table）。
108108

109109
如动画所示：
110110

111-
<imgsrc='../../media/video/KMP精讲1.gif'width=600> </img></div>
111+
<imgsrc='../video/KMP详解1.gif'width=600> </img></div>
112112

113113
动画里，我特意把 子串`aa` 标记上了，这是有原因的，大家先注意一下，后面还会说道。
114114

@@ -169,7 +169,7 @@ next数组就是一个前缀表（prefix table）。
169169

170170
再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示：
171171

172-
<imgsrc='../../media/video/KMP精讲2.gif'width=600> </img></div>
172+
<imgsrc='../video/KMP精讲2.gif'width=600> </img></div>
173173

174174
找到的不匹配的位置， 那么此时我们要看它的前一个字符的前缀表的数值是多少。
175175

@@ -311,7 +311,7 @@ void getNext(int* next, const string& s){
311311

312312
代码构造next数组的逻辑流程动画如下：
313313

314-
<imgsrc='../../media/video/KMP精讲3.gif'width=600> </img></div>
314+
<imgsrc='../video/KMP精讲3.gif'width=600> </img></div>
315315

316316

317317
得到了next数组之后，就要用这个来做匹配了。

‎problems/0042.接雨水.md

Lines changed: 66 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -105,4 +105,69 @@ public:
105105

106106
单调栈究竟如何做呢，得画一个图，不太好理解
107107

108-
按照列来算的，遇到相同的怎么办。
108+
##使用单调栈内元素的顺序
109+
110+
从打到小还是从小打到呢
111+
112+
从栈底到栈头（元素从栈头弹出）是从大到小的顺序，因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子。
113+
114+
如图：
115+
116+
<imgsrc='../pics/42.接雨水4.png'width=600> </img></div>
117+
118+
119+
##遇到相同高度的柱子怎么办。
120+
121+
遇到相同的元素，更新栈内下表，就是将栈里元素（旧下标）弹出，讲新元素（新下标）加入栈中。
122+
123+
例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
124+
125+
因为我们要求宽度的时候 如果遇到相容高度的柱子，需要使用最右边的柱子来计算宽度。
126+
127+
如图所示：
128+
129+
130+
<imgsrc='../pics/42.接雨水5.png'width=600> </img></div>
131+
132+
133+
134+
135+
136+
没有必要 stack<pair<int, int>> st; // 高度，下表
137+
138+
139+
放进去元素，相同怎么办，相同也没事，放里面就行，计算结果也是0
140+
141+
**真的难**
142+
143+
```
144+
class Solution {
145+
public:
146+
int trap(vector<int>& height) {
147+
if (height.size() <= 2) return 0;
148+
stack<int> st; // 存着下标，计算的时候用下标对应的柱子高度
149+
st.push(0);
150+
int sum = 0;
151+
for (int i = 1; i < height.size(); i++) {
152+
if (height[i] < height[st.top()]) {
153+
st.push(i);
154+
} if (height[i] == height[st.top()]) { // 如果相等则更新栈内下表，例如 5 5 1 7 这种情况
155+
st.pop();
156+
st.push(i);
157+
} else {
158+
while (!st.empty() && height[i] > height[st.top()]) { // 注意这里是while
159+
int mid = st.top();
160+
st.pop();
161+
if (!st.empty()) {
162+
int h = min(height[st.top()], height[i]) - height[mid];
163+
int w = i - st.top() - 1 ; // 注意求宽度这里不加1，而是减一
164+
sum += h * w;
165+
}
166+
}
167+
st.push(i);
168+
}
169+
}
170+
return sum;
171+
}
172+
};
173+
```

0 commit comments

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