Algorithmes LeetCode DayGreedy, partie 4

452. Nombre minimum de flèches pour faire éclater des ballons

Il y a des ballons sphériques collés sur un mur plat qui représentent le plan XY. Les ballons sont représentés sous la forme d'un tableau d'entiers 2D où points[i] = [xstart, xend] désigne un ballon dont le diamètre horizontal s'étend entre xstart et xend. Vous ne connaissez pas les coordonnées y exactes des ballons.

Les flèches peuvent être tirées directement verticalement (dans la direction y positive) à partir de différents points le long de l'axe x. Un ballon avec xstart et xend est éclaté par une flèche tirée sur x si xstart <= x <= xend. Il n’y a pas de limite au nombre de flèches pouvant être tirées. Une flèche tirée continue de monter à l'infini, faisant éclater tous les ballons sur son passage.

Étant donné les points du tableau, renvoie le nombre minimum de flèches qui doivent être tirées pour faire éclater tous les ballons.

Exemple 1 :

Entrée : points = [[10,16],[2,8],[1,6],[7,12]]
Sortie : 2
Explication : Les ballons peuvent être éclatés par 2 flèches :

• Tirez une flèche en x = 6 en faisant éclater les ballons [2,8] et [1,6].
• Tirez une flèche en x = 11 en faisant éclater les ballons [10,16] et [7,12]. Exemple 2 :

Entrée : points = [[1,2],[3,4],[5,6],[7,8]]
Sortie : 4
Explication : Une flèche doit être tirée pour chaque ballon pour un total de 4 flèches.
Exemple 3 :

Entrée : points = [[1,2],[2,3],[3,4],[4,5]]
Sortie : 2
Explication : Les ballons peuvent être éclatés par 2 flèches :

• Tirez une flèche en x = 2 en faisant éclater les ballons [1,2] et [2,3].
• Tirez une flèche en x = 4 en faisant éclater les ballons [3,4] et [4,5].

Contraintes :

1 <= points.length <= 105
points[i].length == 2
-2^31 ≪= xstart ≪ xend <= 2^31 - 1
Page originale

    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. Intervalles sans chevauchement

Étant donné un tableau d'intervalles intervalles où intervalles[i] = [starti, endi], renvoie le nombre minimum d'intervalles que vous devez supprimer pour que le reste des intervalles ne se chevauchent pas.

Exemple 1 :

Entrée : intervalles = [[1,2],[2,3],[3,4],[1,3]]
Sortie : 1
Explication : [1,3] peut être supprimé et le reste des intervalles ne se chevauchent pas.
Exemple 2 :

Entrée : intervalles = [[1,2],[1,2],[1,2]]
Sortie : 2
Explication : Vous devez supprimer deux [1,2] pour que le reste des intervalles ne se chevauchent pas.
Exemple 3 :

Entrée : intervalles = [[1,2],[2,3]]
Sortie : 0
Explication : Vous n'avez pas besoin de supprimer aucun des intervalles car ils ne se chevauchent déjà pas.

Contraintes :

1 <= intervalles.longueur <= 10^5
intervalles[i].length == 2
-5 * 10^4 ≪= starti &Lt ; endi <= 5 * 10^4
Page originale

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

Réparez-le

    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. Étiquettes de partition

Vous recevez une chaîne s. Nous voulons diviser la chaîne en autant de parties que possible afin que chaque lettre apparaisse dans au plus une partie.

Notez que la partition est faite de telle sorte qu'après avoir concaténé toutes les parties dans l'ordre, la chaîne résultante soit s.

Renvoie une liste d'entiers représentant la taille de ces parties.

Exemple 1 :

Entrée : s = "ababcbacadefegdehijhklij"
Sortie : [9,7,8]
Explication :
La partition est "ababcbaca", "defegde", "hijhklij".
Il s'agit d'une partition pour que chaque lettre apparaisse dans au plus une partie.
Une partition comme "ababcbacadefegde", "hijhklij" est incorrecte, car elle divise s en moins de parties.
Exemple 2 :

Entrée : s = "eccbbbbdec"
Sortie : [10]

Contraintes :

1 <= s.length <= 500
s se compose de lettres anglaises minuscules.
Page originale

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

Parce qu'il n'est pas important pour évaluer si l'élément a été dans l'ensemble, nous nous concentrons uniquement sur si la fin est atteinte ou non, et si les mêmes éléments se produisent, la fin ne changera pas et si les différents éléments fusionnent, il semble que la fin puisse changer, mais tous n'auront pas d'impact sur l'évaluation if, nous pouvons donc les supprimer.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!