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

公式上可以简化为每次累加 min(duration, timeSeries[i+1] - timeSeries[i])，最后别忘了加上最后一次攻击的完整持续时间。

参考实现

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 字形变换

题目描述

将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列，然后按行读取生成新字符串。

题目示例

输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"

解题思路

Z 字形变换的本质是寻找下标变化的规律。观察可知，字符的行索引变化呈现周期性，周期长度为 2 * numRows - 2。

• 首行和末行：每行只有一个字符参与，下标间隔固定为周期长度。
• 中间行：每个周期内包含两个字符，分别位于当前行的上下两侧。可以通过数学推导得出这两个位置的关系。

我们可以分三部分处理：第一行、中间行（循环枚举）、最后一行。对于中间行，注意判断边界条件，避免数组越界。

参考实现

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;
    }
};

以上三道题均侧重于对基础逻辑的模拟与细节把控。替换问号考察边界判断，提莫攻击考察区间重叠处理，Z 字形变换则是对数学规律的直观应用。掌握这些模式有助于提升解决类似模拟题的能力。