Skip to content

Commit 85e0e59

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent 4355671 commit 85e0e59

11 files changed

+479
-22
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -160,6 +160,7 @@
160160
* [视频来了！！带你学透回溯算法（理论篇）](https://mp.weixin.qq.com/s/wDd5azGIYWjbU0fdua_qBg)
161161
* [回溯算法：重新安排行程](https://mp.weixin.qq.com/s/3kmbS4qDsa6bkyxR92XCTA)
162162
* [回溯算法：N皇后问题](https://mp.weixin.qq.com/s/lU_QwCMj6g60nh8m98GAWg)
163+
* [回溯算法：解数独](https://mp.weixin.qq.com/s/eWE9TapVwm77yW9Q81xSZQ)
163164

164165

165166
（持续更新中....）
@@ -214,6 +215,7 @@
214215

215216
* 双指针法经典题目
216217
* [0027.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
218+
* [0283.移动零](https://github.com/youngyangyang04/leetcode/blob/master/problems/0283.移动零.md) 和27.移除元素很像
217219
* [0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
218220
* [0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
219221
* [0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
@@ -393,6 +395,7 @@
393395
|[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md) |滑动窗口/队列 |困难| **单调队列**|
394396
|[0242.有效的字母异位词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0242.有效的字母异位词.md) |哈希表 |简单| **哈希**|
395397
|[0257.二叉树的所有路径](https://github.com/youngyangyang04/leetcode/blob/master/problems/0257.二叉树的所有路径.md) |树 |简单| **递归/回溯**|
398+
|[0283.移动零](https://github.com/youngyangyang04/leetcode/blob/master/problems/0283.移动零.md) |数组 |简单| **双指针** 和 27.移除元素 一个套路|
396399
|[0316.去除重复字母](https://github.com/youngyangyang04/leetcode/blob/master/problems/0316.去除重复字母.md) |贪心/字符串 |中等| **单调栈** 这道题目处理的情况比较多，属于单调栈中的难题|
397400
|[0332.重新安排行程](https://github.com/youngyangyang04/leetcode/blob/master/problems/0332.重新安排行程.md) |深度优先搜索/回溯 |中等| **深度优先搜索/回溯算法**|
398401
|[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md) |字符串 |简单| **双指针**|

‎pics/39.组合总和1.png

7.13 KB
Loading

‎pics/51.N皇后.png

3.93 KB
Loading

‎problems/0051.N皇后.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并
4949

5050
下面我用一个3 * 3 的棋牌，将搜索过程抽象为一颗树，如图：
5151

52-
![51.N皇后](https://img-blog.csdnimg.cn/20201116173551789.png)
52+
![51.N皇后](https://img-blog.csdnimg.cn/20201118225433127.png)
5353

5454
从图中，可以看出，二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
5555

@@ -89,7 +89,7 @@ void backtracking(int n, int row, vector<string>& chessboard) {
8989
* 递归终止条件
9090

9191
在如下树形结构中：
92-
![51.N皇后](https://img-blog.csdnimg.cn/20201117165155239.png)
92+
![51.N皇后](https://img-blog.csdnimg.cn/20201118225433127.png)
9393

9494
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。
9595

‎problems/0134.加油站.md

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -5,10 +5,10 @@
55

66
来看一下贪心主要贪在哪里：
77

8-
* 如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
9-
* remain[i] = gas[i]-cost[i]为一天剩下的油，remain[i]，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
8+
1. 如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
9+
2. remain[i] = gas[i]-cost[i]为一天剩下的油，remain[i]，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
1010

11-
* 如果累加的最小值是负数，就要从非0节点出发，从后向前，看哪个节点能这个负数填平。
11+
3. 如果累加的最小值是负数，就要从非0节点出发，从后向前，看哪个节点能这个负数填平。
1212

1313
代码如下：
1414

@@ -25,10 +25,9 @@ public:
2525
min = curSum;
2626
}
2727
}
28-
if (curSum < 0) return -1; // 如果总油量-总消耗都小于零，一定是哪里作为起点都不行
29-
if (min >= 0) return 0; // 从0的位置出发，油箱里的油量没有出现负数，说明从0触发可以跑一圈
30-
// 否则就一定是从其他节点触发
31-
// 从后向前遍历，如果那个节点可以补上从0触发油箱出现负数的情况，那么这个i就是起点
28+
if (curSum < 0) return -1; // 情况1
29+
if (min >= 0) return 0; // 情况2
30+
// 情况3
3231
for (int i = gas.size() - 1; i >= 0; i--) {
3332
int remain = gas[i] - cost[i];
3433
min += remain;
@@ -82,4 +81,8 @@ public:
8281
```
8382

8483

84+
> **我是[程序员Carl](https://github.com/youngyangyang04)，[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，关注后就会发现和「代码随想录」相见恨晚！**
85+
86+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
87+
8588

‎problems/0283.移动零.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
2+
# 思路
3+
4+
做这道题目之前，大家可以做一做[27.移除元素](https://leetcode-cn.com/problems/remove-element/)，我在讲解数组系列的时候针对移除元素写了这篇题解：[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
5+
6+
这道题目，使用暴力的解法，可以两层for循环，模拟数组删除元素（也就是向前覆盖）的过程。
7+
8+
好了，我们说一说双指针法，大家如果对双指针还不熟悉，可以看我的这篇总结[双指针法：总结篇！](https://mp.weixin.qq.com/s/_p7grwjISfMh0U65uOyCjA)。
9+
10+
双指针法在数组移除元素中，可以达到O(n)的时间复杂度，在[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)里已经详细讲解了，那么本题和移除元素其实是一个套路。
11+
12+
**相当于对整个数组移除元素0，然后slowIndex之后都是移除元素0的冗余元素，把这些元素都赋值为0就可以了**。
13+
14+
如动画所示：
15+
16+
<img src='../video/283.移动零.gif' width=600> </img></div>
17+
18+
C++代码如下：
19+
20+
```
21+
class Solution {
22+
public:
23+
void moveZeroes(vector<int>& nums) {
24+
int slowIndex = 0;
25+
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
26+
if (nums[fastIndex] != 0) {
27+
nums[slowIndex++] = nums[fastIndex];
28+
}
29+
}
30+
// 将slowIndex之后的冗余元素赋值为0
31+
for (int i = slowIndex; i < nums.size(); i++) {
32+
nums[i] = 0;
33+
}
34+
}
35+
};
36+
```
37+
> **我是[程序员Carl](https://github.com/youngyangyang04)，[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，关注后就会发现和「代码随想录」相见恨晚！**
38+
39+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
40+

‎problems/leetcode的耗时统计.md

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
2+
还有一些录友会很关心leetcode上的耗时统计。
3+
4+
这个是很不准确的，相同的代码多提交几次，大家就知道怎么回事了。
5+
6+
leetcode上的计时应该是以4ms为单位，有的多提交几次，多个4ms就多击败50%，所以比较夸张，如果程序运行是几百ms的级别，可以看看leetcode上的耗时，因为它的误差10几ms对最终影响不大。
7+
8+
**所以我的题解基本不会写击败百分之多少多少，没啥意义，时间复杂度分析清楚了就可以了**，至于回溯算法不用分析时间复杂度了，都是一样的爆搜，就看谁剪枝厉害了。

0 commit comments

Comments
 (0)