Algorithme LeetCode DayGreedy, partie 1

455. Attribuer des cookies

Supposons que vous êtes un parent génial et que vous souhaitez offrir des cookies à vos enfants. Mais vous devriez donner à chaque enfant au plus un cookie.

Chaque enfant i a un facteur de cupidité g[i], qui est la taille minimale d'un cookie dont l'enfant se contentera ; et chaque cookie j a une taille s[j]. Si s[j] >= g[i], nous pouvons attribuer le cookie j à l'enfant i, et l'enfant i sera content. Votre objectif est de maximiser le nombre de vos enfants de contenu et d'en générer le nombre maximum.

Exemple 1 :

Entrée : g = [1,2,3], s = [1,1]
Sortie : 1
Explication : Vous avez 3 enfants et 2 cookies. Les facteurs de cupidité de 3 enfants sont 1, 2, 3.
Et même si vous avez 2 cookies, puisque leur taille est tous deux de 1, vous ne pouvez faire en sorte que l'enfant dont le facteur gourmandise est de 1 soit contenu.
Vous devez sortir 1.
Exemple 2 :

Entrée : g = [1,2], s = [1,2,3]
Sortie : 2
Explication : Vous avez 2 enfants et 3 cookies. Les facteurs de cupidité de 2 enfants sont 1, 2.
Vous disposez de 3 cookies et leurs tailles sont suffisamment grandes pour gratifier tous les enfants,
Vous devez sortir 2.

Contraintes :

1 <= g.longueur <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1

    public int findContentChildren(int[] g, int[] s) {
        // avoid null pointer
        if(g.length == 0 || s.length ==0){
            return 0;
        }
        // 2 * nlogn
        Arrays.sort(g);
        Arrays.sort(s);

        int i = 0;
        int j = 0;
        int count = 0;
        while(i < g.length && j < s.length){
            if(g[i] <= s[j]){
                i++;
                j++;
                count++;
            } else{
                j++;
            }
        }
        return count;   
    }

heure : n`logn

Une autre version pour loop
`
public int findContentChildren(int[] g, int[] s) {
// évite le pointeur nul
if(g.length == 0 || s.length ==0){
renvoie 0 ;
>
// 2 * nlogn
Arrays.sort(g);
Tableaux.sort(s);

    int j = 0;
    int count = 0;
    for(int i=0; i<s.length && j<g.length; i++){
        if(s[i] >= g[j]){
            j++;
            count++;
        }
    }
    return count;   
}


</p>
<p>`</p>

<h2>
  
  
  376. Sous-séquence de mouvements
</h2>

<p>Une séquence de tremblements est une séquence où les différences entre nombres successifs alternent strictement entre positifs et négatifs. La première différence (si elle existe) peut être positive ou négative. Une séquence avec un élément et une séquence avec deux éléments non égaux sont des séquences trivialement agitées.</p>

<p>Par exemple, [1, 7, 4, 9, 2, 5] est une séquence agitée car les différences (6, -3, 5, -7, 3) alternent entre positives et négatives.<br>
En revanche, [1, 4, 7, 2, 5] et [1, 7, 4, 5, 5] ne sont pas des séquences agitées. La première n'est pas parce que ses deux premières différences sont positives, et la seconde n'est pas parce que sa dernière différence est nulle.<br>
Une sous-séquence est obtenue en supprimant certains éléments (éventuellement zéro) de la séquence d'origine, en laissant les éléments restants dans leur ordre d'origine.</p>

<p>Étant donné un tableau d'entiers nums, renvoie la longueur de la sous-séquence de nums la plus longue.</p>

<p>Exemple 1 :</p>

<p>Entrée : nums = [1,7,4,9,2,5]<br>
Sortie : 6<br>
Explication : La séquence entière est une séquence de mouvements avec des différences (6, -3, 5, -7, 3).<br>
Exemple 2 :</p>

<p>Entrée : nums = [1,17,5,10,13,15,10,5,16,8]<br>
Sortie : 7<br>
Explication : Il existe plusieurs sous-séquences qui atteignent cette longueur.<br>
L'un est [1, 17, 10, 13, 10, 16, 8] avec des différences (16, -7, 3, -3, 6, -8).<br>
Exemple 3 :</p>

<p>Entrée : nums = [1,2,3,4,5,6,7,8,9]<br>
Sortie : 2</p>

<p>Contraintes :</p>

<p>1 <= nums.length <= 1000<br>
0 <= nums[i] <= 1000</p>

<p>Suivi : Pourriez-vous résoudre ce problème en un temps O(n) ?</p>

<p>`<br>
    public int wiggleMaxLength(int[] nums) {<br>
        if(nums.length == 0){<br>
            renvoie 0 ;<br>
        ><br>
        nombre int = 1;<br>
        int préFlag = 0;<br>
        int pré = nums[0];</p>

<pre class="brush:php;toolbar:false">    for(int i=1; i<nums.length; i++){
        if(nums[i]-nums[i-1] != 0){
            int flag = (nums[i]-nums[i-1])/Math.abs(nums[i]-nums[i-1]);

            if(flag == -preFlag || preFlag == 0){
                preFlag = flag;
                count++;
            }
        }
    }
    return count;
}

`

53. Sous-tableau maximum

Étant donné un tableau entier nums, trouvez le
sous-tableau
avec la plus grande somme, et renvoie sa somme.

Exemple 1 :

Entrée : nums = [-2,1,-3,4,-1,2,1,-5,4]
Sortie : 6
Explication : Le sous-tableau [4,-1,2,1] a la plus grande somme 6.
Exemple 2 :

Entrée : nums = [1]
Sortie : 1
Explication : Le sous-tableau [1] a la plus grande somme 1.
Exemple 3 :

Entrée : nums = [5,4,-1,7,8]
Sortie : 23
Explication : Le sous-tableau [5,4,-1,7,8] a la plus grande somme 23.

Contraintes :

1 <= nums.length <= 105
-104 <= nums[i] <= 104

Suivi : si vous avez trouvé la solution O(n), essayez de coder une autre solution en utilisant l'approche diviser pour mieux régner, qui est plus subtile.

`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
renvoie 0 ;
>
int max = Entier.MIN_VALUE;
somme int = Integer.MIN_VALUE;
pour (int je = 0; je if(nums[i] > 0){
si (somme < 0) {
somme = nums[i];
}autre{
somme += nums[i];

            }
            max = Math.max(max, sum);
        }else{
            if(sum<0){
                sum = nums[i];
            }else{
            sum += nums[i];
            }
            max = Math.max(max, sum);
        }
    }
    return max;

}

`

improve code
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
int sum = Integer.MIN_VALUE;
for(int i=0; i if(sum < 0){
sum = nums[i];
}else{
sum += nums[i];

            }
            max = Math.max(max, sum);
    }
    return max;

}

`

Another way for greedy
`
public int maxSubArray(int[] nums) {
if(nums.length == 0){
return 0;
}
int max = Integer.MIN_VALUE;
// int sum = Integer.MIN_VALUE;

    int sum = 0;
    for(int i=0; i<nums.length; i++){
        sum+= nums[i];
        if(max < sum){
            max = sum;
        }
        if(sum <0){
            sum = 0;
        }
            // if(sum < 0){
            //     sum = nums[i];
            // }else{
            //     sum += nums[i];

            // }
            // max = Math.max(max, sum);

    }
    return max;

}

`

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!