Lettcode 动态规划 medium

2018-05-19  本文已影响0人  vckah
def uniquePathsWithObstacles(obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        width = len(obstacleGrid[0])
        dp = [0 for m in range(width)]
        dp[0] = 1
        for row in obstacleGrid:
            for i in range(width):
                if row[i] == 1:
                    dp[i] = 0
                elif i > 0:
                    dp[i] += dp[i-1]
        return dp[-1]
def uniquePaths(m, n):
    aux = [[1 for _ in range(n)] for _ in range(m)]
    for i in range(1, m):
        for j in range(1, n):
            aux[i][j] = aux[i][j-1] + aux[i-1][j]
    return aux[-1][-1]
# 构造一个一维数组来求解
def uniquePaths1(m, n):
    row_state = [1] * n
    for _ in range(1, m):
        col_state = 1
        for j in range(1, n):
            row_state[j] += col_state
            col_state = row_state[j]
            
    return row_state[-1]
# 又是动态规划
def min_path_num(grid):
    m = len(grid)
    n = len(grid[0])
    # 计算第一行的和
    for i in range(1, n):
        grid[0][i] += grid[0][i-1]
    # 计算第一列的和
    for i in range(1, m):
        grid[i][0] += grid[i-1][0]
    # 计算到达每一格的最小值
    for i in range(1, m):
        for j in range(1, n):
            grid[i][j] += min(grid[i-1][j], grid[i][j-1])
    return grid[-1][-1]
# 只用一维数组
def minPahtSum(grid):
    """
    :type grid: List[List[int]]
    :rtype: int
    """
    if not grid:
        return 0
    m, n = len(grid), len(grid[0])
    dp = [0 for _ in range(n)]
    dp[0] = grid[0][0]
    
    for j in range(1, n):
        dp[j] = dp[j-1] + grid[0][j]

    for i in range(1,m):
        dp[0]+=grid[i][0]
        for j in range(1,n):
            # 判断当前格子右上角的值和左边格子的值,选择小的一方加到当前格子
            dp[j]=dp[j]+grid[i][j] if dp[j]<dp[j-1] else dp[j-1]+grid[i][j]
    return dp[-1] if dp else 0
def minDistance1(word1, word2):
    l1, l2 = len(word1) + 1, len(word2) + 1
    dp = [[0 for _ in xrange(l2)] for _ in xrange(l1)]
    for i in range(l1):
        dp[i][0] = i
    for j in range(l2):
        dp[0][j] = j
    for i in range(1, l1):
        for j in range(1, l2):
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+(word1[i-1]!=word2[j-1]))
    return dp[-1][-1]
# O(n) space with rolling array            
def minDistance(self, word1, word2):
    l1, l2 = len(word1)+1, len(word2)+1
    pre = [0 for _ in xrange(l2)]
    for j in xrange(l2):
        pre[j] = j
    for i in xrange(1, l1):
        cur = [i]*l2
        for j in xrange(1, l2):
            cur[j] = min(cur[j-1]+1, pre[j]+1, pre[j-1]+(word1[i-1]!=word2[j-1]))
        pre = cur[:]
    return pre[-1]
# rob1 是 easy 种的 house robber
def rob2(nums):
    # 升级版,首尾相连
    if not nums:
        return 0
    if len(nums) < 2:
        return nums[0]
    return max(rob1(nums[1:]), rob1(nums[0:-1]))
Input: [2,3,-2,4]
Output: 6
Input: [-2,0,-1]
Output: 0

思路:需要维护当前的最大值和当前最小值,在 dp_min[i-1] * nums[i], dp_max[i-1] * nums[i-1], nums[i] 这三者中取到

def maxProduct(nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        dp_min = [0 for _ in range(length)]
        dp_max = [0 for _ in range(length)]
        max_su = nums[0]
        dp_max[0] = dp_min[0] = nums[0]
        for i in range(1, length):
            dp_min[i] = min(dp_max[i-1]* nums[i], dp_min[i-1]*nums[i], nums[i])
            dp_max[i] = max(dp_max[i-1]* nums[i], dp_min[i-1]*nums[i], nums[i])
            max_su = max(dp_max[i], max_su)
        return max_su
# 使用 O(n) 空间
# 蛮力法:
def nthUglyNumber(n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        uglyFound = 0
        number = 0
        while uglyFound < n:
            number += 1
            if isUgly(number):
                uglyFound += 1
        return number
    
    def isUgly( number):
        if number <= 0:
            return False
        for i in [2, 3, 5]:
            while number % i == 0:
                number = number/i
        if number==1:
            return True
        else:
            return False

但是这种方法很耗时,于是可以换个思路:
丑数一定是按顺序存放的,每个丑数都是前面的丑数乘以2、3 或 5 得到的。

def nthUglyNumber(n):
    if n <= 0:
        return 0
    if n == 1:
        return 1
    numbers = [1]
    i2 = i3 = i5 = 0
    for _ in range(n-1):
        n2 = numbers[i2] * 2
        n3 = numbers[i3] * 3
        n5 = numbers[i5] * 5
        min_ = min(n2, n3, n5)
        numbers.append(min_)
        if n2 == min_:
            i2 += 1
        if n3 == min_:
            i3 += 1
        if n5 == min_:
            i5 += 1
    return min_
def countNubersWithUniqueDigits(n):
    """
    :type n: int
    :rtype : int
    """
    choices = [9, 9, 8, 7, 6, 5, 4, 3, 2, 1]
    ans, product = 1, 1

    for i in range(n if n <= 10 else 10):
        product *= choices[i]
        ans += product
    return ans
def convert(s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if numRows == 1 or numRows >= len(s):
            return s

        L = [''] * numRows
        index, step = 0, 1

        for x in s:
            L[index] += x
            if index == 0:
                step = 1
            elif index == numRows -1:
                step = -1
            index += step

        return ''.join(L)
上一篇 下一篇

猜你喜欢

热点阅读