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

Commit293fba4

Browse files
Update
1 parente1792c3 commit293fba4

File tree

6 files changed

+141
-29
lines changed

6 files changed

+141
-29
lines changed

‎README.md‎

Lines changed: 16 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -56,6 +56,8 @@
5656
*[字符串：听说你对KMP有这些疑问？](https://mp.weixin.qq.com/s/mqx6IM2AO4kLZwvXdPtEeQ)
5757
*[字符串：KMP算法还能干这个！](https://mp.weixin.qq.com/s/lR2JPtsQSR2I_9yHbBmBuQ)
5858
*[字符串：前缀表不右移，难道就写不出KMP了？](https://mp.weixin.qq.com/s/p3hXynQM2RRROK5c6X7xfw)
59+
*[字符串：总结篇！](https://mp.weixin.qq.com/s/gtycjyDtblmytvBRFlCZJg)
60+
*[栈与队列：来看看栈和队列不为人知的一面](https://mp.weixin.qq.com/s/VZRjOccyE09aE-MgLbCMjQ)
5961

6062
（持续更新中....）
6163

@@ -66,11 +68,11 @@
6668
这里我总结了各个类型的经典题目，**初学者可以按照如下顺序来刷题**，算法老手可以按照这个list查缺补漏！
6769

6870
* 数组经典题目
69-
*[0035.搜索插入位置](https://github.com/youngyangyang04/leetcode/blob/master/problems/0035.搜索插入位置.md)
70-
*[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md)
71+
*[0035.搜索插入位置](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
72+
*[0027.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
7173
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
72-
*[0209.长度最小的子数组](https://github.com/youngyangyang04/leetcode/blob/master/problems/0209.长度最小的子数组.md)
73-
*[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)
74+
*[0209.长度最小的子数组](https://mp.weixin.qq.com/s/UrZynlqi4QpyLlLhBPglyg)
75+
*[0059.螺旋矩阵II](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
7476

7577
* 链表经典题目
7678
*[0203.移除链表元素](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
@@ -94,16 +96,16 @@
9496

9597
* 循环不变量原则
9698
*[0035.搜索插入位置](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
97-
*[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)
99+
*[0059.螺旋矩阵II](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
98100

99101
* 字符串经典题目
100-
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
101-
*[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)
102-
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
103-
*[0151.翻转字符串里的单词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0151.翻转字符串里的单词.md)
104-
*延伸左旋转字符串（剑指offer上的题目）
105-
*[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md)
106-
*[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)
102+
*[0344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
103+
*[0541.反转字符串II](https://mp.weixin.qq.com/s/XGSk1GyPWhfqj2g7Cb1Vgw)
104+
*[剑指Offer05.替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
105+
*[0151.翻转字符串里的单词](https://mp.weixin.qq.com/s/X3qpi2v5RSp08mO-W5Vicw)
106+
*[剑指Offer58-II.左旋转字符串](https://mp.weixin.qq.com/s/PmcdiWSmmccHAONzU0ScgQ)
107+
*[0028.实现strStr()](https://mp.weixin.qq.com/s/Gk9FKZ9_FSWLEkdGrkecyg)
108+
*[0459.重复的子字符串](https://mp.weixin.qq.com/s/lR2JPtsQSR2I_9yHbBmBuQ)
107109

108110
* 双指针法经典题目
109111
*[0027.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
@@ -113,7 +115,7 @@
113115
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
114116
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
115117
*[0344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
116-
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
118+
*[剑指Offer05.替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
117119

118120
* 栈与队列经典题目
119121
*[0232.用栈实现队列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0232.用栈实现队列.md)
@@ -420,6 +422,7 @@ backtracking() {
420422
|[0101.对称二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0101.对称二叉树.md)|树|简单|**递归****迭代/队列/栈**|
421423
|[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)|树|中等|**广度优先搜索/队列**|
422424
|[0104.二叉树的最大深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0104.二叉树的最大深度.md)|树|简单|**递归****迭代/队列/BFS**|
425+
|[0107.二叉树的层次遍历II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0107.二叉树的层次遍历II.md)|树|简单|**广度优先搜索/队列/BFS**|
423426
|[0110.平衡二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0110.平衡二叉树.md)|树|简单|**递归**|
424427
|[0111.二叉树的最小深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0111.二叉树的最小深度.md)|树|简单|**递归****队列/BFS**|
425428
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|

‎problems/0001.两数之和.md‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,13 @@ https://leetcode-cn.com/problems/two-sum/
2222

2323
很明显暴力的解法是两层for循环查找，时间复杂度是O(n^2)。
2424

25-
使用哈希法最为合适，之前已经介绍过，数组和set在哈希法中的应用，那么来看一下使用数组和set来做哈希法的局限。
25+
建议大家做这道题目之前，先做一下这两道
26+
*[242. 有效的字母异位词](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)
27+
*[349. 两个数组的交集](https://mp.weixin.qq.com/s/N9iqAchXreSVW7zXUS4BVA)
28+
29+
[242. 有效的字母异位词](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig) 这道题目是用数组作为哈希表来解决哈希问题，[349. 两个数组的交集](https://mp.weixin.qq.com/s/N9iqAchXreSVW7zXUS4BVA)这道题目是通过set作为哈希表来解决哈希问题。
30+
31+
本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。
2632

2733
* 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
2834
* set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下表位置，因为要返回x 和 y的下表。所以set 也不能用。
@@ -39,10 +45,14 @@ C++中map，有三种类型：
3945

4046
std::unordered_map 底层实现为哈希表，std::map 和std::multimap 的底层实现是红黑树。
4147

42-
同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。更多哈希表的理论知识请看[关于哈希表，你该了解这些！](https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA)。
48+
同理，std::map 和std::multimap 的key也是有序的（这个问题也经常作为面试题，考察对语言容器底层的理解）。 更多哈希表的理论知识请看[关于哈希表，你该了解这些！](https://mp.weixin.qq.com/s/g8N6WmoQmsCUw3_BaWxHZA)。
4349

4450
**这道题目中并不需要key有序，选择std::unordered_map 效率更高！**
4551

52+
解题思路动画如下：
53+
54+
<videosrc='../video/1.两数之和.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
55+
4656
#C++代码
4757

4858
```

‎problems/0232.用栈实现队列.md‎

Lines changed: 61 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,32 +1,65 @@
11
##题目地址
22
https://leetcode-cn.com/problems/implement-queue-using-stacks/
33

4-
##思路
4+
>工作上一定没人这么搞，但是考察对栈、队列理解程度的好题
55
6-
使用**两个栈 一个输入栈，一个输出栈**，这里要注意输入栈和输出栈的关系。
6+
#232. 用栈实现队列
77

8-
下面动画模拟一下队列的执行过程如下：
8+
使用栈实现队列的下列操作：
99

10-
执行语句：
10+
push(x) -- 将一个元素放入队列的尾部。
11+
pop() -- 从队列首部移除元素。
12+
peek() -- 返回队列首部的元素。
13+
empty() -- 返回队列是否为空。
14+
 
15+
16+
示例:
17+
18+
```
19+
MyQueue queue = new MyQueue();
1120
queue.push(1);
1221
queue.push(2);
13-
queue.pop();**注意此时的输出栈的操作**
14-
queue.push(3);
15-
queue.push(4);
16-
queue.pop();
17-
queue.pop();**注意此时的输出栈的操作**
18-
queue.pop();
19-
queue.empty();
22+
queue.peek(); // 返回 1
23+
queue.pop(); // 返回 1
24+
queue.empty(); // 返回 false
25+
```
26+
27+
说明:
28+
29+
* 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
30+
* 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
31+
* 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
32+
33+
#思路
34+
35+
这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。
36+
37+
使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈**一个输入栈，一个输出栈**，这里要注意输入栈和输出栈的关系。
38+
39+
下面动画模拟以下队列的执行过程如下：
40+
41+
执行语句：
42+
queue.push(1);
43+
queue.push(2);
44+
queue.pop();**注意此时的输出栈的操作**
45+
queue.push(3);
46+
queue.push(4);
47+
queue.pop();
48+
queue.pop();**注意此时的输出栈的操作**
49+
queue.pop();
50+
queue.empty();
2051

2152
<videosrc='../video/232.用栈实现队列版本2.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
2253

2354
在push数据的时候，只要数据放进输入栈就好，**但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入）**，再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。
2455

2556
最后如何判断队列为空呢？**如果进栈和出栈都为空的话，说明模拟的队列为空了。**
2657

58+
在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。
59+
2760
代码如下：
2861

29-
##C++代码
62+
#C++代码
3063

3164
```
3265
class MyQueue {
@@ -44,7 +77,7 @@ public:
4477
4578
/** Removes the element from in front of queue and returns that element. */
4679
int pop() {
47-
//只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
80+
//只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据）
4881
if (stOut.empty()) {
4982
// 从stIn导入数据直到stIn为空
5083
while(!stIn.empty()) {
@@ -71,5 +104,19 @@ public:
71104
};
72105
73106
```
74-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
107+
108+
#拓展
109+
110+
可以看出peek()的实现，直接复用了pop()。
111+
112+
再多说一些代码开发上的习惯问题，在工业级别代码开发中，最忌讳的就是 实现一个类似的函数，直接把代码粘过来改一改就完事了。
113+
114+
这样的项目代码会越来越乱，**一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题！（踩过坑的人自然懂）**
115+
116+
工作中如果发现某一个功能自己要经常用，同事们可能也会用到，自己就花点时间把这个功能抽象成一个好用的函数或者工具类，不仅自己方便，也方面了同事们。
117+
118+
同事们就会逐渐认可你的工作态度和工作能力，自己的口碑都是这么一点一点积累起来的！在同事圈里口碑起来了之后，你就发现自己走上了一个正循环，以后的升职加薪才少不了你！哈哈哈
119+
120+
121+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
75122

‎problems/0459.重复的子字符串.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,8 @@ https://leetcode-cn.com/problems/repeated-substring-pattern/
2626

2727
这又是一道标准的KMP的题目。
2828

29+
如果KMP还不够了解，可以看我的这个视频[帮你把KMP算法学个通透！B站](https://www.bilibili.com/video/BV1PD4y1o7nd/)
30+
2931
我们在[字符串：都来看看KMP的看家本领！](https://mp.weixin.qq.com/s/Gk9FKZ9_FSWLEkdGrkecyg)里提到了，在一个串中查找是否出现过另一个串，这是KMP的看家本领。
3032

3133
那么寻找重复子串怎么也涉及到KMP算法了呢？
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
##题目地址
2+
3+
##思路
4+
5+
这道题目就是考察二叉树的层序遍历。
6+
7+
二叉树的层序遍历还有这两道题目，大家可以先做一下，其实都是一个思路
8+
9+
*[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md) 单纯的层寻遍历
10+
* |[0107.二叉树的层次遍历II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0107.二叉树的层次遍历II.md) 相对于[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)就是把每一层倒叙输出就可以了
11+
12+
想要学习二叉树的深度遍历可以看这里[彻底吃透前中后序递归法](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/)。
13+
14+
而本题呢，就是把每一层的结果求一个和，然后取平均值。
15+
16+
层序遍历一个二叉树，需要借用一个辅助数据结构队列来实现，**队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。**
17+
18+
使用队列实现广度优先遍历，动画如下：
19+
20+
<videosrc='../video/102二叉树的层序遍历.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
21+
22+
这样就实现了层序从左到右遍历二叉树。
23+
24+
代码如下：（这份代码也可以作为二叉树层序遍历的模板）。
25+
26+
##C++代码
27+
28+
```
29+
class Solution {
30+
public:
31+
vector<double> averageOfLevels(TreeNode* root) {
32+
queue<TreeNode*> que;
33+
if (root != NULL) que.push(root);
34+
vector<double> result;
35+
while (!que.empty()) {
36+
int size = que.size();
37+
double sum = 0; // 统计每一层的和
38+
for (int i = 0; i < size; i++) { // 这里一定要使用固定大小size，不要使用que.size()
39+
TreeNode* node = que.front();
40+
que.pop();
41+
sum += node->val;
42+
if (node->left) que.push(node->left);
43+
if (node->right) que.push(node->right);
44+
}
45+
result.push_back(sum / size); // 将每一层放进结果集
46+
}
47+
return result;
48+
}
49+
};
50+
```

‎video/1.两数之和.mp4‎

1.16 MB
Binary file not shown.

0 commit comments

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