算法分析课程博客分享 11

402. 移掉K位数字(Remove K Digits)

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

示例 1 :
输入: num = “1432219”, k = 3
输出: “1219”
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :
输入: num = “10200”, k = 1
输出: “200”
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :
输入: num = “10”, k = 2
输出: “0”
解释: 从原数字移除所有的数字，剩余为空就是0。

解题思路:
要移除非负整数 num 中的 k 位数字，使其剩下的数字最小，我们显然需要从 num 的最高位开始移除，移除 k 个最大的数字。因此，我们使用压栈的方式解决这个问题，从字符串的开头开始扫描，每一轮循环中，考虑当前数字 n，我们移除掉栈顶比 n 要大的元素，然后将 n 压入栈中。通过这种方式，我们可以维持栈中元素的顺序，使栈里面的元素拥有升序属性。由于我们只能移除 k 位数字，我们在执行上述操作的同时，需要检测已移除数字的个数，以确保移除的数字个数不会超过 k，若移除数字个数已达到 k 个，则将 num 中的剩余数字全部压入栈中。因为输出不能有任何前导 0，我们接下来需要移除掉所有在栈底的 0，同时保证移除后栈里面的元素个数不为 0。且外，我们在压栈过程中移除掉的数字可能不足 k 位，所以我们需要在栈顶额外移除部分元素，让栈中元素的个数等于 num.length()-k。至此，我们想要获得的最小数字即从栈底元素开始到栈顶的数字序列。为了能同时取用栈顶和栈底的元素，我们使用双端队列 deque 来取代栈，而 deque 支持迭代器的特性也方便我们将栈里面的元素转换为字符串。具体代码如下：

string removeKdigits(string num, int k) {
    if (k >= num.length())
        return "0";

    deque<char> dq;
    for (char n : num) {
        while (k != 0 && !dq.empty() && dq.back() > n) {
            dq.pop_back();
            --k;
        }
        dq.push_back(n);
    }

    while (dq.front() == '0' && dq.size() > 1) {
        dq.pop_front();
    }

    return string(dq.begin(), dq.begin()+dq.size()-k);
}

605. 种花问题(Can Place Flowers)

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

示例 1:
输入: flowerbed = [1,0,0,0,1], n = 1
输出: True

示例 2:
输入: flowerbed = [1,0,0,0,1], n = 2
输出: False

注意:

数组内已种好的花不会违反种植规则。
输入的数组长度范围为 [1, 20000]。
n 是非负整数，且不会超过输入数组的大小。

解题思路:
在这道题目中，我们可以贪心地去种植花，假设我们最多可以种 k 朵花，则我们要返回的是 (n <= k) 的真假。一种比较好想到的思路为：通过扫描数组，获得所有已种植花的位置，然后往这些花中间插入新的花。首先，我们定义 flower 数组来储存原始花坛中花的位置的下标。我们先考虑两朵花中间可以插入的花的数量，假设第一朵花下标为 i，第二朵下标为 j，则可插入的花的数目为 (j-i)/2 - 1。然后，我们还需要考虑第一朵花左边的空位与最后一朵花右边的空位。这里需要先排除掉花坛为空的情况，花坛为空的时候，可种植的花朵的数目为 (flowerbed.size()+1)/2。接下来，我们假设第一朵花的下标为 i，最后一朵花的下标为 j，那么花坛左边空位能种植的花的数目为 (i-0)/2，花坛右边空位能种植的花的数目为 (flowerbed.size()-1-j)/2。具体代码如下：

bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    vector<int> flower;
    for (int i = 0; i < flowerbed.size(); ++i) {
        if (flowerbed[i] == 1) {
            flower.push_back(i);
        }
    }

    for (int i = 1; i < flower.size(); ++i) {
        n -= (flower[i]-flower[i-1])/2 - 1;
    }
    if (flower.empty()) {
        n -= (flowerbed.size()+1) / 2;
    } else {
        n -= flower[0] / 2;
        n -= (flowerbed.size()-flower.back()-1) / 2;
    }

    return (n <= 0);
}

