Algorithmes LeetCode DayGreedy, partie 2-javaDidacticiel-php.cn

Algorithmes LeetCode DayGreedy, partie 2

PHPz

Libérer： 2024-07-16 04:07:01

original

1087 Les gens l'ont consulté

LeetCode DayGreedy Algorithms Part 2

122. Meilleur moment pour acheter et vendre des actions II

Vous recevez un tableau de prix entiers où prix[i] est le prix d'une action donnée le ième jour.

Chaque jour, vous pouvez décider d'acheter et/ou de vendre des actions. Vous ne pouvez détenir qu’une seule action à la fois. Vous pouvez cependant l'acheter puis le revendre immédiatement le jour même.

Trouvez et restituez le profit maximum que vous pouvez réaliser.

Exemple 1 :

Entrée : prix = [7,1,5,3,6,4]
Sortie : 7
Explication : Achetez le jour 2 (prix = 1) et vendez le jour 3 (prix = 5), profit = 5-1 = 4.
Puis achetez le jour 4 (prix = 3) et vendez le jour 5 (prix = 6), profit = 6-3 = 3.
Le bénéfice total est de 4 + 3 = 7.
Exemple 2 :

Entrée : prix = [1,2,3,4,5]
Sortie : 4
Explication : Achetez le jour 1 (prix = 1) et vendez le jour 5 (prix = 5), profit = 5-1 = 4.
Le bénéfice total est de 4.
Exemple 3 :

Entrée : prix = [7,6,4,3,1]
Sortie : 0
Explication : Il n'y a aucun moyen de réaliser un profit positif, nous n'achetons donc jamais d'actions pour atteindre le profit maximum de 0.

Contraintes :

1 <= prix.longueur <= 3 * 104
0 <= prix[i] <= 104
Page originale

Mauvais code

    public int maxProfit(int[] prices) {
        int profit = 0;
        int buy = Integer.MAX_VALUE;
        int sum = 0;
        int peek = 0;

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if(num > buy && num > peek){
                profit = num - buy;
                peek = num;
            }
            else if((num>buy && num<peek) || num < buy){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }

        return sum+profit;
    }

Copier après la connexion

J'initialise l'achat sur int MAX_VALUE et j'oublie de mettre à jour, cela peut entraîner une erreur.

réparez cela et tronquez les codes

Code des amendes

    public int maxProfit(int[] prices) {
        if(prices.length <1){
            return 0;
        }
        int profit = 0;
        int buy = prices[0];
        int sum = 0;
        int peek = prices[0];

        for(int i=0; i<prices.length; i++){
            int num = prices[i];
            if( num > peek){
                profit = num - buy;
                peek = num;
            }
            else if(num<peek){
                sum += profit;
                profit = 0;
                buy = num;
                peek = num;
            }

        }
        sum += profit;
        return sum;
    }

Copier après la connexion

1005. Maximiser la somme du tableau après K négations

Étant donné un tableau entier nums et un entier k, modifiez le tableau de la manière suivante :

choisissez un index i et remplacez nums[i] par -nums[i].
Vous devez appliquer ce processus exactement k fois. Vous pouvez choisir le même index plusieurs fois.

Renvoyer la plus grande somme possible du tableau après l'avoir modifié de cette manière.

Exemple 1 :

Entrée : nums = [4,2,3], k = 1
Sortie : 5
Explication : Choisissez l'index 1 et les nombres deviennent [4,-2,3].
Exemple 2 :

Entrée : nums = [3,-1,0,2], k = 3
Sortie : 6
Explication : Choisissez les indices (1, 2, 2) et les nombres deviennent [3,1,0,2].
Exemple 3 :

Entrée : nums = [2,-3,-1,5,-4], k = 2
Sortie : 13
Explication : Choisissez les indices (1, 4) et les nombres deviennent [2,3,-1,5,4].

Contraintes :

