Lintcode-Fragedatensatz 4

Russische Puppenumschläge

Russisches Puppennestproblem, das ist ein typisches DP-Problem ... Die erzwungene Durchquerung führt zu einer Zeitüberschreitung, aber ich habe lange nicht herausgefunden, wie ich das Problem beheben kann, und habe das Problem zugeschrieben um das längste Inkrementproblem zu finden ... Ich bin jedoch dumm und kann immer noch nicht herausfinden, warum dies möglich ist ... Obwohl das Ergebnis korrekt ist ...

Sortieren Sie zuerst die Daten und verwenden Sie zum Sortieren die integrierte Sortierfunktion von Python. Wenn x jedoch gleich ist, muss y von groß nach klein sortiert werden, sodass ein cmp übergeben werden muss. python3.x unterstützt cmp nicht. Daher habe ich eine Konvertierung verwendet, um es in den Schlüssel umzuwandeln. Wenn der Schlüssel direkt auf x gesetzt ist, wird der Standardwert von y von klein nach groß geschossen

Das Ergebnis dieser Berechnung ist korrekt, aber der dp dieser Iteration ist keine gültige Sequenz... aber die Länge ist korrekt...

<span style="color: #0000ff">class</span><span style="color: #000000"> Solution:
    </span><span style="color: #008000">#</span><span style="color: #008000"> @param {int[][]} envelopes a number of envelopes with widths and heights</span>
    <span style="color: #008000">#</span><span style="color: #008000"> @return {int} the maximum number of envelopes</span>
    <span style="color: #0000ff">def</span><span style="color: #000000"> maxEnvelopes(self, envelopes):
        </span><span style="color: #008000">#</span><span style="color: #008000"> Write your code here</span>
        <span style="color: #0000ff">import</span><span style="color: #000000"> functools
        nums </span>= sorted(envelopes,key= functools.cmp_to_key(<span style="color: #0000ff">lambda</span> x,y:x[0]-y[0] <span style="color: #0000ff">if</span> x[0] != y[0] <span style="color: #0000ff">else</span> y[1] - x[1<span style="color: #000000">]))
        size </span>=<span style="color: #000000"> len(nums)
        dp </span>=<span style="color: #000000"> []
        </span><span style="color: #0000ff">for</span> x <span style="color: #0000ff">in</span><span style="color: #000000"> range(size):
            low, high </span>= 0, len(dp) - 1
            <span style="color: #0000ff">while</span> low <=<span style="color: #000000"> high:
                mid </span>= (low + high)//2
                <span style="color: #0000ff">if</span> dp[mid][1] < nums[x][1<span style="color: #000000">]:
                    low </span>= mid + 1
                <span style="color: #0000ff">else</span><span style="color: #000000">:
                    high </span>= mid - 1
            <span style="color: #0000ff">if</span> low <<span style="color: #000000"> len(dp):
                dp[low] </span>=<span style="color: #000000"> nums[x]
            </span><span style="color: #0000ff">else</span><span style="color: #000000">:
                dp.append(nums[x])
        </span><span style="color: #0000ff">return</span> len(dp)

Das obige ist der detaillierte Inhalt vonLintcode-Fragedatensatz 4. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!