算法分析课程博客分享 1

665. 非递减数列(Non-decreasing Array)

给定一个长度为 n 的整数数组，你的任务是判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的：对于数组中所有的 i (1 <= i < n)，满足 array[i] <= array[i + 1]。

示例 1:
输入: [4,2,3]
输出: True
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。

示例 2:
输入: [4,2,1]
输出: False
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。

解题思路:
本题所传入的参数是一个一维数组，为了更好地看清问题的本质，我们先将题目假设为不能改变任何元素的情况下，该数组是否为非递减数列。此时，我们仅需严格按照非递减数列的定义对数组进行一次扫描即可，具体代码如下:

bool checkPossibility(vector<int>& nums) {
    int size = nums.size();
    for (int i = 1; i < size; ++i) {
        if (nums[i-1] > nums[i])
            return false;
    }
    return true;
}

而当问题变为最多允许改变一个元素，当我们检测到一组不满足非递减数列的值并对其进行修改后，我们可以获得两种结果，第一种是修改后的数据对剩余数据非递减性不产生影响，第二种则是修改后的数据对剩余数据非递减性产生了影响。接下来，我们将分情况去讨论这个问题。
我们可以以输入 [4,2,3] 为例，其中不符合定义的数据为 [4,2]。此时，我们的修改方案可以是将 4 改成 2 或者是将 2 改成 4。若我们执行第一种修改，由于 4 的前面没有其他的数据，将 4 缩小成 2 不会导致前面存在比 2 大的数据。若我们执行第二种修改，将 2 放大成 4 后，其后的 3 便会变得比 4 要小，因此，这种修改是不满足题目要求的。
在理解清楚题目要求后，我们以输入 [3,4,2,3] 为例来推出题目的解法。当我们对数组进行扫描时，第一组不符合定义的数据为 [4,2]，此时我们存在两种修改方案，显然执行缩小修改会使得新数组中的数据 [3,2] 不符合定义，因此，我们必须执行放大修改。要注意的是，在数据 [4,2] 前的所以数据都是符合非递减定义的，所以，数据 4 的上一个数必然是 4 前面所有数据的最大值，故我们只需检测 4 的上一个数是否比 2 大即可判断能否执行缩小修改。执行放大修改后，我们得到的新数组是 [3,4,4,3]，显然，数据 [4,3] 是不符合定义的，因此我们无法仅修改一个数就让输入变成非递减数列。在数次优化效率后，AC代码如下:

bool checkPossibility(vector<int>& nums) {
    int size = nums.size();
    bool flag = false;
    for (int i = 1; i < size; ++i) {
        if (nums[i-1] > nums[i]) {
            if (flag)
                return false;
            if (i > 1 && nums[i-2] > nums[i]) {
                nums[i] = nums[i-1];
            }
            flag = true;
        }
    }
    return true;
}

其中，变量 flag 用于标记此前是否已经修改过数组中的元素，判断条件 (i > 1 && nums[i-2] > nums[i]) 用于判断是否执行放大操作。实际上，由于扫描的下标是由 1 开始的，判断执行缩小操作的条件为 (i == 1 || nums[i-2] <= nums[i])，但是执行缩小操作并不需要改变原数组的数据也能得到正确的结果，因此，我们只需要在执行放大操作时放大 nums[i] 即可，这样可以减少 IO 的次数。最后，此段代码的时间复杂度为 O(n)。

880. 索引处的解码字符串(Decoded String at Index)

给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：

如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。

现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。

示例 1：
输入：S = “leet2code3”, K = 10
输出：”o”
解释：
解码后的字符串为 “leetleetcodeleetleetcodeleetleetcode”。
字符串中的第 10 个字母是 “o”。

示例 2：
输入：S = “ha22”, K = 5
输出：”h”
解释：
解码后的字符串为 “hahahaha”。第 5 个字母是 “h”。

示例 3：
输入：S = “a2345678999999999999999”, K = 1
输出：”a”
解释：
解码后的字符串为 “a” 重复 8301530446056247680 次。第 1 个字母是 “a”。

解题思路:
一开始的时候，我尝试用最暴力的方式，以叠加字符串的形式求出解码字符串，然后再获取第K个字母，结果是不出意外地超出内存限制了。后来在参考了一些资料的前提下，终于解出了题目。 <br / > 我们先考虑输入 “appleappleappleappleappleapple” ，而这个输入实际上是等价于 “apple6” 的。通过观察，我们可以发现对于 “appleappleappleappleappleapple” 来说， “appleappleappleappleappleapple”[K] == “apple”[K%6]。因此，对于形如 “apple6” 的输入，我们可以通过求解 “apple”[K%6] 来优化空间上的使用。
我们接着考虑输入 “ky62”，实际解码后的结果为 “kykykykykykykykykykykyky”。而输入 “ky62” 其实等价于 “kykykykykyky2”，而对于 “kykykykykyky2” 形式，我们可以使用上述的方法简化。到这里，我们就可以找到解决这道题目的思路了。考虑输入 “ky62”，对于给定的 K，我们有 “kykykykykykykykykykykyky”[K] == “kykykykykyky”[K%12] == “ky[K%12%2]”。该种思路可以用如下代码实现:

