算法模拟实战：替换问号、提莫攻击与 Z 字形变换

39. 提莫攻击

题目描述

题目示例

核心思路

关键在于处理中毒时间的重叠问题。我们按顺序遍历攻击时间点，计算当前攻击与下一次攻击的时间差：

• 如果时间差大于等于持续时长 duration，说明前一次中毒效果完全释放，累加 duration。
• 如果时间差小于 duration，说明前一次中毒被后一次覆盖了一部分，实际有效时间仅为两者的差值。

最后别忘了加上最后一次攻击带来的完整持续时间。

参考实现

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

题目描述

题目示例

核心思路

这道题的核心在于发现索引变化的周期性。当行数为 numRows 时，整个 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. 处理第一行：每隔 d 个字符取一个
        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. 处理最后一行：每隔 d 个字符取一个
        for(int i = numRows - 1; i < s.size(); i += d) {
            ret.push_back(s[i]);
        }

        return ret;
    }
};

解题思路图解