lintcode題目記錄4

Russian Doll Envelopes

俄羅斯玩偶嵌套問題，這個是典型的dp問題···強行遍歷會提示超時，然而整了好久也沒整明白怎麼整，網上搜了下把問題歸結為求最長遞增子序列問題··然而本人愚鈍還是想不明白為啥可以這樣做··雖然出來的結果是對的····

#先把資料排序， 用python內建的排序函數進行排序，但是因為當x相等時，y要按從大到小拍，所以要傳一個cmp進去，python3.x不支援cmp了所以用了一個轉換，轉換成key，如果直接key設定為x預設y會按從小到大拍

#這樣算的結果是對的·但是那個迭代的dp不是一個有效的序列···但是長度是對的···

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

 

以上是lintcode題目記錄4的詳細內容。更多資訊請關注PHP中文網其他相關文章！