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

Commit494b9c0

Browse files
Update
1 parentcaf33c6 commit494b9c0

File tree

5 files changed

+82
-14
lines changed

5 files changed

+82
-14
lines changed

‎README.md‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@
4646
*[数组：这个循环可以转懵很多人！](https://mp.weixin.qq.com/s/KTPhaeqxbMK9CxHUUgFDmg)
4747
*[数组：总结篇](https://mp.weixin.qq.com/s/LIfQFRJBH5ENTZpvixHEmg)
4848
*[字符串：这道题目，使用库函数一行代码搞定](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
49+
*[字符串：简单的反转还不够！](https://mp.weixin.qq.com/s/XGSk1GyPWhfqj2g7Cb1Vgw)
4950
* 精选链表相关的面试题
5051
* 精选字符串相关的面试题
5152
* 精选栈与队列相关的面试题
@@ -108,7 +109,7 @@
108109
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
109110
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
110111
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
111-
*[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
112+
*[0344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
112113
*[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
113114

114115
* 栈与队列经典题目

‎problems/0486.预测赢家.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -237,7 +237,7 @@ for (int i = 0; i < nums.size(); i++) {
237237

238238
接下来就要推导公式了，首先要知道最终求是dp[0][nums.size() - 1]是否大于等于0，也就是求dp[0][nums.size() - 1] 至关重要。
239239

240-
从下图中，可以看出在推导方程的时候一定要从右上角向下推导，而且矩阵左半部分根本不用管！
240+
从下图中，可以看出在推导方程的时候一定要从右下角向上推导，而且矩阵左半部分根本不用管！
241241

242242
<imgsrc='../pics/486.预测赢家1.png'width=600> </img></div>
243243

‎problems/0841.钥匙和房间.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,7 @@ https://leetcode-cn.com/problems/keys-and-rooms/
33

44
##思路
55

6-
其实这道题的本质就是判断各个房间所连成的有向图，是否存在孤岛，如果有孤岛，说明不用访问所有的房间。
6+
其实这道题的本质就是判断各个房间所连成的有向图，说明不用访问所有的房间。
77

88
如图所示：
99

@@ -13,7 +13,7 @@ https://leetcode-cn.com/problems/keys-and-rooms/
1313

1414
示例2中，就不能访问所有房间，从图中就可以看出，房间2是一个孤岛，我们从0出发，无论怎么遍历，都访问不到房间2。
1515

16-
认清本质问题之后，**就知道孤岛问题，使用 广度优先搜索(BFS) 还是 深度优先搜索(DFS) 都是可以的。**
16+
认清本质问题之后，**使用 广度优先搜索(BFS) 还是 深度优先搜索(DFS) 都是可以的。**
1717

1818
代码如下：
1919

‎problems/剑指Offer05.替换空格.md‎

Lines changed: 77 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,23 +1,45 @@
11
##题目地址
22
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
33

4-
##思路
4+
>遇到对字符串或者数组做填充或删除的操作时，都要想想从后向前操作怎么样。
55
6-
如果想把这道题目做到极致，就不要只用额外的辅助空间，先扩充数组到每个空格替换成"%20"之后的大小
7-
然后从后向前替换空格，双指针法：
6+
#题目：剑指Offer 05.替换空格
87

9-
思路如下：
10-
<videosrc="../video/替换空格.mp4"controls="controls"width="640"height="320"autoplay="autoplay">
11-
Your browser does not support the video tag.
12-
</video>
8+
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
139

14-
时间复杂度，空间复杂度均超过100%的用户
10+
示例 1：
11+
输入：s = "We are happy."
12+
输出："We%20are%20happy."
13+
14+
#思路
15+
16+
如果想把这道题目做到极致，就不要只用额外的辅助空间了！
17+
18+
首先扩充数组到每个空格替换成"%20"之后的大小。
19+
20+
然后从后向前替换空格，也就是双指针法，过程如下：
21+
22+
i指向新长度的末尾，j指向旧长度的末尾。
23+
24+
<imgsrc='../video/替换空格.gif'width=600> </img></div>
25+
26+
有同学问了，为什么要从后向前填充，从前向后填充不行么？
27+
28+
从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。
29+
30+
**其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。**
31+
32+
这么做有两个好处：
33+
34+
1. 不用申请新数组。
35+
2. 从后向前填充元素，避免了从前先后填充元素要来的 每次添加元素都要将添加元素之后的所有元素向后移动。
36+
37+
时间复杂度，空间复杂度均超过100%的用户。
1538

1639
<imgsrc='../pics/剑指Offer05.替换空格.png'width=600> </img></div>
1740

1841
##C++代码
1942

20-
2143
```
2244
class Solution {
2345
public:
@@ -48,5 +70,50 @@ public:
4870
};
4971
5072
```
51-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
73+
时间复杂度：O(n)
74+
空间复杂度：O(1)
75+
76+
此时算上本题，我们已经做了七道双指针相关的题目了分别是：
77+
78+
*[27.移除元素](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
79+
*[15.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
80+
*[18.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
81+
*[206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
82+
*[142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
83+
*[344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
84+
85+
#拓展
86+
87+
这里也给大家拓展一下字符串和数组有什么差别，
88+
89+
字符串是若干字符组成的有限序列，也可以理解为是一个字符数组，但是很多语言对字符串做了特殊的规定，接下来我来说一说C/C++中的字符串。
90+
91+
在C语言中，把一个字符串存入一个数组时，也把结束符 '\0'存入数组，并以此作为该字符串是否结束的标志。
92+
93+
例如这段代码：
94+
95+
```
96+
char a[5] = "asd";
97+
for (int i = 0; a[i] != '\0'; i++) {
98+
}
99+
```
100+
101+
在C++中，提供一个string类，string类会提供 size接口，可以用来判断string类字符串是否结束，就不用'\0'来判断是否结束。
102+
103+
例如这段代码:
104+
105+
```
106+
string a = "asd";
107+
for (int i = 0; i < a.size(); i++) {
108+
}
109+
```
110+
111+
那么vector< char > 和 string 又有什么区别呢？
112+
113+
其实在基本操作上没有区别，但是 string提供更多的字符串处理的相关接口，例如string 重载了+，而vector却没有。
114+
115+
所以想处理字符串，我们还是会定义一个string类型。
116+
117+
118+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
52119

‎video/替换空格.gif‎

1.14 MB
Loading

0 commit comments

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