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

Commitea0d3d2

Browse files
Update
1 parent3bc79d5 commitea0d3d2

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