LeetCode DayGreedy-Algorithmen Teil 4

452. Mindestanzahl an Pfeilen, um Ballons zum Platzen zu bringen

Auf einer flachen Wand, die die XY-Ebene darstellt, sind einige kugelförmige Ballons aufgeklebt. Die Ballons werden als 2D-Integer-Array-Punkte dargestellt, wobei Punkte[i] = [xstart, xend] einen Ballon bezeichnet, dessen horizontaler Durchmesser sich zwischen xstart und xend erstreckt. Sie kennen die genauen Y-Koordinaten der Ballons nicht.

Pfeile können von verschiedenen Punkten entlang der x-Achse direkt vertikal (in positiver y-Richtung) nach oben geschossen werden. Ein Ballon mit xstart und xend wird durch einen auf x geschossenen Pfeil zerplatzt, wenn xstart <= x <= xend. Es gibt keine Begrenzung für die Anzahl der Pfeile, die abgefeuert werden können. Ein abgeschossener Pfeil bewegt sich unendlich weiter nach oben und lässt alle Ballons auf seinem Weg platzen.

Geben Sie anhand der Array-Punkte die Mindestanzahl an Pfeilen zurück, die abgeschossen werden müssen, um alle Ballons zum Platzen zu bringen.

Beispiel 1:

Eingabe: Punkte = [[10,16],[2,8],[1,6],[7,12]]
Ausgabe: 2
Erklärung: Die Ballons können durch 2 Pfeile zum Platzen gebracht werden:

• Schieße einen Pfeil auf x = 6, wodurch die Ballons [2,8] und [1,6] platzen.
• Schieße einen Pfeil auf x = 11, wodurch die Ballons [10,16] und [7,12] platzen. Beispiel 2:

Eingabe: Punkte = [[1,2],[3,4],[5,6],[7,8]]
Ausgabe: 4
Erklärung: Für jeden Ballon muss ein Pfeil abgefeuert werden, also insgesamt 4 Pfeile.
Beispiel 3:

Eingabe: Punkte = [[1,2],[2,3],[3,4],[4,5]]
Ausgabe: 2
Erklärung: Die Ballons können durch 2 Pfeile zum Platzen gebracht werden:

• Schieße einen Pfeil auf x = 2, wodurch die Ballons [1,2] und [2,3] platzen.
• Schieße einen Pfeil auf x = 4, wodurch die Ballons [3,4] und [4,5] platzen.

Einschränkungen:

1 <= Punkte.Länge <= 105
Punkte[i].Länge == 2
-2^31 <= xstart < xend <= 2^31 - 1
Originalseite

    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. Nicht überlappende Intervalle

Gibt bei einem gegebenen Array von Intervallen, wobei Intervalle[i] = [starti, endi] ist, die Mindestanzahl an Intervallen zurück, die entfernt werden müssen, damit sich die restlichen Intervalle nicht überlappen.

Beispiel 1:

Eingabe: Intervalle = [[1,2],[2,3],[3,4],[1,3]]
Ausgabe: 1
Erläuterung: [1,3] kann entfernt werden und die restlichen Intervalle überlappen sich nicht.
Beispiel 2:

Eingabe: Intervalle = [[1,2],[1,2],[1,2]]
Ausgabe: 2
Erläuterung: Sie müssen zwei [1,2] entfernen, damit sich die restlichen Intervalle nicht überlappen.
Beispiel 3:

Eingabe: Intervalle = [[1,2],[2,3]]
Ausgabe: 0
Erläuterung: Sie müssen keines der Intervalle entfernen, da sie sich bereits nicht überlappen.

Einschränkungen:

1 <= Intervalle.Länge <= 10^5
Intervalle[i].length == 2
-5 * 10^4 <= starti < endi <= 5 * 10^4
Originalseite

Falscher Code

    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;
    }

Repariere es

    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. Partitionsbezeichnungen

Sie erhalten eine Zeichenfolge s. Wir möchten die Zeichenfolge in möglichst viele Teile unterteilen, sodass jeder Buchstabe in höchstens einem Teil vorkommt.

Beachten Sie, dass die Partitionierung so erfolgt, dass nach der Verkettung aller Teile in der richtigen Reihenfolge die resultierende Zeichenfolge s. sein sollte.

Gibt eine Liste von Ganzzahlen zurück, die die Größe dieser Teile darstellen.

Beispiel 1:

Eingabe: s = "ababcbacadefegdehijhklij"
Ausgabe: [9,7,8]
Erklärung:
Die Partition ist „ababcbaca“, „defegde“, „hijhklij“.
Dies ist eine Partition, sodass jeder Buchstabe höchstens in einem Teil vorkommt.
Eine Partition wie „ababcbacadefegde“, „hijhklij“ ist falsch, da sie s in weniger Teile aufteilt.
Beispiel 2:

Eingabe: s = "eccbbbbdec"
Ausgabe: [10]

Einschränkungen:

1 <= s.length <= 500
s besteht aus englischen Kleinbuchstaben.
Originalseite

    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;
    }

Da es für die Beurteilung nicht wichtig ist, ob das Element in der Menge enthalten war, konzentrieren wir uns nur darauf, ob das Ende erreicht ist oder nicht, und wenn die gleichen Elemente vorkommen, wird sich das Ende nicht ändern und wenn die verschiedenen Elemente verschmelzen, Es sieht so aus, als ob sich das Ende ändern könnte, aber alle davon werden sich nicht auf die if-Auswertung auswirken, sodass wir sie entfernen können.

Das obige ist der detaillierte Inhalt vonLeetCode DayGreedy-Algorithmen Teil 4. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!