Heim> Java> javaLernprogramm> Hauptteil

LeetCode Day Dynamische Programmierung Teil 10

王林
Freigeben: 2024-07-19 13:07:01
Original
212 Leute haben es durchsucht

LeetCode Day Dynamic Programming Part 10

300. Längste ansteigende Folge

Bei einem ganzzahligen Array nums wird die Länge des längsten streng ansteigenden
zurückgegeben Folge
.

Beispiel 1:

Eingabe: nums = [10,9,2,5,3,7,101,18]
Ausgabe: 4
Erläuterung: Die längste ansteigende Teilfolge ist [2,3,7,101], daher beträgt die Länge 4,
Beispiel 2:

Eingabe: nums = [0,1,0,3,2,3]
Ausgabe: 4
Beispiel 3:

Eingabe: nums = [7,7,7,7,7,7,7]
Ausgabe: 1

Einschränkungen:

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

Follow-up: Können Sie einen Algorithmus entwickeln, der mit einer Zeitkomplexität von O(n log(n)) ausgeführt wird?
Originalseite

Falscher Code

public int lengthOfLIS(int[] nums) { int start = nums[0]; int pre = nums[0]; int preMax = nums[0]; int cnt = 1; int max = 1; for(int i=1; i pre){ cnt ++; } pre = nums[i]; System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt); } return Math.max(max, cnt); } 

Fehler beheben


        
Nach dem Login kopieren
Nach dem Login kopieren

Von anderen lernen Baumkarte

public int lengthOfLIS(int[] nums) { TreeMap map = new TreeMap<>(); map.put(Integer.MIN_VALUE,0); for(int i: nums) { map.put(i,map.get(map.lowerKey(i))+1); while(map.higherKey(i)!=null && map.get(map.higherKey(i))<=map.get(i)) { map.remove(map.higherKey(i)); } } return map.get(map.lastKey()); }
Nach dem Login kopieren

674. Längste kontinuierlich ansteigende Folge

Gibt bei einem unsortierten Array ganzzahliger Zahlen die Länge der längsten kontinuierlich ansteigenden Teilsequenz (d. h. Subarray) zurück. Die Teilfolge muss streng ansteigend sein.

Eine kontinuierlich steigende Teilfolge wird durch zwei Indizes l und r (l < r) definiert, sodass sie [nums[l], nums[l + 1], ..., nums[r - 1], nums[r ist ]] und für jedes l <= i < r, nums[i] < nums[i + 1].

Beispiel 1:

Eingabe: nums = [1,3,5,4,7]
Ausgabe: 3
Erläuterung: Die längste kontinuierlich ansteigende Teilfolge ist [1,3,5] mit der Länge 3.
Obwohl [1,3,5,7] eine aufsteigende Teilfolge ist, ist sie nicht stetig, da die Elemente 5 und 7 durch Elemente getrennt sind
4.
Beispiel 2:

Eingabe: nums = [2,2,2,2,2]
Ausgabe: 1
Erläuterung: Die längste kontinuierlich ansteigende Teilfolge ist [2] mit der Länge 1. Beachten Sie, dass sie streng sein muss
zunehmend.

Einschränkungen:

1 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
Originalseite

Gieriger Algorithmus

public int findLengthOfLCIS(int[] nums) { if(nums.length < 1){ return 0; } int res = 1; int cnt = 1; int pre = nums[0]; for(int i=1; i pre){ cnt++; }else{ res = Math.max(res, cnt); cnt = 1; } // System.out.println("cur: " + nums[i] + " pre:" + pre + " count:" + cnt); pre = nums[i]; } return Math.max(res, cnt); }
Nach dem Login kopieren

Dynamische Programmierung

Anders als bei der vorherigen Frage konnten wir bei dieser Frage nur kontinuierlich steigende Teilsequenzen berücksichtigen, was den Prozess vereinfacht.


       
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonLeetCode Day Dynamische Programmierung Teil 10. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Quelle:dev.to
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
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage
Über uns Haftungsausschluss Sitemap
Chinesische PHP-Website:Online-PHP-Schulung für das Gemeinwohl,Helfen Sie PHP-Lernenden, sich schnell weiterzuentwickeln!