美文网首页
Lettcode 动态规划 medium

Lettcode 动态规划 medium

作者: vckah | 来源:发表于2018-05-19 23:46 被阅读0次
    • 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)
    

    相关文章

      网友评论

          本文标题:Lettcode 动态规划 medium

          本文链接:https://www.haomeiwen.com/subject/olpadftx.html