lintcode题目记录4

Russian Doll Envelopes Largest Divisible Subset Two Sum - Input array is sorted

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)

Largest Divisible Subset

标签写的是动态规划 ·感觉没啥规划还是直接强行遍历的··

class Solution:

    # @param {int[]} nums a set of distinct positive integers

    # @return {int[]} the largest subset

    def largestDivisibleSubset(self, nums):

        # Write your code here

        n=len(nums)

        nums= sorted(nums,reverse=True)

        res=[]

        res.append([nums[0]])

        for i in range(1,n):

            cur=nums[i]

            for r in res:

                if  r[-1] % cur== 0:

                    r.append(cur)

            if i==1:res.append([nums[0]])

            res.append([nums[i]])

        res=sorted(res,key=lambda x:len(x),reverse=True)

        return res[0]

Two Sum - Input array is sorted

有序数组，找出一个组合之和是给定目标值，题目写的有序基本就是说用二分查找吧···，而且还要求index2>index1相当简单了··，遍历一遍就可以了··

class Solution:

    """

    @param nums {int[]} n array of Integer

    @param target {int} = nums[index1] + nums[index2]

    @return {int[]} [index1 + 1, index2 + 1] (index1 < index2)

    """

    def twoSum(self, nums, target):

        # Write your code here

        index1=0

        index2=-1

        for i in range(len(nums)-1):

            index1 = i

            index2 = -1

            start = i+1

            end = len(nums)-1

            st = target - nums[index1]

            while start <= end:

                mid = (start + end) // 2

                if nums[mid] < st:

                    start = mid + 1

                elif nums[mid] > st:

                    end = mid - 1

                else:

                    index2 = mid

                    return [index1 + 1, index2 + 1]

巴特西

lintcode题目记录4

Russian Doll Envelopes Largest Divisible Subset Two Sum - Input array is sorted

Russian Doll Envelopes

Largest Divisible Subset

Two Sum - Input array is sorted

最新文章

热门文章