我们也可以在上述基础上做出改进，考虑到算法只依赖连续两朵花的下标，我们可以用 O(1) 空间复杂度解决这个问题。首先，我们注意到花坛左边空位能种植的花的数目为 (i-0)/2，我们可以将其转化为 (i-(-2))/2 -1，令 -2 作为 flower[0] 的前一项，则我们可以把计算花坛左边空位能种植的花的数目的计算合并到计算两朵花中间可以插入的花的数量的计算中。然后，我们用 prev 和 cur 分别表示上一朵花的下标和当前花的下标，在扫描 flowerbed 的时候，当检测到新的花朵，则更新 prev 与 cur 的值，并且计算出两朵花之间可插入的花的数目。在扫描结束后，我们还需额外计算花坛右边空位可插入的花的数量，其值为 (flowerbed.size()-cur-1)/2；而花坛为空时，可插入的花的数目为 (flowerbed.size()+1)/2。我们可以将 (flowerbed.size()+1)/2 转化为 (flowerbed.size()-(-2)-1)/2，又花坛为空时 cur 的值等于 -2，我们可以将上述两种情况合并在一次。最终，算法的时间复杂度为 O(n)，空间复杂度为 O(1)。具体代码如下：

bool canPlaceFlowers(vector<int>& flowerbed, int n) {
    int prev = -2, cur = -2;
    for (int i = 0; i < flowerbed.size(); ++i) {
        if (flowerbed[i] == 1) {
            prev = cur;
            cur = i;
            n -= (cur-prev)/2 - 1;
        }
    }
    n -= (flowerbed.size()-cur-1) / 2;

    return (n <= 0);
}

115. 不同的子序列(Distinct Subsequences)

给定一个字符串 S 和一个字符串 T，计算在 S 的子序列中 T 出现的个数。

一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，”ACE” 是 “ABCDE” 的一个子序列，而 “AEC” 不是）

示例 1:
输入: S = “rabbbit”, T = “rabbit”
输出: 3
解释:
如下图所示, 有 3 种可以从 S 中得到 “rabbit” 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

示例 2:
输入: S = “babgbag”, T = “bag”
输出: 5
解释:
如下图所示, 有 5 种可以从 S 中得到 “bag” 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^  ^
babgbag
^^       ^
babgbag
^       ^^
babgbag
    ^   ^^
babgbag
       ^^^

解题思路:
为了能更好地理解这个问题，我们可以令 dp[i][j] 为在 s.substr(0, i) 中 t.substr(0, j) 出现的个数，且假设我们已经知道 dp[i][j] 的值。在考虑 dp[i+1][j] 时，假如 s[i+1] == t[j]，那么 dp[i+1][j] = dp[i-1][j] + dp[i][j-1]。其含义为：当我们识别到 s 的第 i+1 位与 t 的第 j 位相等时，s.substr(0, i+1) 中 t.substr(0, j) 出现的个数就等于 s.substr(0, i-1) 中 t.substr(0, j) 出现的个数加上s.substr(0, i) 中 t.substr(0, j-1) 出现的个数。其中，s.substr(0, i) 中 t.substr(0, j-1) 出现的个数代表扫描到 s 的第 i+1 位后新增的匹配方案。根据此状态转移方程，我们可以很容易地用二维数组解决这个问题。实际上，由于我们不需要记录每一轮的结果，我们可以改用一个一维数组解决问题。但要注意的是，我们的状态是依赖上一轮的结果的，所以在内循环中需要反向扫描。且外，我们也可以在 dp 数组的开头额外插入一个 1，以免去我们在匹配 t 开头元素时所需的特殊操作，代表我们在 s 中匹配到 t 的开头元素时，s.substr(0, i) 中 t.substr(0, 0) 出现的个数将始终增加 1。具体代码如下：

int numDistinct(string s, string t) {
    vector<int> dp(t.length()+1, 0);
    dp[0] = 1;
    for (int i = 0; i < s.length(); ++i) {
        for (int j = t.length(); j > 0 ; --j) {
            if (s[i] == t[j-1]) {
                dp[j] += dp[j-1];
            }
        }
    }

    return dp[t.length()];
}