string decodeAtIndex(string S, int K) {
    long size = 0;
    for (int i = 0; i < S.length(); ++i) {
        if (isdigit(S[i])) {
            size *= S[i] - '0';
        } else {
            ++size;
        }
    }
    for (int i = S.length()-1; i >= 0; --i) {
        K %= size;
        if (K == 0 && isalpha(S[i]))
            return string(1, S[i]);
        if (isdigit(S[i])) {
            size /= S[i] - '0';
        } else {
            --size;
        }
    }
}

首先我们通过一次正向扫描，得出解码串的长度为 24。然后对于任意合法的 K，我们首先假设为 23。我们从后往前扫描字符串，得到的第一个数据是 ‘2’，说明上一步得到的解码串长度为 24/2 = 12，故我们执行 K%=12，得到新的 K 值 11。继续往前扫描，得到的数据是 ‘6’，则上一步得到的解码串长度为 12/6 = 2，执行 K%=2，得到新的 K 值 1。继续往前扫描，得到数据 ‘y’，则上一步得到的解码串长度为 2-1 = 1。此时 K%size == 0，即我们只要获得当前状态解码串的末尾元素即可。该算法的时间复杂度是 O(n)，空间复杂度是 O(1)。
而实际上，考虑到 S 的长度始终小于等于 100，我们可以适量增多内存的占用来减少执行数学运算的次数，具体代码如下:

string decodeAtIndex(string S, int K) {
    stack<long> s;
    s.push(0);
    for (int i = 0; i < S.length(); ++i) {
        if (isdigit(S[i])) {
            s.push(s.top()*(S[i]-'0'));
        } else {
            s.push(s.top()+1);
        }
        if (s.top() >= K)
            break;
    }
    for (int i = s.size()-2; i > -1; --i) {
        K %= s.top();
        if (K == 0 && isalpha(S[i]))
            return string(1, S[i]);
        s.pop();
    }
}

在这段代码中，在第一次扫描中，我们检测了当前解密串大小是否大于 K，减少了第一次遍历的数学运算次数。而在第二次遍历时，从第一次遍历的终止点开始逆向扫描，可以减少需要扫描元素的数量，且由于数据是从栈中取用，也省去了更新 size 的开销，算法的时间复杂度为 O(n)，空间复杂度也为 O(n)。但此段代码可以在增加少量内存(最多100个long型)的情况下，省去了较多的除法运算与乘法运算。

41. 缺失的第一个正数

给定一个未排序的整数数组，找出其中没有出现的最小的正整数。

示例 1:
输入: [1,2,0]
输出: 3

示例 2:
输入: [3,4,-1,1]
输出: 2

示例 3:
输入: [7,8,9,11,12]
输出: 1

解题思路:
一开始看到题目要求的时候，我是想不到时间复杂度为 O(n)，空间复杂度为 O(1) 的算法的。在我脑海里，首先出现的想法分别有一下两种。
1、先对数组进行排序，然后扫描一遍获取缺失的最小正数，具有线性时间复杂度与常数空间复杂度。
2、另外申请与数组等大小的空间，进行一次桶排序，然后扫描一遍获取缺失的最小正数，具有线性时间复杂度和线性空间复杂度。这种做法实际上就是以空间换取时间。
但是，根据题目的描述，我们还是可以从 O(1) 空间复杂度推出我们需要的算法是一个原地算法，从 O(n) 时间复杂度推出我们需要先执行常量次数的预处理扫描再通过一遍扫描获取答案。实际上，我们可以通过优化第二种方法来得出这道题目的正确解。由于知识水平有限，我在网上查阅资料后发现了一种叫循环不变式的概念，而这也是这道题目的关键。我们如果将整个数组看成是桶，把数组中的每一个元素都移动到与其值相等的下标的位置上，我们就只需找到第一个与桶标号不相等的元素即可，具体代码如下:

int firstMissingPositive(vector<int>& nums) {
    int size = nums.size();
    for (int i = 0; i < size; ) {
        if (nums[i] <= size && nums[i] > 0 && nums[i]-1 != i && nums[i] != nums[nums[i]-1]) {
            swap(nums[i], nums[nums[i]-1]);
        } else {
            ++i;
        }
    }
    for (int i = 0; i < size; ++i) {
        if (nums[i] != i+1)
            return i+1;
    }
    return size+1;
}

对于这一段代码，我们首先假设对于数组的所有位置，若元素的值属于桶标号的范围，则其下标的值等于元素的值减 1。故我们在第一遍扫描过程中，若元素不违反该规则，则扫描下一元素，否则将其移动到与其元素值相等的下标的位置上。值得注意的是，移动前我们需要保证 nums[nums[i]-1] != i+1，否则在交换后，程序将陷入死锁，此处可考虑输入 [1,2,2,2]。而这一逻辑又可以等价为 nums[i] != nums[nums[i]-1]，以省去计算 i+1 的开销。最终，代码的时间复杂度为 O(n)，空间复杂度为 O(1)。