enregistrement de questions lintcode 4

Enveloppes de poupée russe

Problème d'imbrication de poupées russes, c'est un problème typique de dp... La traversée forcée entraînera un délai d'attente, mais je n'ai pas trouvé comment le résoudre depuis longtemps, j'ai cherché en ligne et attribué le problème. pour trouver l'incrément le plus long. Problème de sous-séquence... Cependant, je suis stupide et je n'arrive toujours pas à comprendre pourquoi cela peut être fait... Bien que le résultat soit correct...

Triez d'abord les données et utilisez la fonction de tri intégrée de python pour trier. Cependant, lorsque x est égal, y doit être trié du plus grand au plus petit, donc un cmp doit être transmis. python3.x. ne prend pas en charge cmp. J'ai donc utilisé une conversion pour la convertir en clé. Si la clé est directement définie sur x, le y par défaut sera tourné de petit à grand

.

Le résultat de ce calcul est correct, mais le dp de cette itération n'est pas une séquence valide... mais la longueur est correcte...

<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)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!