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

Commit3bc79d5

Browse files
Update
1 parent71fb7b9 commit3bc79d5

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+
classSolution {
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)
[8]ページ先頭
©2009-2025 Movatter.jp