LeetCode DayGreedy-Algorithmus Teil 1

455. Cookies zuweisen

Angenommen, Sie sind ein toller Elternteil und möchten Ihren Kindern ein paar Kekse geben. Aber Sie sollten jedem Kind höchstens einen Keks geben.

Jedes Kind i hat einen Gierfaktor g[i], der die Mindestgröße eines Cookies angibt, mit dem das Kind zufrieden ist; und jedes Cookie j hat eine Größe s[j]. Wenn s[j] >= g[i] ist, können wir das Cookie j dem Kind i zuweisen, und das Kind i wird zufrieden sein. Ihr Ziel ist es, die Anzahl Ihrer Content-Kinder zu maximieren und die maximale Anzahl auszugeben.

Beispiel 1:

Eingabe: g = [1,2,3], s = [1,1]
Ausgabe: 1
Erläuterung: Sie haben 3 Kinder und 2 Kekse. Die Gierfaktoren von 3 Kindern sind 1, 2, 3.
Und selbst wenn Sie 2 Kekse haben, können Sie nur das Kind zufriedenstellen, dessen Gierfaktor 1 beträgt, da beide die Größe 1 haben.
Sie müssen 1 ausgeben.
Beispiel 2:

Eingabe: g = [1,2], s = [1,2,3]
Ausgabe: 2
Erläuterung: Sie haben 2 Kinder und 3 Kekse. Die Gierfaktoren von 2 Kindern sind 1, 2.
Du hast 3 Kekse und ihre Größe ist groß genug, um alle Kinder zufrieden zu stellen,
Sie müssen 2 ausgeben.

Einschränkungen:

1 <= g.length <= 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;   
    }

Zeit: n`logn

Eine andere Version für die Schleife
`
public int findContentChildren(int[] g, int[] s) {
// Nullzeiger vermeiden
if(g.length == 0 || s.length ==0){
return 0;
}
// 2 * nlogn
Arrays.sort(g);
Arrays.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. Wiggle-Folge
</h2>

<p>Eine Wackelsequenz ist eine Sequenz, bei der die Unterschiede zwischen aufeinanderfolgenden Zahlen streng zwischen positiv und negativ wechseln. Der erste Unterschied (falls vorhanden) kann entweder positiv oder negativ sein. Eine Folge mit einem Element und eine Folge mit zwei ungleichen Elementen sind trivialerweise Wiggle-Folgen.</p>

<p>Zum Beispiel ist [1, 7, 4, 9, 2, 5] eine Wackelsequenz, da die Differenzen (6, -3, 5, -7, 3) zwischen positiv und negativ wechseln.<br>
Im Gegensatz dazu sind [1, 4, 7, 2, 5] und [1, 7, 4, 5, 5] keine Wiggle-Sequenzen. Das erste liegt nicht daran, dass die ersten beiden Differenzen positiv sind, und das zweite nicht daran, dass die letzte Differenz Null ist.<br>
Eine Teilsequenz wird erhalten, indem einige Elemente (möglicherweise Null) aus der Originalsequenz gelöscht werden und die übrigen Elemente in ihrer ursprünglichen Reihenfolge belassen werden.</p>

<p>Gibt bei einem gegebenen ganzzahligen Array „nums“ die Länge der längsten Wiggle-Teilfolge von „nums“ zurück.</p>

<p>Beispiel 1:</p>

<p>Eingabe: nums = [1,7,4,9,2,5]<br>
Ausgabe: 6<br>
Erläuterung: Die gesamte Sequenz ist eine Wackelsequenz mit Unterschieden (6, -3, 5, -7, 3).<br>
Beispiel 2:</p>

<p>Eingabe: nums = [1,17,5,10,13,15,10,5,16,8]<br>
Ausgabe: 7<br>
Erläuterung: Es gibt mehrere Teilsequenzen, die diese Länge erreichen.<br>
Eine davon ist [1, 17, 10, 13, 10, 16, 8] mit Unterschieden (16, -7, 3, -3, 6, -8).<br>
Beispiel 3:</p>

<p>Eingabe: nums = [1,2,3,4,5,6,7,8,9]<br>
Ausgabe: 2</p>

<p>Einschränkungen:</p>

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

<p>Nachfassen: Konnten Sie das Problem in O(n) Zeit lösen?</p>

<p>`<br>
    public int wiggleMaxLength(int[] nums) {<br>
        if(nums.length == 0){<br>
            return 0;<br>
        }<br>
        int count = 1;<br>
        int preFlag = 0;<br>
        int pre = nums[0];</p>

<pre class="brush:php;toolbar:false">    for(int i=1; i&lt;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. Maximales Subarray

Suchen Sie bei einem gegebenen ganzzahligen Array nums das
Unterarray
mit der größten Summe und geben Sie die Summe zurück.

Beispiel 1:

Eingabe: nums = [-2,1,-3,4,-1,2,1,-5,4]
Ausgabe: 6
Erläuterung: Das Subarray [4,-1,2,1] hat die größte Summe 6.
Beispiel 2:

Eingabe: nums = [1]
Ausgabe: 1
Erläuterung: Das Subarray [1] hat die größte Summe 1.
Beispiel 3:

Eingabe: nums = [5,4,-1,7,8]
Ausgabe: 23
Erläuterung: Das Subarray [5,4,-1,7,8] hat die größte Summe 23.

Einschränkungen:

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

Folge: Wenn Sie die O(n)-Lösung herausgefunden haben, versuchen Sie, eine andere Lösung mit dem „Teile-und-Herrsche“-Ansatz zu programmieren, der subtiler ist.

`
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(nums[i] > 0){
if(sum < 0){
sum = nums[i];
}else{
sum += 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<nums.length; 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;

}

`

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