算法题讲解：替换所有问号、提莫攻击与 Z 字形变换

39. 提莫攻击

题目链接

495. 提莫攻击 - 力扣（LeetCode）

题目描述

题目示例

解法（模拟 + 分情况讨论）

算法思路

模拟 + 分情况讨论。 计算相邻两个时间点的差值：

• 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒。
• 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值。

还可以这样想，我们每次加上 min(duration, 差值) 就行。

C++ 算法代码

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int sum = 0;
        for(int i = 0; i < timeSeries.size() - 1; i++) {
            sum += min(timeSeries[i + 1] - timeSeries[i], duration);
        }
        sum += duration;
        return sum;
    }
};

算法总结及流程解析

40. Z 字形变换

题目链接

6. Z 字形变换 - 力扣（LeetCode）

题目描述

题目示例

解法（模拟 + 找规律）

算法思路

找规律，用 row 代替行数，row = 4 时画出的 N 字形如下： 0 2row - 2 4row - 4 1 2row - 3 2row - 1 4row - 5 4row - 3 2 2row-4 2row 4row - 6 4row - 2 3 2row + 1 4row - 1

不难发现，数据是以 2row - 2 为一个周期进行规律变换的。将所有数替换成用周期来表示的变量： 第一行的数是：0, 2row - 2, 4row - 4； 第二行的数是：1, (2row - 2) - 1, (2row - 2) + 1, (4row - 4) - 1, (4row - 4) + 1； 第三行的数是：2, (2row - 2) - 2, (2row - 2) + 2, (4row - 4) - 2, (4row - 4) + 2； 第四行的数是：3, (2row - 2) + 3, (4row - 4) + 3。

可以观察到，第一行、第四行为差为 2row - 2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为 (2n - 1, 2n) 的数围绕（2row - 2）的倍数左右取值。 以此规律，我们可以写出迭代算法。

C++ 算法代码

class Solution {
public:
    string convert(string s, int numRows) {
        string ret;
        int d = 2 * numRows - 2;
        if(d == 0) {
            return s;
        }
        // 1、处理第一行
        for(int i = 0; i < s.size(); i += d) {
            ret.push_back(s[i]);
        }
        // 2、处理中间行
        for(int k = 1; k < numRows - 1; k++) {
            for(int i = k, j = d - k; i < s.size() || j < s.size(); i += d, j += d) {
                if(i < s.size()) {
                    ret.push_back(s[i]);
                }
                if(j < s.size()) {
                    ret.push_back(s[j]);
                }
            }
        }
        // 3、处理最后一行
        for(int i = numRows - 1; i < s.size(); i += d) {
            ret.push_back(s[i]);
        }
        return ret;
    }
};

算法总结及流程解析