LeetCode Top 100（二）

作者: oneoverzero | 来源:发表于2020-03-12 18:11 被阅读0次

64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:
Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

思路分析：

详细的分析过程参见： https://leetcode.com/problems/minimum-path-sum/discuss/23457/C%2B%2B-DP

方法是动态规划，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j] ，但是这里要特别注意的是对边界条件的处理（即对 dp[0][0] 的处理、对 dp[0][j] 的处理以及对 dp[i][0] 的处理）。

代码如下：

class Solution(object):
    def minPathSum(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        if not grid:
            return None
        dp = [grid[0][0]] * len(grid)
        for i in range(1, len(grid)):
            dp[i] = dp[i-1] + grid[i][0]
        for j in range(1, len(grid[0])):
            dp[0] += grid[0][j]
            for i in range(1, len(grid)):
                dp[i] = min(dp[i-1], dp[i]) + grid[i][j]
        
        return dp[-1]

代码说明如下：

第 9 行体现的是对 dp[0][0] 这个边界条件的处理；
第 10 ~ 11 行体现的是对 dp 矩阵第 1 列的处理，这里是固定 j=0 ，让 i 从 1 增加到 len(grid) ；
然后第 12 ~ 15 行是从第 1 列开始逐列地向右推进，直至到达 grid 的最后一列。在这期间，第 13 行首先进行 dp[0] += grid[0][j] 是要先计算出 dp 最上面的一个元素，这实际上是对 dp[0][j] 这个边界条件的处理。第 15 行便是动态规划的核心。
时间复杂度： $O(m \times n)$ （ $m$ 、 $n$ 分别是 grid 的行数和列数），空间复杂度： $O(1)$ 。

70. Climbing Stairs

题目描述：

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:
Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

思路分析：

参见： https://leetcode.com/problems/climbing-stairs/discuss/25299/Basically-it's-a-fibonacci.

本题的实质是一个斐波那契数列问题，解决方法是动态规划，核心是 dp[n] = dp[n-1] + dp[n-2] 。参照《剑指offer》上的斐波那契数列问题，可以写出如下代码：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        pre, cur = 1, 2
        for i in range(n-1):
            pre, cur = cur, pre + cur
        
        return pre

72. Edit Distance

题目描述：

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Example 1:
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:
Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

思路分析：

参见： https://leetcode.com/problems/edit-distance/discuss/25846/C%2B%2B-O(n)-space-DP

基于上述链接中作者的分析，个人觉得在这个问题中，各状态之间的转移轨迹和机器人在二维方格中的运动过程有点类似（只不过这一次除了可以向右走和向下走之外，还可以沿斜向右下 45 ° 角的方向走）。状态转移方程如下：
$\text{dp[i][j]} = \left\{ \begin{aligned} & \text{dp[i-1][j-1]}, & \text{if word1[i-1] = word2[j-1]} \\ & \min \left\{ \text{dp[i-1][j-1], dp[i-1][j], dp[i][j-1]} \right\} + 1, & \text{if word1[i-1]}\ \ne \text{word2[j-1]} \end{aligned} \right. \tag 1$
如果这个问题换一个角度来思考：假设初始时给定的两个单词分别为 word1 和 word2 ，由于总共允许的操作方法只有三种：插入、删除、替换，将它们分别记为 $O_i$ 、 $O_d$ 、 $O_r$ （其中 $O_i = O_d = O_r = 1$ ），则从 word1 到 word2 必是由以上三种操作经过若干种排列组合而得到的。记总的操作数为 $S$ ，则有
$S = k \cdot O_i + m \cdot O_d + n \cdot O_r \tag 2$
其中， $k \in \mathbb{N}$ ， $m \in \mathbb{N}$ ， $n \in \mathbb{N}$ 。

现在我们要求的是 $\underset{k, m, n}{\arg \min S}$ ，如果一下子要求出 $k,m,n$ 的值肯定不好求。那怎么办呢？我们可以将这个大问题分解一下，假设如下是针对某一个具体问题的 dp 矩阵：

[[ 0  1  2  3  4  5  6  7  8  9]
 [ 1  1  2  3  4  5  6  7  8  9]
 [ 2  1  2  2  3  4  5  6  7  8]
 [ 3  2  1  2  3  4  5  6  7  8]
 [ 4  3  2  1  2  3  4  5  6  7]
 [ 5  4  3  2  1  2  3  4  5  6]
 [ 6  5  4  3  2  1  2  3  4  5]
 [ 7  6  5  4  3  2  1  2  3  4]
 [ 8  7  6  5  4  3  2  1  2  3]
 [ 9  8  7  6  5  4  3  2  1  2]
 [10  9  8  7  6  5  4  3  2  1]]

这个矩阵向下是 i 轴，向右是 j 轴。考察矩阵中的任意一个元素 dp[i][j] ，它是怎么得来的呢？首先一种最省操作数的方式是什么也不做，即 dp[i][j] = dp[i-1][j-1] ；另外一种是必须要做一步，这个时候 dp[i][j] 可以由它正上方、正左方或左上角的元素加 1 得到，具体是哪个元素加 1 要看哪个元素的值最小。这样，我们从两个单词都为空的状态开始，逐个地添加字母到 word1 和 word2 中，每添加一个字母，我们都计算一次最小操作数。当两个单词都添加完所有的字母后，一定能在上述的 dp 矩阵中找到一条路径，使得不仅最终总的操作数是最少的，甚至每新增一个字母时，这条路径的操作数始终都是最少的（如上述矩阵中恒为 1 的那条主对角线路径）。

上述的思路本质上还是穷举，只不过每添加一个字母都会进行一次动态规划，而且会将历史最优路径记录下来，避免重复地对已经规划过的路径重新进行规划，因此时间复杂度必为 $O(m \times n)$ （ $m,n$ 分别是两单词的长度）。可以优化的地方是空间上的消耗，只需要上述矩阵中的一列就可以了，没必要保存整个 dp 矩阵。

空间优化前的代码：

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not word1 or not word2: # 这里是为了避免后面出现索引越界的情况
            return len(word1) or len(word2)
        l1, l2 = len(word1), len(word2)
        dp = [[0] * (l2+1) for _ in range(l1+1)] # 注意dp矩阵是多一行和一列
        for i in range(1, l1+1): # i要往后多遍历一位，下同
            dp[i][0] = i
        for j in range(1, l2+1): # j也要往后多遍历一位，下同
            dp[0][j] = j
        for i in range(1, l1+1):
            for j in range(1, l2+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
        
        return dp[l1][l2]

空间优化后的代码：

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not word1 or not word2:
            return len(word1) or len(word2)
        l1, l2 = len(word1), len(word2)
        dp = [0] * (l2+1)
        for j in range(1, l2+1): # 初始化第一行
            dp[j] = j
        for i in range(1, l1+1): # 索引必须要到l1+1
            upleft = dp[0] # 由于要用到左上角的值，所以要单独记下来
            dp[0] = i # 初始化第一列
            for j in range(1, l2+1): # 索引必须要到l2+1
                upleft_dynamic = dp[j] # 左上角的值必须要动态更新
                if word1[i-1] == word2[j-1]: # 这里是word1[i-1]和word2[j-1]比，而不是word1[i]和word2[j]比
                    dp[j] = upleft
                else:
                    dp[j] = min(upleft, dp[j], dp[j-1]) + 1
                upleft = upleft_dynamic
        
        return dp[l2] # 或者 return dp[-1]

75. Sort Colors

题目描述：

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Follow up:

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with a one-pass algorithm using only constant space?

思路分析： https://leetcode.com/problems/sort-colors/discuss/26472/Share-my-at-most-two-pass-constant-space-10-line-solution

代码：

class Solution(object):
    def sortColors(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        left, right = 0, len(nums)-1
        for i in range(len(nums)):
            while nums[i] == 2 and i < right:
                nums[i], nums[right] = nums[right], nums[i]
                right -= 1
            while nums[i] == 0 and i > left:
                nums[i], nums[left] = nums[left], nums[i]
                left += 1
            if i == right:
                break
        
        return nums

说明：上述代码中，left 是 0 的右边界，right 是 2 的左边界，如下：

    left    right
      |       |
[0  0 | 1   1 | 2   2]
      |       |

LeetCode Top 100（二）

64. Minimum Path Sum

70. Climbing Stairs

72. Edit Distance

75. Sort Colors

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读