欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

lintcode题目记录4

程序员文章站 2022-04-10 09:37:05
...

Russian Doll Envelopes

俄罗斯玩偶嵌套问题,这个是典型的dp问题···强行遍历会提示超时,然而整了好久也没整明白怎么整,网上搜了下 把问题归结为求最长递增子序列问题··然而本人愚钝还是想不明白为啥可以这样做··虽然出来的结果是对的·····

先把数据排序, 用python内建的排序函数进行排序,但是因为当x相等时,y要按从大到小拍,所以要传一个cmp进去,python3.x不支持cmp了 所以 用了一个转换,转换成key,如果直接key设置为x默认y会按从小到大拍

这样算的结果是对的·但是那个迭代的dp不是一个有效的序列···但是长度是对的···

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

 

以上就是lintcode题目记录4的详细内容,更多请关注其它相关文章!