新浪8.18算法笔经

class Solution(object):
    def maxEnvelopes(self, envelopes):
        """
        :type envelopes: List[List[int]]
        :rtype: int
        """
        # 先将信封按宽度排序
        envelopes.sort(key=lambda x:(x[0],-x[1]))
        # 将问题转换为最长上升子序列
        # dp[i]表示第i个信封可以装多少个信
        dp = [1]*len(envelopes)
        dp[0] = 1
        ans = 1
        for i in range(1,len(envelopes)):
            for j in range(i):
                if envelopes[i][1] > envelopes[j][1]:
                    dp[i] = max(dp[i],dp[j]+1)
                ans = max(ans,dp[i])
        # print(dp)
        # print(envelopes)
        return ans

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if len(nums)<=1:
            return nums
        p = 0
        while p<len(nums) and nums[p] != 0:
            p+=1
        if p == len(nums):
            return nums
        q = p+1
        while p<q and q<len(nums):
            if nums[q] != 0:
                nums[p],nums[q] = nums[q],nums[p]
                p+=1
            q+=1
        return nums