leetcode 72+213 题解

发表于

1. 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:

  1. Insert a character
  2. Delete a character
  3. Replace a character

Example 1:

1
2
3
4
5
6
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

1
2
3
4
5
6
7
8
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')

解法

这题首先注意到，在做字符匹配时，我们一共有三种操作：插入、编辑和删除，因此可能存在非常多的对齐方式，这里使用动态规划来解决这一问题。

对于动态规划来说，最重要的是定义子问题，之后就按照子问题规模递增的顺序逐个求解。那么对于这道题来说如何定义子问题呢？大目标是寻找字符串x[1,...m]与y[1,...,n]间的编辑距离，将这个问题记为E(m, n)，我们可以尝试找到三种操作下的最小的E(i, j)，其中i，j比m，n规模更小，这样逐步推导下去就可以到达底层了。也就是说对每一个E(i, j)，将它分解为：E(i, j) = min{1 + E(i - 1, j), 1 + E(i, j - 1), diff(i, j) + E(i - 1, j - 1)}，这里diff(i, j)在i，j相同时为0，否则为1。

实现在这里没有选择递归，而是采用了填表的做法，实际效果是一样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minDistance(string word1, string word2) {
    int m = word1.size() + 1, n = word2.size() + 1;
    vector<vector<int>> E(m, vector<int>(n, 0));
    for(int i = 0; i < m; ++i){
        E[i][0] = i;        
    }
    for(int j = 1; j < n; ++j){
        E[0][j] = j;        
    }
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            int diff = word1[i - 1] == word2[j - 1] ? 0 : 1;
            E[i][j] = min(min(1 + E[i - 1][j], 1 + E[i][j - 1]), diff + E[i - 1][j - 1]);
        }
    }
    return E[m - 1][n - 1];
}

##2. House Robber Ⅱ

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Example 1:

1
2
3
4
Input: [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2),
             because they are adjacent houses.

Example 2:

1
2
3
4
Input: [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
             Total amount you can rob = 1 + 3 = 4.

解法

题目意思即在数组中取数，相邻的数不能一起取，同时头和尾不能一起取。可以想到，当我们从前往后取时，取了一个数后下一个数的位置一定是现在的位置加2或加3，先不考虑头尾相邻，那么就可以得到我们的算法了：对数组每个位置i，填充dp[i] += (dp[i - 2] > dp[i - 3] ? dp[i - 2] : dp[i - 3]);，前三位则独立讨论，这样在给数组赋值的过程中就是在进行子问题的计算。最后，因为一定会到达倒数第一个位置或第二个位置，那么就返回这两个中更大的那个。

对于头和尾不能同时取的问题，只需要分成不包含头和不包含尾的两部分分开求解，最后返回更大的就行了。

具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int rob(vector<int>& nums) {
    if(nums.empty()) return 0;
    int n = nums.size(), i = 0;
    if(nums.size() == 1){
        return nums[0];
    }
    vector<int> dp1(n - 1, 0);
    vector<int> dp2(n - 1, 0);
    for(int j = 0; j < nums.size() - 1; ++j){
        dp1[j] = nums[j];
        dp2[j] = nums[j + 1];
    }
    return max(find(dp1), find(dp2));
}
int find(vector<int>& dp){
    int i = 0;
    if(dp.size() == 1){
        return dp[0];
    }
    if(dp.size() == 2){
        return max(dp[0], dp[1]);
    }
    if(dp.size() == 3){
        return max(dp[1], dp[0] + dp[2]);
    }
    dp[2] += dp[0];
    for(i = 3; i < dp.size(); ++i){
        dp[i] += (dp[i - 2] > dp[i - 3] ? dp[i - 2] : dp[i - 3]);
    }
    return dp[i - 1] > dp[i - 2] ? dp[i - 1] : dp[i - 2];
}