Heim Java javaLernprogramm LeetCode DayGreedy-Algorithmus Teil 1

LeetCode DayGreedy-Algorithmus Teil 1

Jul 12, 2024 pm 04:51 PM

LeetCode DayGreedy Algorithm Part 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;   
    }
Nach dem Login kopieren

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 <= nums.length <= 1000<br>
0 <= nums[i] <= 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<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;
}
Nach dem Login kopieren

`

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;

}
Nach dem Login kopieren

`

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;

}
Nach dem Login kopieren

`

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;

}
Nach dem Login kopieren

`

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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
3 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Top 4 JavaScript -Frameworks in 2025: React, Angular, Vue, Svelte Top 4 JavaScript -Frameworks in 2025: React, Angular, Vue, Svelte Mar 07, 2025 pm 06:09 PM

Top 4 JavaScript -Frameworks in 2025: React, Angular, Vue, Svelte

Wie implementiere ich mehrstufige Caching in Java-Anwendungen mit Bibliotheken wie Koffein oder Guava-Cache? Wie implementiere ich mehrstufige Caching in Java-Anwendungen mit Bibliotheken wie Koffein oder Guava-Cache? Mar 17, 2025 pm 05:44 PM

Wie implementiere ich mehrstufige Caching in Java-Anwendungen mit Bibliotheken wie Koffein oder Guava-Cache?

Wie funktioniert der Klassenladungsmechanismus von Java, einschließlich verschiedener Klassenloader und deren Delegationsmodelle? Wie funktioniert der Klassenladungsmechanismus von Java, einschließlich verschiedener Klassenloader und deren Delegationsmodelle? Mar 17, 2025 pm 05:35 PM

Wie funktioniert der Klassenladungsmechanismus von Java, einschließlich verschiedener Klassenloader und deren Delegationsmodelle?

Node.js 20: wichtige Leistungssteigerung und neue Funktionen Node.js 20: wichtige Leistungssteigerung und neue Funktionen Mar 07, 2025 pm 06:12 PM

Node.js 20: wichtige Leistungssteigerung und neue Funktionen

ICEBERG: Die Zukunft von Data Lake Tabellen ICEBERG: Die Zukunft von Data Lake Tabellen Mar 07, 2025 pm 06:31 PM

ICEBERG: Die Zukunft von Data Lake Tabellen

Spring Boot Snakeyaml 2.0 CVE-2022-1471 Problem behoben Spring Boot Snakeyaml 2.0 CVE-2022-1471 Problem behoben Mar 07, 2025 pm 05:52 PM

Spring Boot Snakeyaml 2.0 CVE-2022-1471 Problem behoben

Wie kann ich JPA (Java Persistence-API) für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden verwenden? Wie kann ich JPA (Java Persistence-API) für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden verwenden? Mar 17, 2025 pm 05:43 PM

Wie kann ich JPA (Java Persistence-API) für Objektrelationszuordnungen mit erweiterten Funktionen wie Caching und faulen Laden verwenden?

Wie benutze ich Maven oder Gradle für das fortschrittliche Java -Projektmanagement, die Erstellung von Automatisierung und Abhängigkeitslösung? Wie benutze ich Maven oder Gradle für das fortschrittliche Java -Projektmanagement, die Erstellung von Automatisierung und Abhängigkeitslösung? Mar 17, 2025 pm 05:46 PM

Wie benutze ich Maven oder Gradle für das fortschrittliche Java -Projektmanagement, die Erstellung von Automatisierung und Abhängigkeitslösung?

See all articles