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

Commit7011c07

Browse files
Update
1 parent7ff0587 commit7011c07

File tree

7 files changed

+154
-17
lines changed

7 files changed

+154
-17
lines changed

‎README.md‎

Lines changed: 13 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -28,12 +28,18 @@
2828
*[这六道哈希表相关的面试题，你一定要会！](https://mp.weixin.qq.com/s/nxuWv5cUhCPSbAdIHtWgSg)
2929
*[关于链表，你该了解这些！](https://mp.weixin.qq.com/s/ntlZbEdKgnFQKZkSUAOSpQ)
3030
*[刷leetcode的时候，究竟什么时候可以使用库函数，什么时候不要使用库函数，过来人来说一说](https://leetcode-cn.com/circle/article/E1Kjzn/)
31+
*[链表：听说用虚拟头节点会方便很多？](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
32+
*[链表：一道题目考察了常见的五个操作！](https://mp.weixin.qq.com/s/Cf95Lc6brKL4g2j8YyF3Mg)
33+
*[链表：听说过两天反转链表又写不出来了？](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
34+
*[链表：环找到了，那入口呢？](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
35+
*[哈希表：可以拿数组当哈希表来用，但哈希值不要太大](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)
3136
* 精选链表相关的面试题
3237
* 精选字符串相关的面试题
3338
* 精选栈与队列相关的面试题
3439
* 精选二叉树相关的面试题
3540
* 精选递归与回溯面试题
3641

42+
3743
（持续更新中....）
3844

3945
#LeetCode 刷题攻略
@@ -50,10 +56,10 @@
5056
*[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)
5157

5258
* 链表经典题目
53-
*[0203.移除链表元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0203.移除链表元素.md)
54-
*[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)
55-
*[0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
56-
*[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
59+
*[0203.移除链表元素](https://mp.weixin.qq.com/s/slM1CH5Ew9XzK93YOQYSjA)
60+
*[0707.设计链表](https://mp.weixin.qq.com/s/Cf95Lc6brKL4g2j8YyF3Mg)
61+
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
62+
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
5763

5864
* 哈希表经典题目
5965
*[0242.有效的字母异位词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0242.有效的字母异位词.md)
@@ -335,6 +341,7 @@ int countNodes(TreeNode* root) {
335341
|---|---| ---| ---|
336342
|[0001.两数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0001.两数之和.md)| 数组|简单|**暴力****哈希**|
337343
|[0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)| 数组|中等|**双指针****哈希**|
344+
|[0017.电话号码的字母组合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0017.电话号码的字母组合.md)| 回溯|中等|**回溯**|
338345
|[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)| 数组|中等|**双指针**|
339346
|[0020.有效的括号](https://github.com/youngyangyang04/leetcode/blob/master/problems/0020.有效的括号.md)| 栈|简单|**栈**|
340347
|[0021.合并两个有序链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0021.合并两个有序链表.md)|链表|简单|**模拟**|
@@ -345,6 +352,7 @@ int countNodes(TreeNode* root) {
345352
|[0053.最大子序和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0053.最大子序和.md)|数组|简单|**暴力****贪心** 动态规划 分治|
346353
|[0059.螺旋矩阵II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0059.螺旋矩阵II.md)|数组|中等|**模拟**|
347354
|[0083.删除排序链表中的重复元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0083.删除排序链表中的重复元素.md)|链表|简单|**模拟**|
355+
|[0093.复原IP地址](https://github.com/youngyangyang04/leetcode/blob/master/problems/0093.复原IP地址)|回溯|中等|**回溯**|
348356
|[0094.二叉树的中序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0094.二叉树的中序遍历.md)|树|中等|**递归****迭代/栈**|
349357
|[0098.验证二叉搜索树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0098.验证二叉搜索树.md)|树|中等|**递归**|
350358
|[0100.相同的树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0100.相同的树.md)|树|简单|**递归**|
@@ -353,6 +361,7 @@ int countNodes(TreeNode* root) {
353361
|[0104.二叉树的最大深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0104.二叉树的最大深度.md)|树|简单|**递归****迭代/队列/BFS**|
354362
|[0110.平衡二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0110.平衡二叉树.md)|树|简单|**递归**|
355363
|[0111.二叉树的最小深度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0111.二叉树的最小深度.md)|树|简单|**递归****队列/BFS**|
364+
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
356365
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)|链表|中等|**快慢指针/双指针**|
357366
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)|树|中等|**递归****迭代/栈**|
358367
|[0145.二叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0145.二叉树的后序遍历.md)|树|困难|**递归****迭代/栈**|

‎pics/93_复原IP地址.png‎

43.4 KB
Loading

‎problems/0083.删除排序链表中的重复元素.md‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -36,5 +36,5 @@ public:
3636
};
3737
```
3838

39-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
39+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
4040

‎problems/0093.复原IP地址.md‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
##题目地址
2+
https://leetcode-cn.com/problems/restore-ip-addresses/
3+
4+
##思路
5+
6+
7+
##C++代码
8+
9+
```
10+
class Solution {
11+
private:
12+
vector<string> result;// 记录结果
13+
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
14+
void search(string& s, int startIndex, int pointNum) {
15+
if (pointNum == 3) { // 逗点数量为3时，分隔结束
16+
// 判断第四段子字符串是否合法，如果合法就放进result中
17+
if (isValid(s, startIndex, s.size() - 1)) {
18+
result.push_back(s);
19+
}
20+
return;
21+
}
22+
// 从起始位置开始构造字段字符串串
23+
for (int i = startIndex; i < s.size(); i++) {
24+
// 判断 [startIndex,i] 这个区间的子串是否合法
25+
if (isValid(s, startIndex, i)) {
26+
// 合法，在i的后面插入一个逗点
27+
s.insert(s.begin() + i + 1 , '.');
28+
// 插入逗点之后下一个子串的起始位置为i+2
29+
search(s, i + 2, pointNum + 1);
30+
s.erase(s.begin() + i + 1); // 回溯时删掉逗点
31+
} else break;
32+
}
33+
}
34+
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
35+
bool isValid(const string& s, int start, int end) {
36+
if (start > end) {
37+
return false;
38+
}
39+
if (s[start] == '0' && start != end) {// 0开头的数字不合法
40+
return false;
41+
}
42+
int num = 0;
43+
for (int i = start; i <= end; i++) {
44+
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
45+
return false;
46+
}
47+
num = num * 10 + (s[i] - '0');
48+
if (num > 255) { // 如果大于255了不合法
49+
return false;
50+
}
51+
}
52+
return true;
53+
}
54+
public:
55+
vector<string> restoreIpAddresses(string s) {
56+
result.clear();
57+
search(s, 0, 0);
58+
return result;
59+
}
60+
};
61+
```
62+
63+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0131.分割回文串.md‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
2+
##题目地址
3+
https://leetcode-cn.com/problems/palindrome-partitioning/
4+
5+
##思路
6+
7+
8+
##C++代码
9+
```
10+
class Solution {
11+
private:
12+
vector<vector<string>> result;
13+
14+
// startIndex: 搜索的起始位置，vec: 放已经回文的子串
15+
void search(const string& s, int startIndex, vector<string>& vec) {
16+
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
17+
if (startIndex >= s.size()) {
18+
result.push_back(vec);
19+
return;
20+
}
21+
for (int i = startIndex; i < s.size(); i++) {
22+
if (isPalindrome(s, startIndex, i)) { // 是回文子串
23+
// 获取[startIndex,i]在s中的子串
24+
string str = s.substr(startIndex, i - startIndex + 1);
25+
vec.push_back(str);
26+
} else { // 如果不是则直接跳过
27+
continue;
28+
}
29+
search(s, i + 1, vec); // 寻找i+1为起始位置的子串
30+
vec.pop_back(); // 回溯过程，弹出本次已经填在的子串
31+
}
32+
}
33+
bool isPalindrome(const string& s, int start, int end) {
34+
for (int i = start, j = end; i < j; i++, j--) {
35+
if (s[i] != s[j]) {
36+
return false;
37+
}
38+
}
39+
return true;
40+
}
41+
public:
42+
vector<vector<string>> partition(string s) {
43+
result.clear();
44+
vector<string> vec;
45+
search(s, 0 , vec);
46+
return result;
47+
}
48+
};
49+
```

‎problems/0349.两个数组的交集.md‎

Lines changed: 23 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -2,21 +2,35 @@
22
##题目地址
33
https://leetcode-cn.com/problems/intersection-of-two-arrays/
44

5-
##思路
5+
>如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！
66
7-
这道题目，主要要学会使用一种哈希数据结构，unordered_set，这个数据结构可以解决很多类似的问题。
7+
#第349题. 两个数组的交集
8+
9+
题意：给定两个数组，编写一个函数来计算它们的交集。
10+
11+
![349. 两个数组的交集](https://img-blog.csdnimg.cn/20200818193523911.png)
12+
13+
**说明：**
14+
输出结果中的每个元素一定是唯一的。
15+
我们可以不考虑输出结果的顺序。
16+
17+
#思路
18+
19+
这道题目，主要要学会使用一种哈希数据结构：unordered_set，这个数据结构可以解决很多类似的问题。
820

921
注意题目特意说明：**输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序**
1022

11-
这道题用暴力的解法时间复杂度是O(n^2)，这种解法面试官一定不会满意，那看看使用哈希法进一步优化。
23+
这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。
24+
25+
可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了。
1226

13-
那么可以发现，貌似用数组做哈希表可以解决这道题目，把nums1的元素，映射到哈希数组的下表上，然后在遍历nums2的时候，判断是否出现过就可以了。
27+
但是要注意，**使用数据来做哈希的题目，都限制了数值的大小，例如[哈希表：可以拿数组当哈希表来用，但哈希值不要太大](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)题目中只有小写字母，或者数值大小在[0- 10000] 之内等等。**
1428

15-
但是要注意，使用数据来做哈希的题目，都限制了数值的大小，例如只有小写字母，或者数值大小在[0- 10000] 之内等等。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
29+
而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
1630

17-
例如说：如果我的输入样例是这样的， 难道要定义一个2亿大小的数组来做哈希表么， 不同的语言对数组定义的大小都是有限制的， 即使有的语言可以定义这么大的数组，那也是对内存空间造成了非常大的浪费。
31+
**而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。**
1832

19-
此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构
33+
此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：
2034

2135
* std::set
2236
* std::multiset
@@ -25,9 +39,10 @@ https://leetcode-cn.com/problems/intersection-of-two-arrays/
2539
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。
2640

2741
思路如图所示：
42+
2843
![set哈希法](https://img-blog.csdnimg.cn/2020080918570417.png)
2944

30-
##代码
45+
#C++代码
3146
```
3247
class Solution {
3348
public:

‎problems/0383.赎金信.md‎

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,9 @@ https://leetcode-cn.com/problems/ransom-note/
33

44
##思路
55

6-
这道题题意很清晰，就是用判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点1.
6+
这道题目和[242.有效的字母异位词](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)很像，[242.有效的字母异位词](https://mp.weixin.qq.com/s/vM6OszkM6L1Mx2Ralm9Dig)相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。
7+
8+
本题判断第一个字符串ransom能不能由第二个字符串magazines里面的字符构成，但是这里需要注意两点1.
79

810
*  第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思”  这里*说明杂志里面的字母不可重复使用。*
911

@@ -37,13 +39,12 @@ public:
3739
};
3840
```
3941
40-
这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的，当然这段代码也可以过这道题
42+
这里时间复杂度是比较高的，而且里面还有一个字符串删除也就是erase的操作，也是费时的，当然这段代码也可以过这道题。
4143
42-
我们想一想优化解法
4344
4445
## 字典计数法（哈希策略）
4546
46-
因为题目所只有小写字母，那我们可以采用空间换区时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
47+
因为题目所只有小写字母，那可以采用空间换区时间的哈希策略， 用一个长度为26的数组还记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母。
4748
代码如下：
4849
4950
```C++

0 commit comments

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