452. 풍선을 터뜨리기 위한 최소 화살표 수
XY 평면을 나타내는 평평한 벽에 몇 개의 구형 풍선이 테이프로 붙어 있습니다. 풍선은 2D 정수 배열 점으로 표시됩니다. 여기서 points[i] = [xstart, xend]는 수평 직경이 xstart와 xend 사이에 걸쳐 있는 풍선을 나타냅니다. 풍선의 정확한 y좌표를 모릅니다.
화살표는 x축을 따라 여러 지점에서 수직(양의 y 방향)으로 직접 발사될 수 있습니다. xstart <= x <= xend인 경우 xstart 및 xend가 있는 풍선은 x를 향해 발사된 화살에 의해 터집니다. 쏠 수 있는 화살의 수에는 제한이 없습니다. 쏜 화살은 무한히 위로 날아가며 경로에 있는 모든 풍선을 터뜨립니다.
배열 포인트가 주어지면 모든 풍선을 터뜨리기 위해 발사해야 하는 최소 화살 수를 반환합니다.
예 1:
입력: 포인트 = [[10,16],[2,8],[1,6],[7,12]]
출력: 2
설명: 풍선은 2개의 화살로 터뜨릴 수 있습니다:
- x = 6에서 화살을 쏘아 풍선 [2,8]과 [1,6]을 터뜨립니다.
- x = 11에서 화살을 쏘아 풍선 [10,16]과 [7,12]를 터뜨립니다.
예시 2:
입력: 포인트 = [[1,2],[3,4],[5,6],[7,8]]
출력: 4
설명: 풍선 1개당 화살 1개를 쏘아 총 4개의 화살을 쏘아야 합니다.
예시 3:
입력: 포인트 = [[1,2],[2,3],[3,4],[4,5]]
출력: 2
설명: 풍선은 2개의 화살로 터뜨릴 수 있습니다:
- x = 2에서 화살을 쏘아 풍선 [1,2]와 [2,3]을 터뜨립니다.
- x = 4에서 화살을 쏘아 풍선 [3,4]와 [4,5]를 터뜨립니다.
제약사항:
1 <= 포인트.길이 <= 105
포인트[i].길이 == 2
-2^31 <= xstart < xend <= 2^31 - 1
원본페이지
public int findMinArrowShots(int[][] points) {
if(points.length == 0){
return 0;
}
Arrays.sort(points, (a,b) ->{
if(a[0] == b[0]){
return a[1] - b[1];
}
return a[0] - b[0];
});
int arrow = 1;
int start = points[0][0];
int end = points[0][1];
for(int i=0; i<points.length; i++){
if((points[i][0] >= start && points[i][0]<= end) ||
(end >=points[i][0] && end <= points[i][1])){
//Narrow the arrow point down
if(points[i][0] > start && points[i][0] <= end){
start = points[i][0];
}
if(points[i][1]>start && points[i][1] < end){
end = points[i][1];
}
continue;
}else{
// current arrow point is not satisfied with balloons
start = points[i][0];
end = points[i][1];
arrow ++;
}
}
return arrow;
}
로그인 후 복사
435. 겹치지 않는 간격
간격[i] = [starti, endi]인 간격의 배열이 주어지면 나머지 간격이 겹치지 않도록 제거해야 하는 최소 간격 수를 반환합니다.
예 1:
입력: 간격 = [[1,2],[2,3],[3,4],[1,3]]
출력: 1
설명: [1,3]은 제거할 수 있으며 나머지 간격은 겹치지 않습니다.
예시 2:
입력: 간격 = [[1,2],[1,2],[1,2]]
출력: 2
설명: 나머지 간격이 겹치지 않게 하려면 두 개의 [1,2]를 제거해야 합니다.
예시 3:
입력: 간격 = [[1,2],[2,3]]
출력: 0
설명: 이미 겹치지 않는 간격을 제거할 필요가 없습니다.
제약사항:
1 <= 간격.길이 <= 10^5
간격[i].길이 == 2
-5 * 10^4 <= 시작 < 엔디 <= 5 * 10^4
원본페이지
잘못된 코드
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length == 0){
return 0;
}
Arrays.sort(intervals, (a,b) ->{
if(a[0] == b[0]){
return a[1] - b[1];
}
return a[0] - b[0];
});
Arrays.stream(intervals)
.map(Arrays::toString)
.forEach(System.out::println);
int count = 0;
// List<int[]> list = new LinkedList<>();
int start = intervals[0][0];
int end = intervals[0][1];
for(int i=1; i<intervals.length; i++){
//if the left edge is not included in the previous interval the right will definitely not be in it.
if(intervals[i][0] >=start && intervals[i][0] <end){
count++;
continue;
}
start = intervals[i][0];
end = intervals[i][1];
// list.add(intervals[i]);
}
return count;
}
로그인 후 복사
고치다
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length == 0){
return 0;
}
Arrays.sort(intervals, (a,b) ->{
return a[0] - b[0];
});
int count = 0;
int start = intervals[0][0];
int end = intervals[0][1];
for(int i=1; i<intervals.length; i++){
if(intervals[i][0] < intervals[i-1][1]){
count++;
// here we need to find the maximum overlap, the means whether the next element overlap to above groups of overlaps
// if only find overlap from the previous interval, it may cause miss calculation over-add 1 count
intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
}
}
return count;
}
로그인 후 복사
763. 파티션 라벨
문자열 s가 주어졌습니다. 각 문자가 최대 한 부분에 나타나도록 문자열을 가능한 많은 부분으로 분할하려고 합니다.
모든 부분을 순서대로 연결한 후 결과 문자열은 s가 되도록 파티션이 수행되었습니다.
이 부품의 크기를 나타내는 정수 목록을 반환합니다.
예 1:
입력: s = "ababcbacadefegdehijhklij"
출력: [9,7,8]
설명:
파티션은 "ababcbaca", "defegde", "hijhklij"입니다.
각 문자가 최대 한 부분에 나타나도록 하는 파티션입니다.
"ababcbacadefegde", "hijhklij"와 같은 파티션은 s를 더 적은 부분으로 분할하므로 올바르지 않습니다.
예시 2:
입력: s = "eccbbbbdec"
출력: [10]
제약사항:
1 <= s.length <= 500
s는 영문 소문자로 구성됩니다.
원본페이지
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
Set<Character> set = new HashSet<>();
if(s.length() == 0){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
if(!set.contains(target)){
set.add(target);
int j = s.length()-1;
for(;j>i;j--){
if(s.charAt(j) == target){
break;
}
}
end = Math.max(end, j);
}
if(i == end){
list.add(end-start+1);
start = i+1;
set.clear();
}
}
return list;
}
</p>
<pre class="brush:php;toolbar:false"> public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
Set<Character> set = new HashSet<>();
int[] pos = new 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){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
if(!set.contains(target)){
set.add(target);
end = Math.max(end, pos[target-'a']);
}
if(i == end){
list.add(end-start+1);
start = i+1;
set.clear();
}
}
return list;
}
로그인 후 복사
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList<>();
int[] pos = new 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){
return list;
}
int start = 0;
int end = 0;
for(int i=0; i<s.length(); i++){
Character target = s.charAt(i);
end = Math.max(end, pos[target-'a']);
if(i == end){
list.add(end-start+1);
start = i+1;
}
}
return list;
}
로그인 후 복사
요소가 집합에 있었는지 평가하는 것은 중요하지 않기 때문에 끝에 도달했는지 여부에만 중점을 두고 동일한 요소가 발생하면 끝은 변경되지 않고 다른 요소가 병합되면, end가 변경될 수 있는 것처럼 보이지만 모두 if 평가에 영향을 미치지 않으므로 제거할 수 있습니다.
위 내용은 LeetCode DayGreedy 알고리즘 4부의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
