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

Commit80cb4d9

Browse files
Update
1 parentf881e3e commit80cb4d9

File tree

5 files changed

+149
-17
lines changed

5 files changed

+149
-17
lines changed

‎pics/763.划分字母区间.png

15.5 KB
Loading

‎problems/0435.无重叠区间.md

Lines changed: 61 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@
4848

4949
按照左边界排序，就要从右向左遍历，因为左边界数值越大越好（越靠右），这样就给前一个区间的空间就越大，所以可以从右向左遍历。
5050

51-
如果按照左边界排序，还从左向右遍历的话，要处理各个区间右边界的各种情况，就很复杂了。
51+
如果按照左边界排序，还从左向右遍历的话，其实也可以，逻辑会有所不同。
5252

5353
一些同学做这道题目可能真的去模拟去重复区间的行为，这是比较麻烦的，还要去删除区间。
5454

@@ -126,7 +126,67 @@ public:
126126

127127
**所以我把本题的难点也一一列出，帮大家不仅代码看的懂，想法也理解的透彻！**
128128

129+
#补充
130+
131+
本题其实和[贪心算法：用最少数量的箭引爆气球](https://mp.weixin.qq.com/s/HxVAJ6INMfNKiGwI88-RFw)非常像，弓箭的数量就相当于是非交叉区间的数量，只要把弓箭那道题目代码里射爆气球的判断条件加个等号（认为[0，1][1，2]不是相邻区间），然后用总区间数减去弓箭数量 就是要移除的区间数量了。
132+
133+
把[贪心算法：用最少数量的箭引爆气球](https://mp.weixin.qq.com/s/HxVAJ6INMfNKiGwI88-RFw)代码稍做修改，别可以AC本题。
134+
135+
```C++
136+
classSolution {
137+
public:
138+
// 按照区间右边界排序
139+
static bool cmp (const vector<int>& a, const vector<int>& b) {
140+
return a[1] < b[1];
141+
}
142+
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
143+
if (intervals.size() == 0) return 0;
144+
sort(intervals.begin(), intervals.end(), cmp);
145+
146+
int result = 1; // points 不为空至少需要一支箭
147+
for (int i = 1; i < intervals.size(); i++) {
148+
if (intervals[i][0] >= intervals[i - 1][1]) {
149+
result++; // 需要一支箭
150+
}
151+
else { // 气球i和气球i-1挨着
152+
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
153+
}
154+
}
155+
return intervals.size() - result;
156+
}
157+
};
158+
```
159+
160+
这里按照 作弊案件遍历，或者按照右边界遍历，都可以AC，具体原因我还没有仔细看，后面有空再补充。
161+
```C++
162+
classSolution {
163+
public:
164+
// 按照区间左边界排序
165+
static bool cmp (const vector<int>& a, const vector<int>& b) {
166+
return a[0] < b[0];
167+
}
168+
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
169+
if (intervals.size() == 0) return 0;
170+
sort(intervals.begin(), intervals.end(), cmp);
171+
172+
int result = 1; // points 不为空至少需要一支箭
173+
for (int i = 1; i < intervals.size(); i++) {
174+
if (intervals[i][0] >= intervals[i - 1][1]) {
175+
result++; // 需要一支箭
176+
}
177+
else { // 气球i和气球i-1挨着
178+
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界
179+
}
180+
}
181+
return intervals.size() - result;
182+
}
183+
};
184+
185+
```
186+
129187
循序渐进学算法，认准「代码随想录」就够了，值得介绍给身边的朋友同学们！
130188

131189
>我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[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/20200815195519696.png)，期待你的关注！
132190
191+
192+
是不是尽可能重叠，其实它都在那里，没有尽可能这一说

‎problems/0494.目标和.md

Lines changed: 41 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -70,33 +70,68 @@ public:
7070

7171
##动态规划
7272

73-
使用背包要明确dp[i]表示的是什么，i表示的又是什么？
73+
如何转化为01背包问题呢。
7474

75-
填满i（包括i）这么大容积的包，有dp[i]种方法。
75+
假设加法的总和为x，那么减法对应的总和就是sum - x。
7676

77+
所以我们要求的是 x - (sum - x) = S
78+
79+
x = (S + sum) / 2
80+
81+
此时问题就转化为，装满容量为x背包，有几种方法。
82+
83+
大家看到(S + sum) / 2 应该担心计算的过程中向下取整有没有影响。
84+
85+
这么担心就对了，例如sum 是5，S是2的话其实就是无解的，所以：
86+
87+
```
88+
if ((S + sum) % 2 == 1) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
89+
```
90+
91+
看到这种表达式，应该本能的反应，两个int相加数值可能溢出的问题，当然本题并没有溢出。
92+
93+
在回归到01背包问题，
94+
95+
这次和之前遇到的背包问题不一样了，之前都是求容量为j的背包，最多能装多少。
96+
97+
本题是装满有几种方法。
98+
99+
* 确定dp数组以及下标的含义
100+
101+
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[i]种方法
102+
103+
* 确定递推公式
104+
105+
有哪些来源可以推出dp[j]呢，只有dp[j - nums[i]]。
106+
107+
那么dp[j] 应该是 dp[j] + dp[j - nums[i]] （**这块需要好好讲讲**）
108+
109+
* dp数组如何初始化
110+
* 确定遍历顺序
77111

78112
```
79-
// 时间复杂度O(n^2)
80-
// 空间复杂度可以说是O(n)，也可以说是O(1)，因为每次申请的辅助数组的大小是一个常数
81113
class Solution {
82114
public:
83115
int findTargetSumWays(vector<int>& nums, int S) {
84116
int sum = 0;
85117
for (int i = 0; i < nums.size(); i++) sum += nums[i];
86118
if (S > sum) return 0; // 此时没有方案
87-
if ((S + sum) % 2) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
119+
if ((S + sum) % 2 == 1) return 0; // 此时没有方案，两个int相加的时候要各位小心数值溢出的问题
88120
89121
int bagSize = (S + sum) / 2;
90122
int dp[1001] = {1};
91123
for (int i = 0; i < nums.size(); i++) {
92124
for (int j = bagSize; j >= nums[i]; j--) {
93-
if (j - nums[i] >= 0)dp[j] += dp[j - nums[i]];
125+
dp[j] += dp[j - nums[i]];
94126
}
95127
}
96128
return dp[bagSize];
97129
}
98130
};
99131
```
132+
* 时间复杂度O(n * m)，n为正数个数，m为背包容量
133+
* 空间复杂度：O(n)，也可以说是O(1)，因为每次申请的辅助数组的大小是一个常数
134+
100135
dp数组中的数值变化：（从[0 - 4]）
101136

102137
```

‎problems/0763.划分字母区间.md

Lines changed: 44 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,46 @@
1-
##题目链接
2-
https://leetcode-cn.com/problems/partition-labels/
1+
>看起来有点难，看仅仅是看起来难而已
32
4-
##思路
3+
#763.划分字母区间
54

6-
一想到分割字符串就想到了回溯，但本题其实不用那么复杂。
5+
题目链接：https://leetcode-cn.com/problems/partition-labels/
6+
7+
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
8+
9+
示例：
10+
输入：S = "ababcbacadefegdehijhklij"
11+
输出：[9,7,8]
12+
解释：
13+
划分结果为 "ababcbaca", "defegde", "hijhklij"。
14+
每个字母最多出现在一个片段中。
15+
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
16+
 
17+
提示：
18+
19+
* S的长度在[1, 500]之间。
20+
* S只包含小写字母 'a' 到 'z' 。
21+
22+
#思路
23+
24+
一想到分割字符串就想到了回溯，但本题其实不用回溯去暴力搜索。
25+
26+
题目要求同一字母最多出现在一个片段中，那么如何把同一个字母的都圈在同一个区间里呢？
27+
28+
如果没有接触过这种题目的话，还挺有难度的。
29+
30+
在遍历的过程中相当于是要找每一个字母的边界，**如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了**。此时前面出现过所有字母，最远也就到这个边界了。
731

832
可以分为如下两步：
933

1034
* 统计每一个字符最后出现的位置
11-
* 从头遍历字符，如果找到之前字符最大出现位置下标和当前下标相等，则找到了分割点
35+
* 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
1236

1337
如图：
1438

15-
<imgsrc='../pics/763.划分字母区间.png'width=600> </img></div>
39+
![763.划分字母区间](https://img-blog.csdnimg.cn/20201222191924417.png)
1640

1741
明白原理之后，代码并不复杂，如下：
1842

19-
```
43+
```C++
2044
classSolution {
2145
public:
2246
vector<int> partitionLabels(string S) {
@@ -38,4 +62,16 @@ public:
3862
}
3963
};
4064
```
41-
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
65+
66+
* 时间复杂度：O(n)
67+
* 空间复杂度：O(1) 使用的hash数组是固定大小
68+
69+
# 总结
70+
71+
这道题目leetcode标记为贪心算法，说实话，我没有感受到贪心，找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。
72+
73+
但这道题目的思路是很巧妙的，所以有必要介绍给大家做一做，感受一下。
74+
75+
就酱，循序渐进寻算法，认准「代码随想录」，直接介绍给身边的朋友同学们！
76+
77+

‎problems/1049.最后一块石头的重量II.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -37,10 +37,11 @@ dp[j]有两个来源方向，一个是dp[j]自己，一个是dp[j - stones[i]]
3737

3838
for循环遍历石头的数量嵌套一个for循环遍历背包容量，且因为是01背包，每一个物品只使用一次，所以遍历背包容量的时候要倒序。
3939

40-
具体原因我在
40+
具体原因我在[01背包一维数组实现](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-2.md)详细讲解过了。大家感兴趣可以去看一下。
4141

4242

43-
```
43+
最后C++代码如下：
44+
```C++
4445
classSolution {
4546
public:
4647
int lastStoneWeightII(vector<int>& stones) {

0 commit comments

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