Skip to content

Commit 3bc79d5

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent 71fb7b9 commit 3bc79d5

File tree

4 files changed

+161
-4
lines changed

4 files changed

+161
-4
lines changed

‎README.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@
4040
* 编程语言
4141
* [C++面试&C++学习指南知识点整理](https://github.com/youngyangyang04/TechCPP)
4242

43-
* 代码风格
43+
* 编程素养
4444
* [看了这么多代码，谈一谈代码风格！](https://mp.weixin.qq.com/s/UR9ztxz3AyL3qdHn_zMbqw)
4545

4646
* 求职
@@ -54,6 +54,7 @@
5454
* 算法性能分析
5555
* [关于时间复杂度，你不知道的都在这里！](https://mp.weixin.qq.com/s/LWBfehW1gMuEnXtQjJo-sw)
5656
* [O(n)的算法居然超时了，此时的n究竟是多大？](https://mp.weixin.qq.com/s/73ryNsuPFvBQkt6BbhNzLA)
57+
* [通过一道面试题目，讲一讲递归算法的时间复杂度！](https://mp.weixin.qq.com/s/I6ZXFbw09NR31F5CJR_geQ)
5758

5859
* 数组
5960
* [必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
@@ -276,6 +277,7 @@
276277
|[0129.求根到叶子节点数字之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0129.求根到叶子节点数字之和.md) |二叉树 |中等|**递归/回溯** 递归里隐藏着回溯，和113.路径总和II类似|
277278
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md) |回溯 |中等|**回溯**|
278279
|[0135.分发糖果](https://github.com/youngyangyang04/leetcode/blob/master/problems/0135.分发糖果.md) |贪心 |困难|**贪心**好题目|
280+
|[0139.单词拆分](https://github.com/youngyangyang04/leetcode/blob/master/problems/0139.单词拆分.md) |动态规划 |中等|**完全背包** **回溯法**|
279281
|[0141.环形链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0141.环形链表.md) |链表 |简单|**快慢指针/双指针**|
280282
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md) |链表 |中等|**快慢指针/双指针**|
281283
|[0143.重排链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0143.重排链表.md) |链表 |中等|**快慢指针/双指针** 也可以用数组，双向队列模拟，考察链表综合操作的好题|
@@ -355,6 +357,7 @@
355357
|[0767.重构字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0767.重构字符串.md) |字符串 |中等|**字符串** + 排序+一点贪心|
356358
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md) |孤岛问题 |中等|**bfs** **dfs**|
357359
|[0844.比较含退格的字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0844.比较含退格的字符串.md) |字符串 |简单|**栈** **双指针优化** 使用栈的思路但没有必要使用栈|
360+
|[0860.柠檬水找零](https://github.com/youngyangyang04/leetcode/blob/master/problems/0860.柠檬水找零.md) |贪心算法 |简单|**贪心算法** 基础题目|
358361
|[0925.长按键入](https://github.com/youngyangyang04/leetcode/blob/master/problems/0925.长按键入.md) |字符串 |简单|**双指针/模拟** 是一道模拟类型的题目|
359362
|[0941.有效的山脉数组](https://github.com/youngyangyang04/leetcode/blob/master/problems/0941.有效的山脉数组.md) |数组 |简单|**双指针**|
360363
|[0968.监控二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0968.监控二叉树.md) |二叉树 |困难|**贪心** 贪心与二叉树的结合|

‎problems/0139.单词拆分.md

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
2+
// 如何往 完全背包上靠？
3+
// 用多次倒是可以往 完全背包上靠一靠
4+
// 和单词分割的问题有点像
5+
6+
[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)
7+
8+
回溯法代码：
9+
```
10+
class Solution {
11+
private:
12+
bool backtracking (const string& s, const unordered_set<string>& wordSet, int startIndex) {
13+
if (startIndex >= s.size()) {
14+
return true;
15+
}
16+
for (int i = startIndex; i < s.size(); i++) {
17+
string word = s.substr(startIndex, i - startIndex + 1);
18+
if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, i + 1)) {
19+
return true;
20+
}
21+
}
22+
return false;
23+
}
24+
public:
25+
bool wordBreak(string s, vector<string>& wordDict) {
26+
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
27+
return backtracking(s, wordSet, 0);
28+
}
29+
};
30+
```
31+
32+
```
33+
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
34+
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
35+
```
36+
37+
可以使用一个一维数组保存一下，递归过程中计算的结果，C++代码如下：
38+
39+
使用memory数组保存 每次计算的以startIndex起始的计算结果，如果memory[startIndex]里已经被赋值了，直接用memory[startIndex]的结果。
40+
```
41+
class Solution {
42+
private:
43+
bool backtracking (const string& s,
44+
const unordered_set<string>& wordSet,
45+
vector<int>& memory,
46+
int startIndex) {
47+
if (startIndex >= s.size()) {
48+
return true;
49+
}
50+
// 如果memory[startIndex]不是初始值了，直接使用memory[startIndex]的结果
51+
if (memory[startIndex] != -1) return memory[startIndex];
52+
for (int i = startIndex; i < s.size(); i++) {
53+
string word = s.substr(startIndex, i - startIndex + 1);
54+
if (wordSet.find(word) != wordSet.end() && backtracking(s, wordSet, memory, i + 1)) {
55+
memory[startIndex] = 1; // 记录以startIndex开始的子串是可以被拆分的
56+
return true;
57+
}
58+
}
59+
memory[startIndex] = 0; // 记录以startIndex开始的子串是不可以被拆分的
60+
return false;
61+
}
62+
public:
63+
bool wordBreak(string s, vector<string>& wordDict) {
64+
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
65+
vector<int> memory(s.size(), -1); // -1 表示初始化状态
66+
return backtracking(s, wordSet, memory, 0);
67+
}
68+
};
69+
```
70+
71+
72+
得好好分析一下，完全背包和01背包，这个对于刷leetcode太重要了
73+
74+
注意这里要空出一个 dp[0] 来做起始位置
75+
```
76+
class Solution {
77+
public:
78+
bool wordBreak(string s, vector<string>& wordDict) {
79+
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
80+
vector<bool> dp(s.size() + 1, false);
81+
dp[0] = true;
82+
for (int i = 1; i <= s.size(); i++) {
83+
for (int j = 0; j < i; j++) {
84+
string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
85+
if (wordSet.find(word) != wordSet.end() && dp[j]) {
86+
dp[i] = true;
87+
}
88+
}
89+
//for (int k = 0; k <=i; k++) cout << dp[k] << " ";
90+
//cout << endl;
91+
}
92+
return dp[s.size()];
93+
}
94+
};
95+
```
96+
时间复杂度起始是O(n^3)，因为substr返回子串的副本是O(n)的复杂度（n是substring的长度）

‎problems/0860.柠檬水找零.md

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
> 如果对贪心算法理论基础还不了解的话，可以看看这篇：[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg) ，相信看完之后对贪心就有基本的了解了。
2+
3+
这道题目我们需要维护三种金额的数量，5，10和20。
4+
5+
有如下三种情况：
6+
* 情况一：账单是5，直接收下。
7+
* 情况二：账单是10，消耗一个5，增加一个10
8+
* 情况三：账单是20，优先消耗一个10和一个5，如果不够，在消耗三个5
9+
10+
这道题大家可能感觉纯模拟就可以了，其实这里有贪心，就在情况三中。
11+
12+
账单是20的情况，为什么要优先消耗一个10和一个5呢？
13+
14+
**因为美元10只能给账单20找零，而美元5可以给账单10和账单20找零，美元5更万能！**
15+
16+
局部最优：遇到账单20，优先消耗美元10，完成本次找零。全局最优：完成全部账单的找零。
17+
18+
局部最优可以推出全局最优，并找不出反例，那么就试试贪心。
19+
20+
C++代码如下：
21+
22+
```C++
23+
class Solution {
24+
public:
25+
bool lemonadeChange(vector<int>& bills) {
26+
int five = 0, ten = 0, twenty = 0;
27+
for (int bill : bills) {
28+
// 情况一
29+
if (bill == 5) five++;
30+
// 情况二
31+
if (bill == 10) {
32+
if (five <= 0) return false;
33+
ten++;
34+
five--;
35+
}
36+
// 情况三
37+
if (bill == 20) {
38+
// 优先消耗10美元，因为5美元的找零用处更大，能多留着就多留着
39+
if (five > 0 && ten > 0) {
40+
five--;
41+
ten--;
42+
twenty++; // 其实这行代码可以删了，因为记录20已经没有意义了，不会用20来找零
43+
} else if (five >= 3) {
44+
five -= 3;
45+
twenty++; // 同理，这行代码也可以删了
46+
} else return false;
47+
}
48+
}
49+
return true;
50+
}
51+
};
52+
53+
```
54+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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/20201124161234338.png)，关注后就会发现和「代码随想录」相见恨晚！**
55+
56+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
57+

‎problems/导读.md

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -12,10 +12,10 @@
1212

1313
# 文章篇
1414

15-
* 代码风格
15+
* 编程素养
1616
* [看了这么多代码，谈一谈代码风格！](https://mp.weixin.qq.com/s/UR9ztxz3AyL3qdHn_zMbqw)
1717

18-
* 求职
18+
* 求职
1919
* [程序员的简历应该这么写！！（附简历模板）](https://mp.weixin.qq.com/s/nCTUzuRTBo1_R_xagVszsA)
2020
* [BAT级别技术面试流程和注意事项都在这里了](https://mp.weixin.qq.com/s/815qCyFGVIxwut9I_7PNFw)
2121
* [深圳原来有这么多互联网公司，你都知道么？](https://mp.weixin.qq.com/s/Yzrkim-5bY0Df66Ao-hoqA)
@@ -26,6 +26,7 @@
2626
* 算法性能分析
2727
* [关于时间复杂度，你不知道的都在这里！](https://mp.weixin.qq.com/s/LWBfehW1gMuEnXtQjJo-sw)
2828
* [O(n)的算法居然超时了，此时的n究竟是多大？](https://mp.weixin.qq.com/s/73ryNsuPFvBQkt6BbhNzLA)
29+
* [通过一道面试题目，讲一讲递归算法的时间复杂度！](https://mp.weixin.qq.com/s/I6ZXFbw09NR31F5CJR_geQ)
2930

3031
* 数组
3132
* [必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
@@ -172,10 +173,10 @@
172173
# 视频篇
173174

174175
* 算法
176+
* [带你学透KMP算法（理论篇&代码篇）](https://mp.weixin.qq.com/s/SFAs4tbo2jDgzST9AsF2xg)
175177
* [带你学透回溯算法（理论篇）](https://mp.weixin.qq.com/s/wDd5azGIYWjbU0fdua_qBg)
176178
* [回溯算法：组合问题](https://mp.weixin.qq.com/s/a_r5JR93K_rBKSFplPGNAA)
177179
* [回溯算法：组合问题的剪枝操作](https://mp.weixin.qq.com/s/CK0kj9lq8-rFajxL4amyEg)
178-
* [带你学透KMP算法（理论篇&代码篇）](https://mp.weixin.qq.com/s/SFAs4tbo2jDgzST9AsF2xg)
179180
* C++
180181
* 听说C++ primer 太厚了 看不进去？：https://www.bilibili.com/video/BV1Z5411874t
181182
* C++ primer 第一章，你要知道的知识点还有这些！：https://www.bilibili.com/video/BV1Kv41117Ya

0 commit comments

Comments
 (0)