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

Commit8f905ff

Browse files
Update
1 parente5a672e commit8f905ff

9 files changed

+182
-40
lines changed

‎README.md

Lines changed: 14 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,8 @@
4040
*[哈希表：这道题目我做过？](https://mp.weixin.qq.com/s/sYZIR4dFBrw_lr3eJJnteQ)
4141
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
4242
*[双指针法：一样的道理，能解决四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
43+
*[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
44+
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
4345
* 精选链表相关的面试题
4446
* 精选字符串相关的面试题
4547
* 精选栈与队列相关的面试题
@@ -82,6 +84,10 @@
8284
*[0219.存在重复元素II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0219.存在重复元素II.md)
8385
* 0220.存在重复元素III
8486

87+
* 循环不变量原则
88+
*[0035.搜索插入位置](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
89+
*[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)
90+
8591
* 字符串经典题目
8692
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
8793
*[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)
@@ -92,11 +98,12 @@
9298
*[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)
9399

94100
* 双指针法经典题目
95-
*[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
96-
*[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
101+
*[0027.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
102+
*[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
103+
*[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
97104
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
98-
*[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
99-
*[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
105+
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
106+
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
100107
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
101108
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
102109

@@ -400,7 +407,7 @@ int countNodes(TreeNode* root) {
400407
|[0205.同构字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0205.同构字符串.md)|哈希表|简单|**哈希**|
401408
|[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)|链表|简单|**双指针法****递归**|
402409
|[0209.长度最小的子数组](https://github.com/youngyangyang04/leetcode/blob/master/problems/0209.长度最小的子数组.md)|数组|中等|**暴力****滑动窗口**|
403-
|[0216.组合总和III](https://github.com/youngyangyang04/leetcode/blob/master/problems/0216.组合总和III.md)|数组/回溯|中等|**回溯**|
410+
|[0216.组合总和III](https://github.com/youngyangyang04/leetcode/blob/master/problems/0216.组合总和III.md)|数组/回溯|中等|**回溯算法**|
404411
|[0219.存在重复元素II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0219.存在重复元素II.md)| 哈希表|简单|**哈希**|
405412
|[0222.完全二叉树的节点个数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0222.完全二叉树的节点个数.md)| 树|简单|**递归**|
406413
|[0225.用队列实现栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0225.用队列实现栈.md)| 队列|简单|**队列**|
@@ -409,6 +416,7 @@ int countNodes(TreeNode* root) {
409416
|[0237.删除链表中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0237.删除链表中的节点.md)|链表|简单|**原链表移除****添加虚拟节点** 递归|
410417
|[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md)|滑动窗口/队列|困难|**单调队列**|
411418
|[0242.有效的字母异位词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0242.有效的字母异位词.md)|哈希表|简单|**哈希**|
419+
|[0332.重新安排行程](https://github.com/youngyangyang04/leetcode/blob/master/problems/0332.重新安排行程.md)|深度优先搜索/回溯|中等|**深度优先搜索/回溯算法**|
412420
|[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)|字符串|简单|**双指针**|
413421
|[0347.前K个高频元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0347.前K个高频元素.md)|哈希/堆/优先级队列|中等|**哈希/优先级队列**|
414422
|[0349.两个数组的交集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0349.两个数组的交集.md)|哈希表|简单|**哈希**|
@@ -418,7 +426,7 @@ int countNodes(TreeNode* root) {
418426
|[0450.删除二叉搜索树中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0450.删除二叉搜索树中的节点.md)|树|中等|**递归**|
419427
|[0454.四数相加II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0454.四数相加II.md)|哈希表|中等|**哈希**|
420428
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
421-
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯**|
429+
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法**|
422430
|[0541.反转字符串II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0541.反转字符串II.md)|字符串|简单|**模拟**|
423431
|[0575.分糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0575.分糖果.md)|哈希表|简单|**哈希**|
424432
|[0617.合并二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0617.合并二叉树.md)|树|简单|**递归****迭代**|
22.2 KB
Loading

‎problems/0017.电话号码的字母组合.md

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -39,17 +39,17 @@ https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
3939
**那么在来讲一讲回溯法，回溯法的模板如下：**
4040

4141
```
42-
回溯函数() {
42+
backtracking() {
4343
if (终止条件) {
4444
存放结果;
4545
}
4646
4747
for (枚举同一个位置的所有可能性，可以想成节点孩子的数量) {
48-
递归，处理下一个孩子;
49-
(递归的下面就是回溯的过程);
48+
递归，处理节点;
49+
backtracking();
50+
回溯，撤销处理结果
5051
}
5152
}
52-
5353
```
5454

5555
按照这个模板，不难写出如下代码：

‎problems/0018.四数之和.md

Lines changed: 16 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,22 @@ https://leetcode-cn.com/problems/4sum/
4040

4141
而[四数相加II](https://mp.weixin.qq.com/s/Ue8pKKU5hw_m-jPgwlHcbA)是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于本题还是简单了不少！
4242

43-
大家解决一下这两道题目就能感受出来难度的差异。
43+
我们来回顾一下，几道题目使用了双指针法。
44+
45+
双指针法将时间复杂度O(n^2)的解法优化为 O(n)的解法。也就是降一个数量级，题目如下：
46+
*[0027.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
47+
*[15.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
48+
*[18.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
49+
50+
双指针来记录前后指针实现链表反转：
51+
52+
*[206.反转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
53+
54+
使用双指针来确定有环：
55+
56+
*[142题.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
57+
58+
双指针法在数组和链表中还有很多应用，后面还会介绍到。
4459

4560
#C++代码
4661
```

‎problems/0027.移除元素.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -39,7 +39,7 @@ https://leetcode-cn.com/problems/remove-element/
3939

4040
删除过程如下：
4141

42-
<imgsrc='../../World/Writing/leetcode/video/27.移除元素-暴力解法.gif'width=600> </img></div>
42+
<imgsrc='../video/27.移除元素-暴力解法.gif'width=600> </img></div>
4343

4444
很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。
4545

@@ -73,7 +73,7 @@ public:
7373

7474
删除过程如下：
7575

76-
<imgsrc='../../World/Writing/leetcode/video/27.移除元素-双指针法.gif'width=600> </img></div>
76+
<imgsrc='../video/27.移除元素-双指针法.gif'width=600> </img></div>
7777

7878
**双指针法（快慢指针法）在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法。**
7979

‎problems/0059.螺旋矩阵II.md

Lines changed: 51 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,66 @@
11
>笔者在BAT从事技术研发多年，利用工作之余重刷leetcode，更多原创文章请关注公众号「代码随想录」。
22
3-
##题目地址
3+
#题目地址
44
https://leetcode-cn.com/problems/spiral-matrix-ii/
55

6-
##思路
6+
>一进循环深似海，从此offer是路人
77
8-
模拟顺时针画矩阵的过程
8+
#题目59.螺旋矩阵II
99

10-
填充上行从左到右
11-
填充右列从上到下
12-
填充下行从右到左
13-
填充左列从下到上
10+
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
1411

15-
在模拟的过程中最重要的思想是**保持画每一条边的原则一致，即每次都是左闭右开的原则**，如果所示
12+
示例:
13+
14+
输入: 3
15+
输出:
16+
[
17+
[ 1, 2, 3],
18+
[ 8, 9, 4],
19+
[ 7, 6, 5]
20+
]
21+
22+
#思路
23+
24+
这道题目可以说在面试中出现频率较高的题目，**本题并不涉及到什么算法，就是模拟过程，但却十分考察对代码的掌控能力。**
25+
26+
要如何画出这个螺旋排列的正方形矩阵呢？
27+
28+
相信很多同学刚开始做这种题目的时候，上来就是一波判断猛如虎。
29+
30+
结果运行的时候各种问题，然后开始各种修修补补，最后发现改了这里哪里有问题，改了那里这里又跑不起来了。
31+
32+
大家还记得我们在这篇文章[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)中讲解了二分法，提到如果要写出正确的二分法一定要坚持**循环不变量原则**。
33+
34+
而求解本题依然是要坚持循环不变量原则。
35+
36+
模拟顺时针画矩阵的过程:
37+
38+
* 填充上行从左到右
39+
* 填充右列从上到下
40+
* 填充下行从右到左
41+
* 填充左列从下到上
42+
43+
由外向内一圈一圈这么画下去。
44+
45+
可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是**一进循环深似海，从此offer是路人**。
46+
47+
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开又闭的原则，这样这一圈才能按照统一的规则画下来。
48+
49+
那么我按照左闭右开的原则，来画一圈，大家看一下：
1650

1751
<imgsrc='../pics/螺旋矩阵.png'width=600> </img></div>
1852

19-
很多同学，做这道题目之所以一直写不好，代码越写越乱，就是因为 在画每一条边的时候，没有保证统一原则
53+
这里每一种颜色，代表一条边，我们遍历的长度，可以看出每一个拐角处的处理规则，拐角处让给新的一条边来继续画。
54+
55+
这也是坚持了每条边左闭右开的原则。
56+
57+
一些同学做这道题目之所以一直写不好，代码越写越乱。
58+
59+
就是因为在画每一条边的时候，一会左开又闭，一会左闭右闭，一会又来左闭右开，岂能不乱。
2060

21-
例如：模拟矩阵上边的时候 左闭右开，然后模拟矩阵右列的时候又开始了左闭又闭，那岂能不乱
61+
代码如下，已经详细注释了每一步的目的，可以看出while循环里判断的情况是很多的，代码里处理的原则也是统一的左闭右开。
2262

23-
##解法
63+
#C++代码
2464

2565
```C++
2666
classSolution {

‎problems/0209.长度最小的子数组.md

Lines changed: 52 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,18 +1,24 @@
11
##题目地址
22
https://leetcode-cn.com/problems/minimum-size-subarray-sum/
33

4-
##思路
5-
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2) 。
4+
>滑动窗口拯救了你
65
7-
还可以使用滑动窗口的细想来做这道题。所谓滑动窗口，**就是不断的调节子序列的起始位置，从而得出我们要想的结果**
6+
#题目209.长度最小的子数组
87

9-
这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下动画效果：
8+
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
109

11-
<videosrc='../video/209.长度最小的子数组.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
10+
示例：
1211

13-
代码如下：
12+
输入：s = 7, nums =[2,3,1,2,4,3]
13+
输出：2
14+
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
15+
16+
17+
#暴力解法
18+
19+
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是O(n^2) 。
1420

15-
##暴力解法
21+
代码如下：
1622

1723
```
1824
class Solution {
@@ -27,7 +33,6 @@ public:
2733
sum += nums[j];
2834
if (sum >= s) { // 一旦发现子序列和超过了s，更新result
2935
subLength = j - i + 1; // 取子序列的长度
30-
// result取 result和subLength最小的那个
3136
result = result < subLength ? result : subLength;
3237
break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
3338
}
@@ -38,12 +43,45 @@ public:
3843
}
3944
};
4045
```
46+
时间复杂度：O(n^2)
47+
空间复杂度：O(1)
48+
49+
#滑动窗口
50+
51+
接下来就开始介绍数组操作中另一个重要的方法：**滑动窗口**。
52+
53+
所谓滑动窗口，**就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果**。
54+
55+
这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
56+
57+
<imgsrc='../video/209.长度最小的子数组.gif'width=600> </img></div>
4158

42-
##滑动窗口
59+
最后找到 4，3 是最短距离。
60+
61+
其实从动画中可以发现滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
62+
63+
在本题中实现滑动窗口，主要确定如下三点：
64+
65+
* 窗口内是什么？
66+
* 如何移动窗口的起始位置？
67+
* 如何移动窗口的结束位置？
68+
69+
窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
70+
71+
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
72+
73+
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
74+
75+
解题的关键在于 窗口的起始位置如何移动，如图所示：
4376

4477
<imgsrc='../pics/leetcode_209.png'width=600> </img></div>
78+
79+
可以发现**滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。**
80+
81+
82+
#C++滑动窗口代码
83+
4584
```
46-
// 滑动窗口
4785
class Solution {
4886
public:
4987
int minSubArrayLen(int s, vector<int>& nums) {
@@ -56,7 +94,6 @@ public:
5694
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
5795
while (sum >= s) {
5896
subLength = (j - i + 1); // 取子序列的长度
59-
// result取 result和subLength最小的那个
6097
result = result < subLength ? result : subLength;
6198
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
6299
}
@@ -67,5 +104,8 @@ public:
67104
};
68105
```
69106

70-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
107+
时间复杂度：O(n)
108+
空间复杂度：O(1)
109+
110+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
71111

‎problems/0332.重新安排行程.md

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -94,15 +94,15 @@ class Solution {
9494
private:
9595
// unordered_map<出发城市, map<到达城市, 航班次数>> targets
9696
unordered_map<string, map<string, int>> targets;
97-
bool backtracking(int ticketNum,int index,vector<string>& result) {
98-
if (index == ticketNum + 1) {
97+
bool backtracking(int ticketNum, vector<string>& result) {
98+
if (result.size() == ticketNum + 1) {
9999
return true;
100100
}
101101
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
102102
if (target.second > 0 ) { // 使用int字段来记录到达城市是否使用过了
103103
result.push_back(target.first);
104104
target.second--;
105-
if (backtracking(ticketNum,index + 1,result)) return true;
105+
if (backtracking(ticketNum, result)) return true;
106106
result.pop_back();
107107
target.second++;
108108
}
@@ -116,9 +116,10 @@ public:
116116
targets[vec[0]][vec[1]]++; // 记录映射关系
117117
}
118118
result.push_back("JFK");
119-
backtracking(tickets.size(),1,result);
119+
backtracking(tickets.size(), result);
120120
return result;
121121
}
122122
};
123+
123124
```
124125

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
##题目地址
2+
https://leetcode-cn.com/problems/robot-return-to-origin/
3+
4+
##思路
5+
6+
这道题目还是挺简单的，大家不要想复杂了，一波哈希法又一波图论算法啥的，哈哈。
7+
8+
其实就是，x，y坐标，初始为0，然后：
9+
* if (moves[i] == 'U') y++;
10+
* if (moves[i] == 'D') y--;
11+
* if (moves[i] == 'L') x--;
12+
* if (moves[i] == 'R') x++;
13+
14+
最后判断一下x，y是否回到了(0, 0)位置就可以了。
15+
16+
如图所示：
17+
<imgsrc='../pics/657.机器人能否返回原点.png'width=600> </img></div>
18+
19+
##C++代码
20+
21+
```
22+
class Solution {
23+
public:
24+
bool judgeCircle(string moves) {
25+
int x = 0, y = 0;
26+
for (int i = 0; i < moves.size(); i++) {
27+
if (moves[i] == 'U') y++;
28+
if (moves[i] == 'D') y--;
29+
if (moves[i] == 'L') x--;
30+
if (moves[i] == 'R') x++;
31+
}
32+
if (x == 0 && y == 0) return true;
33+
return false;
34+
}
35+
};
36+
```
37+
38+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

0 commit comments

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