yp 11-20

P11 coding题是字符串乘法，全是bug，懒得说了。。。

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        num1, num2 = num1[::-1], num2[::-1]
        res = [0]*(len(num1)+len(num2))

        for i in range(len(num1)):
            for j in range(len(num2)):
                tmp = int(num1[i])*int(num2[j])
                cur = res[i+j]+tmp
                res[i+j] = cur%10
                res[i+j+1] += cur//10
                print res



        while len(res)>1 and res[-1]==0:
            res.pop()

        return ''.join(map(str, res[::-1]))


num1 = '999'
num2 = '9999'
so = Solution()
a = so.multiply(num1, num2)
print(a)

P12 maximum subarray

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        pre = 0
        res = float('-inf')
        for num in nums:
            pre = max(num, num+pre)
            res = max(res,pre)

        return res


nums = [-2,1,-3,4,-1,2,1,-5,4]
so = Solution()
a = so.maxSubArray(nums)
print a

P13 Coin Change

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        self.res = float('inf')
        coins = sorted(coins, reverse=True)
        self.dfs(coins, 0, amount)
        return self.res if self.res!=float('inf') else -1

    def dfs(self, coins, cnt, amount):
        if amount<0:
            return 
        if amount==0:
            self.res = min(self.res, cnt)
        for c in coins:
            if c<=amount<c*(self.res-cnt):
                self.dfs(coins, cnt+1, amount-c)

scores = [1,2,5]
target = 1000
so = Solution()
a = so.coinChange(scores, target)
print a

DP解法

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [0]*(amount+1)
        dp[0] = 0

        for i in range(amount+1):
            tmp = []
            for c in coins:
                if c<=i and (dp[i-c]!=0 or (i-c)==0):
                    tmp.append(dp[i-c]+1)
            if tmp:
                dp[i] = min(tmp)

        return dp[-1] if dp[-1] else -1

scores = [1,2,5]
target = 11
so = Solution()
a = so.coinChange(scores, target)
print a