Lettcode 动态规划 medium

• Unique Paths II (Lettcode)
  一个机器人在 M * N 的二维数组中，机器人可以向下或向右移动，现在在其中添加了障碍，用 1 表示，机器人要到达网格的右下角，请问有多少条路径？
  dp 动态规划，如果是 1 ，直接本条路径为 0
  否则加之前一个格子的路径

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]

• Unique Paths (Lettcode)
  机器人从 M * N 的网格左上角开始，要到右下角，问总共有多少条路径？
  到达某一点的路径数等于到达它上一点的路径数与它左边的路径数之和。即起点到达 (i, j) 点的路径 = 起点到 (i - 1, j) + 起点到 (i, j-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]

• Minimum Path Sum
  一个 M * N 的网格，里面有非负整数，现要求找到一条从左到右的路径，使其经过的格子数值之和最小，每一步只能向右或向下。

# 又是动态规划
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

• Edit Distance
  两个字符串，问需要经过多少次操作才能使 word1 变为 word2，操作有插入一个字符串，删除一个字符串，替换一个字符串。

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]

• House Robber II
  前一个问题的升级版，可以分解为两个子问题，从第一个到倒数第二个，从第二个到最后一个，然后比较这两个的最大值

# 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]))

• Maximum Product Subarray
  给定一个数组，找到相邻子数组乘积最大

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) 空间

• Ugly Number II
  找出第 n 个丑数。丑数是那些只包含因子 2， 3， 5 的数字

# 蛮力法：
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_

• Count Numbers with Unique Digits
  计算各个位数不同的数字个数
  概率论知识，当第一位选择某个数字时，第二位就不能选择这个数字了。第一位可选择的数字有 9 个，不包括 0 ，第二位也能选 9 个，包括 0 。之后递减。

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

• ZigZag Conversion
  以 Z 字型排列一个字符串，然后输出

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)