LeetCode Day Dynamische Programmierung Teil 10

300. Längste ansteigende Folge

Gibt bei einem gegebenen ganzzahligen Array nums die Länge des längsten streng ansteigenden
zurück Teilsequenz
.

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

Weitere Informationen: Können Sie einen Algorithmus entwickeln, der in O(n log(n)) Zeitkomplexität 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<nums.length; i++){
            if(nums[i] < start){
                max = Math.max(max, cnt);
                start = nums[i];
                cnt = 1;
            } 
            else if(nums[i] > pre){
                cnt ++;
            }
            pre = nums[i];
            System.out.println("cur:"+nums[i] + " pre:"+pre+ " count:" + cnt);
        }
        return Math.max(max, cnt);
    }


</p>
<h2>
  
  
  Fehler beheben
</h2>


<div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">

Nach dem Login kopieren

Von anderen lernen Baumkarte

    public int lengthOfLIS(int[] nums) {


        TreeMap<Integer,Integer> 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());

    }

---

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 ist [r]] 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.
Auch wenn [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

Greedy-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<nums.length; i++){
            if(nums[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);
    }

Dynamische Programmierung

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

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!