LeetCode DayGreedy 알고리즘 4부

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!