452. 击破气球的最少箭数
一些球形气球贴在代表 XY 平面的平坦墙壁上。气球表示为 2D 整数数组点，其中，points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend 之间延伸的气球。您不知道气球的确切 y 坐标。
箭头可以从x轴上的不同点直接垂直（y轴正方向）射出。如果 xstart
给定数组点，返回击破所有气球所需的最少箭数。
示例1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
说明：气球可以用 2 个箭头来爆破： 在 x = 6 处射箭，使气球 [2,8] 和 [1,6] 破裂。 在 x = 11 处射箭，使气球 [10,16] 和 [7,12] 破裂。 示例2：输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
说明：每个气球需要射一支箭，总共4支箭。
示例3：输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
说明：气球可以用 2 个箭头来爆破： 在 x = 2 处射箭，使气球 [1,2] 和 [2,3] 爆裂。 在 x = 4 处射箭，使气球 [3,4] 和 [4,5] 爆裂。限制：
1 点[i].length == 2
-2^31 原始页面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
public int findMinArrowShots(int[][] 点) {
if(points.length == 0){
返回0；
}
Arrays.sort(点, (a,b) ->{
如果（a[0] == b[0]）{
返回a[1] - b[1]；
}
返回a[0] - b[0]；
});
整数箭头=1；
int start = 点[0][0];
int end = 点[0][1];
for(int i=0; i<points.length i if>= 开始 && 点[i][0]=点[i][0] && 结束 开始 && 点[i][0] 开始 && 点[i][1]
<h2>
435. 不重叠的区间
</h2>
<p>给定一个间隔数组，其中间隔[i] = [starti, endi]，返回需要删除以使其余间隔不重叠的最小间隔数。</p>
<p>示例1：</p>
<p>输入：间隔 = [[1,2],[2,3],[3,4],[1,3]]<br>
输出：1<br>
解释：[1,3]可以去掉，其余区间不重叠。<br>
示例2：</p>
<p>输入：间隔 = [[1,2],[1,2],[1,2]]<br>
输出：2<br>
说明：您需要删除两个 [1,2] 以使其余间隔不重叠。<br>
示例3：</p>
<p>输入：间隔 = [[1,2],[2,3]]<br>
输出：0<br>
说明：您不需要删除任何间隔，因为它们已经不重叠。</p>
<p>限制：</p>
<p>1
间隔[i].length == 2<br>
-5 10^4
原始页面</p>
<h2>
错误代码
</h2>
<pre class="brush:php;toolbar:false"> public int EraseOverlapIntervals(int[][]Intervals) {
if(intervals.length == 0){
返回0；
}
Arrays.sort(间隔, (a,b) ->{
if(a[0] == b[0]){
返回a[1] - b[1]；
}
返回a[0] - b[0]；
});
Arrays.stream(间隔)
.map(数组::toString)
.forEach(System.out::println);
整数计数=0；
// List<int> list = new LinkedList();
int start = 间隔[0][0];
int end = 间隔[0][1];
for(int i=1; i<intervals.length i if>=开始 && 间隔[i][0]
<h2>
修理它
</h2>
<pre class="brush:php;toolbar:false"> public int EraseOverlapIntervals(int[][]Intervals) {
if(intervals.length == 0){
返回0；
}
Arrays.sort(间隔, (a,b) ->{
返回a[0] - b[0]；
});
整数计数=0；
int start = 间隔[0][0];
int end = 间隔[0][1];
for(int i=1; i<intervals.length i if math.min><h2>
763. 分区标签
</h2>
<p>给你一个字符串 s。我们希望将字符串分成尽可能多的部分，以便每个字母最多出现在一个部分中。</p>
<p>注意，分区是为了将所有部分按顺序连接后，得到的字符串应该是 s。</p>
<p>返回表示这些部分大小的整数列表。</p>
<p>示例1：</p>
<p>输入：s = "ababcbacadefegdehijhklij"<br>
输出：[9,7,8]<br>
说明：<br>
分区是“ababcbaca”、“defegde”、“hijhklij”。<br>
这是一个分区，以便每个字母最多出现在一个部分中。<br>
像“ababcbacadefegde”、“hijhklij”这样的分区是不正确的，因为它将 s 分成更少的部分。<br>
示例2：</p>
<p>输入：s = "eccbbbbdec"<br>
输出：[10]</p>
<p>限制：</p>
<p>1
s 由小写英文字母组成。<br>
原始页面<br></p>
<pre class="brush:php;toolbar:false"> public List<integer>partitionLabels(String s) {
List<integer> list = new ArrayList();
Set set = new HashSet();
if(s.length() == 0){
返回列表；
}
int 开始 = 0;
整数结束= 0；
for(int i=0; i<s.length i s.charat if set.add int j="s.length()-1;" for>i;j--){
if(s.charAt(j) == 目标){
休息;
}
}
结束 = Math.max(结束, j);
}
如果（我==结束）{
list.add(结束-开始+1);
开始 = i+1;
设置.clear();
}
}
返回列表；
}
</s.length></integer></integer>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public List<integer>partitionLabels(String s) {
List<integer> list = new ArrayList();
Set set = new HashSet();
int[] pos = 新 int[27];
for(int i=s.length()-1; i>0;i--){
if(pos[s.charAt(i)-a] == 0){
pos[s.charAt(i)-a] = i;
}
}
if(s.length() == 0){
返回列表；
}
int 开始 = 0;
整数结束= 0；
for(int i=0; i<s.length i s.charat if set.add end="Math.max(end," pos list.add><pre class="brush:php;toolbar:false"> public List<integer>partitionLabels(String s) {
List<integer> list = new ArrayList();
int[] pos = 新 int[27];
for(int i=s.length()-1; i>0;i--){
if(pos[s.charAt(i)-a] == 0){
pos[s.charAt(i)-a] = i;
}
}
if(s.length() == 0){
返回列表；
}
int 开始 = 0;
整数结束= 0；
for(int i=0; i<s.length i s.charat end="Math.max(end," pos list.add><p>因为判断元素是否已经在集合中并不重要，我们只关注是否到达终点，如果出现相同的元素，终点不会改变，如果不同的元素合并，看起来like end 可能会改变，但所有这些都不会影响 if 评估，因此我们可以删除它们。 </p>
</s.length></integer></integer>
以上就是LeetCode Day 贪心算法 第 4 部分的详细内容，更多请关注其它相关文章！