lintcode题目记录4

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的详细内容...