Skip to content

Commit ea0d3d2

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent 3bc79d5 commit ea0d3d2

File tree

5 files changed

+208
-1
lines changed

5 files changed

+208
-1
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,7 @@
5555
* [关于时间复杂度，你不知道的都在这里！](https://mp.weixin.qq.com/s/LWBfehW1gMuEnXtQjJo-sw)
5656
* [O(n)的算法居然超时了，此时的n究竟是多大？](https://mp.weixin.qq.com/s/73ryNsuPFvBQkt6BbhNzLA)
5757
* [通过一道面试题目，讲一讲递归算法的时间复杂度！](https://mp.weixin.qq.com/s/I6ZXFbw09NR31F5CJR_geQ)
58+
* [本周小结！（算法性能分析系列一）](https://mp.weixin.qq.com/s/5m8xDbGUeGgYJsESeg5ITQ)
5859

5960
* 数组
6061
* [必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
@@ -327,6 +328,7 @@
327328
|[0454.四数相加II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0454.四数相加II.md) |哈希表 |中等| **哈希**|
328329
|[0455.分发饼干](https://github.com/youngyangyang04/leetcode/blob/master/problems/0455.分发饼干.md) |贪心 |简单| **贪心**|
329330
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md) |字符创 |简单| **KMP**|
331+
|[0473.火柴拼正方形](https://github.com/youngyangyang04/leetcode/blob/master/problems/0473.火柴拼正方形.md) |深度优先搜索|中等| **回溯算法** 和698.划分为k个相等的子集差不多|
330332
|[0474.一和零](https://github.com/youngyangyang04/leetcode/blob/master/problems/0474.一和零.md) |动态规划 |中等| **多重背包** 好题目|
331333
|[0486.预测赢家](https://github.com/youngyangyang04/leetcode/blob/master/problems/0486.预测赢家.md) |动态规划 |中等| **递归** **记忆递归** **动态规划**|
332334
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md) |深度优先搜索 |中等|**深度优先搜索/回溯算法** 这个去重有意思|
@@ -345,9 +347,11 @@
345347
|[0590.N叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0590.N叉树的后序遍历.md) |N叉树 |简单|**递归** **栈/迭代**|
346348
|[0617.合并二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0617.合并二叉树.md) |树 |简单|**递归** **迭代**|
347349
|[0637.二叉树的层平均值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0637.二叉树的层平均值.md) |树 |简单|**广度优先搜索/队列**|
350+
|[0649.Dota2参议院](https://github.com/youngyangyang04/leetcode/blob/master/problems/0649.Dota2参议院.md) |贪心 |简单|**贪心算法** 简单的贪心策略但代码实现很有技巧|
348351
|[0654.最大二叉树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0654.最大二叉树.md) |树 |中等|**递归**|
349352
|[0685.冗余连接II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0685.冗余连接II.md) | 并查集/树/图 |困难|**并查集**|
350353
|[0669.修剪二叉搜索树](https://github.com/youngyangyang04/leetcode/blob/master/problems/0669.修剪二叉搜索树.md) | 二叉搜索树/二叉树 |简单|**递归** **迭代**|
354+
|[0698.划分为k个相等的子集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0698.划分为k个相等的子集.md) |回溯算法|中等|动态规划 **回溯算法** 这其实是组合问题，使用了两次递归，好题|
351355
|[0700.二叉搜索树中的搜索](https://github.com/youngyangyang04/leetcode/blob/master/problems/0700.二叉搜索树中的搜索.md) |二叉搜索树 |简单|**递归** **迭代**|
352356
|[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md) |二叉搜索树 |简单|**递归** **迭代**|
353357
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md) |哈希表 |简单|**模拟**|

‎problems/0416.分割等和子集.md

Lines changed: 50 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
11

2-
和Leetcode 473：火柴拼正方形和Leetcode 698：划分为k个相等的子集是
32

3+
* 473. 火柴拼正方形 （回溯算法）
4+
* 698. 划分为k个相等的子集
5+
6+
一起再回忆一下回溯算法
7+
8+
|[0473.火柴拼正方形](https://github.com/youngyangyang04/leetcode/blob/master/problems/0473.火柴拼正方形.md) |深度优先搜索|中等| **回溯算法** 和698.划分为k个相等的子集差不多|
49

510
## 思路
611

@@ -82,6 +87,8 @@ public:
8287

8388
本来是想用回溯暴力搜索出所有答案的，各种剪枝，还是超时了，不想在调了，放弃回溯，直接上01背包吧。
8489

90+
**需要尝试一下记忆化递归**
91+
8592
回溯搜索超时的代码如下：
8693

8794
```
@@ -119,3 +126,45 @@ public:
119126
};
120127
121128
```
129+
130+
```
131+
class Solution {
132+
private:
133+
bool backtracking(vector<int>& nums,
134+
int k,
135+
int target, // 子集目标和
136+
int cur, // 当前目标和
137+
int startIndex, // 起始位置
138+
vector<bool>& used) { // 标记是否使用过
139+
if (k == 0) return true; // 找到了k个相同子集
140+
if (cur == target) { // 发现一个合格子集，然后重新开始寻找
141+
return backtracking(nums, k - 1, target, 0, 0, used); // k-1
142+
}
143+
for (int i = startIndex; i < nums.size(); i++) {
144+
if (cur + nums[i] <= target && !used[i]) {
145+
used[i] = true;
146+
if (backtracking(nums, k, target, cur + nums[i], i + 1, used)) {
147+
return true;
148+
}
149+
used[i] = false;
150+
}
151+
}
152+
return false;
153+
}
154+
155+
public:
156+
bool canPartition(vector<int>& nums) {
157+
if (nums.size() < 2) return false; // 火柴数量小于4凑不上正方形
158+
int sum = 0;
159+
for (int i = 0; i < nums.size(); i++) {
160+
sum += nums[i];
161+
}
162+
if (sum % 2 != 0) return false;
163+
int target = sum / 2;
164+
vector<bool> used(nums.size(), false);
165+
166+
return backtracking(nums, 2, target, 0, 0, used);
167+
168+
}
169+
};
170+
```

‎problems/0473.火柴拼正方形.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2+
698.划分为k个相等的子集 的代码几乎不用改动，就可以AC
3+
```
4+
class Solution {
5+
private:
6+
bool backtracking(vector<int>& nums,
7+
int k,
8+
int target, // 子集目标和
9+
int cur, // 当前目标和
10+
int startIndex, // 起始位置
11+
vector<bool>& used) { // 标记是否使用过
12+
if (k == 0) return true; // 找到了k个相同子集
13+
if (cur == target) { // 发现一个合格子集，然后重新开始寻找
14+
return backtracking(nums, k - 1, target, 0, 0, used); // k-1
15+
}
16+
for (int i = startIndex; i < nums.size(); i++) {
17+
if (cur + nums[i] <= target && !used[i]) {
18+
used[i] = true;
19+
if (backtracking(nums, k, target, cur + nums[i], i + 1, used)) {
20+
return true;
21+
}
22+
used[i] = false;
23+
}
24+
}
25+
return false;
26+
}
27+
public:
28+
bool makesquare(vector<int>& nums) {
29+
if (nums.size() < 4) return false; // 火柴数量小于4凑不上正方形
30+
int sum = 0;
31+
for (int i = 0; i < nums.size(); i++) {
32+
sum += nums[i];
33+
}
34+
if (sum % 4 != 0) return false;
35+
int target = sum / 4;
36+
vector<bool> used(nums.size(), false);
37+
38+
return backtracking(nums, 4, target, 0, 0, used);
39+
40+
}
41+
};
42+
```

‎problems/0649.Dota2参议院.md

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
2+
## 思路
3+
4+
这道题 题意太绕了，我举一个更形象的例子给大家捋顺一下。
5+
6+
例如输入"RRDDD"，执行过程应该是什么样呢？
7+
8+
* 第一轮：senate[0]的R消灭senate[2]的D，senate[1]的R消灭senate[3]的D，senate[4]的D消灭senate[0]的R，此时剩下"RD"，第一轮结束！
9+
* 第二轮：senate[0]的R消灭senate[1]的D，第二轮结束
10+
* 第三轮：只有R了，R胜利
11+
12+
估计不少同学都困惑，R和D数量相同怎么办，究竟谁赢，**其实这是一个持续消灭的过程！** 即：如果同时存在R和D就继续进行下一轮消灭，轮数直到只剩下R或者D为止！
13+
14+
那么每一轮消灭的策略应该是什么呢？
15+
16+
例如：RDDRD
17+
18+
第一轮：senate[0]的R消灭senate[1]的D，那么senate[2]的D，是消灭senate[0]的R还是消灭senate[3]的R呢？
19+
20+
当然是消灭senate[3]的R，因为当轮到这个R的时候，它可以消灭senate[4]的D。
21+
22+
**所以消灭的策略是，尽量消灭自己后面的对手，因为前面的对手已经使用过权利了，而后序的对手依然可以使用权利消灭自己的同伴！**
23+
24+
那么局部最优：有一次权利机会，就消灭自己后面的对手。全局最优：为自己的阵营赢取最大利益。
25+
26+
局部最优可以退出全局最优，举不出反例，那么试试贪心。
27+
28+
如果对贪心算法理论基础还不了解的话，可以看看这篇：[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg) ，相信看完之后对贪心就有基本的了解了。
29+
30+
## 代码实现
31+
32+
实现代码，在每一轮循环的过程中，去过模拟优先消灭身后的对手，其实是比较麻烦的。
33+
34+
这里有一个技巧，就是用一个变量记录当前参议员之前有几个敌对对手了，进而判断自己是否被消灭了。这个变量我用flag来表示。
35+
36+
C++代码如下：
37+
38+
39+
```
40+
class Solution {
41+
public:
42+
string predictPartyVictory(string senate) {
43+
// R = true表示本轮循环结束后，字符串里依然有R。D同理
44+
bool R = true, D = true;
45+
// 当flag大于0时，R在D前出现，R可以消灭D。当flag小于0时，D在R前出现，D可以消灭R
46+
int flag = 0;
47+
while (R && D) { // 一旦R或者D为false，就结束循环，说明本轮结束后只剩下R或者D了
48+
R = false;
49+
D = false;
50+
for (int i = 0; i < senate.size(); i++) {
51+
if (senate[i] == 'R') {
52+
if (flag < 0) senate[i] = 0; // 消灭R，R此时为false
53+
else R = true; // 如果没被消灭，本轮循环结束有R
54+
flag++;
55+
}
56+
if (senate[i] == 'D') {
57+
if (flag > 0) senate[i] = 0;
58+
else D = true;
59+
flag--;
60+
}
61+
}
62+
}
63+
// 循环结束之后，R和D只能有一个为true
64+
return R == true ? "Radiant" : "Dire";
65+
}
66+
};
67+
```
68+
69+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
70+

‎problems/0698.划分为k个相等的子集.md

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2+
使用回溯法，首先要明确这是组合问题，即集合里是不强调顺序的，所以要用startIndex
3+
4+
```
5+
class Solution {
6+
private:
7+
bool backtracking(vector<int>& nums,
8+
int k,
9+
int target, // 子集目标和
10+
int cur, // 当前目标和
11+
int startIndex, // 起始位置
12+
vector<bool>& used) { // 标记是否使用过
13+
if (k == 0) return true; // 找到了k个相同子集
14+
if (cur == target) { // 发现一个合格子集，然后重新开始寻找
15+
return backtracking(nums, k - 1, target, 0, 0, used); // k-1
16+
}
17+
for (int i = startIndex; i < nums.size(); i++) {
18+
if (cur + nums[i] <= target && !used[i]) {
19+
used[i] = true;
20+
if (backtracking(nums, k, target, cur + nums[i], i + 1, used)) {
21+
return true;
22+
}
23+
used[i] = false;
24+
}
25+
}
26+
return false;
27+
}
28+
public:
29+
bool canPartitionKSubsets(vector<int>& nums, int k) {
30+
//sort(nums.begin(), nums.end()); 不需要排序
31+
int sum = 0;
32+
for (int i = 0; i < nums.size(); i++) {
33+
sum += nums[i];
34+
}
35+
if (sum % k != 0) return false;
36+
int target = sum / k;
37+
vector<bool> used(nums.size(), false);
38+
39+
return backtracking(nums, k, target, 0, 0, used);
40+
}
41+
};
42+
```

0 commit comments

Comments
 (0)