算法题精讲：模拟法在字符串与时间计算中的应用

1. 如果时间差大于等于中毒持续时间 duration，说明上次中毒效果已完全结束，累加完整的 duration。
2. 如果时间差小于 duration，说明上次中毒尚未结束，本次攻击会延长中毒时间，实际贡献时间为时间差值。

综合来看，每次攻击对总时间的贡献就是 min(时间差，duration)。最后一次攻击因为没有下一次攻击来截断它，所以直接加上完整的 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 字形变换

题目描述

解题思路

Z 字形变换的本质是按特定路径将字符写入二维矩阵，再按行读取。观察规律可以发现，字符的行索引变化呈现周期性：从上到下递增，到达底部后折返向上，直到顶部再次向下。

周期长度为 2 * numRows - 2。我们可以利用这个周期直接计算每一行应该包含哪些字符的下标，从而避免构建二维数组，直接生成结果字符串。

具体策略分为三部分处理：

1. 第一行：下标为 0, period, 2*period...
2. 中间行：每行有两个下标序列交替出现，分别是 k + n*period 和 (period - k) + n*period
3. 最后一行：下标为 numRows - 1, period + numRows - 1...

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

总结

这三道题虽然场景不同，但都体现了模拟思想在算法中的核心地位。无论是字符串的局部替换、时间区间的重叠计算，还是复杂路径的索引映射，关键在于准确理解题目规则并将其转化为可执行的步骤。在实际编码中，注意边界条件的判断（如空串、单行、首尾元素）往往能避免大量调试时间。