1 <= nums.length <= 10^4
-100 <= nums[i] <= 100
1 <= k <= 10^4
Page originale

    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int change = nums[nums.length-1] >=0?0:nums.length-1;
        int sum = 0;
        for(int i=0; i<nums.length; i++){
            if(nums[i] < 0 && k>0){

                sum  -= nums[i];
                k--;
            }else{
                sum += nums[i];
            }
            // find the cross over 
            if(i>0 && nums[i-1]<=0 && nums[i]>0){
                if(-nums[i-1]>nums[i]){
                    change = i;
                }else{
                    change = i-1;
                }    
            }  
        }
        // k>nums.length so we need to run out of these k
        if(k>0){
            if(k%2!=0){
                //find the min abs value
                sum -= 2*Math.abs(nums[change]);
            }
        }
        return sum;
    }




</p>
<h2>
  
  
  55. Jeu de saut
</h2>

<p>Vous recevez un tableau de nombres entiers. Vous êtes initialement positionné au premier index du tableau et chaque élément du tableau représente votre longueur de saut maximale à cette position.</p>

<p>Renvoyer vrai si vous pouvez atteindre le dernier index, ou faux sinon.</p>

<p>Exemple 1 :</p>

<p>Entrée : nums = [2,3,1,1,4]<br>
Sortie : vrai<br>
Explication : Sauter 1 pas de l'index 0 à 1, puis 3 pas jusqu'au dernier index.<br>
Exemple 2 :</p>

<p>Entrée : nums = [3,2,1,0,4]<br>
Sortie : faux<br>
Explication : Vous arriverez toujours à l’index 3 quoi qu’il arrive. Sa longueur maximale de saut est de 0, ce qui rend impossible l'atteinte du dernier indice.</p>

<p>Contraintes :</p>

<p>1 <= nums.length <= 10^4<br>
0 <= nums[i] <= 10^5</p>
<h2>
  
  
  Mauvais code
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        //find whether achive the last element so that we only can see whether can reach the second last element 
        for(int i=0; i<nums.length-1;){
            int size = nums[i];
            int next = 0;
            int nextVal = 0;
            if(size == 0){
                return false;
            }
            if(i+size >= nums.length){
                return true;
            }
            //find the max steps among the current step
            for(int j=0; j<=size; j++){
                // calculate max for both index and value
                if(i+j+nums[i+j]>next){
                    next = i+j+nums[i+j];
                }
            }
            i = next;
        }
        return true;
    }


</p>
<h2>
  
  
  Mauvais code 2
</h2>


<pre class="brush:php;toolbar:false">    public boolean canJump(int[] nums) {
        if(nums.length==1){

            return true;
        }

        if(nums[0] == 0){
            return false;
        }

        for(int i=0; i<nums.length-1; i++){
            if(i+nums[i]>=nums.length-1){
                return true;
            }
        }

        return false;
    }

Copier après la connexion

    public boolean canJump(int[] nums) {
        if(nums.length==1){      
            return true;
        }

        int range = 0;

        for(int i=0; i<=range; i++){
            range = Math.max(range, i+nums[i]);
            if(range >= nums.length-1){
                return true;
            }
        }

        return false;
    }

Copier après la connexion

45. Jeu de saut II

Vous recevez un tableau de nombres entiers indexés 0 de longueur n. Vous êtes initialement positionné à nums[0].

Chaque élément nums[i] représente la longueur maximale d'un saut vers l'avant à partir de l'index i. En d'autres termes, si vous êtes à nums[i], vous pouvez accéder à n'importe quel nums[i + j] où :

0 <= j <= nums[i] et
je + j &Lt ; n
Renvoie le nombre minimum de sauts pour atteindre nums[n - 1]. Les cas de test sont générés de telle sorte que vous puissiez atteindre nums[n - 1].

Exemple 1 :

Entrée : nums = [2,3,1,1,4]
Sortie : 2
Explication : Le nombre minimum de sauts pour atteindre le dernier index est de 2. Sauter 1 pas de l'index 0 à 1, puis 3 pas jusqu'au dernier index.
Exemple 2 :

Entrée : nums = [2,3,0,1,4]
Sortie : 2

Contraintes :

1 <= nums.length <= 104
0 <= nums[i] <= 1000
C'est garanti que vous pourrez atteindre nums[n - 1].

    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int step = 0;
        int range = 0;
        int preRange = 0;
        for(int i=0; i= nums.length-1){
                step++;
                break;
            }
            if(i == preRange){
                preRange = range;
                step++;
            }

        }
        return step;

    }





          

            
        
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!