目录
1. 提莫攻击
1.1 题目解析
1.2 解法
1.3 代码实现
2. Z字形变换
2.1 题目解析
2.2 解法
2.3 代码实现
1. 提莫攻击
495. 提莫攻击 - 力扣（LeetCode）
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。
正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。
给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。
返回艾希处于中毒状态的 总 秒数。
示例 1：
输入：timeSeries = [1,4], duration = 2 输出：4 解释：提莫攻击对艾希的影响如下： - 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。 - 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。 艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。
示例 2：
输入：timeSeries = [1,2], duration = 2 输出：3 解释：提莫攻击对艾希的影响如下： - 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。 - 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。 艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。
提示：
1 <= timeSeries.length <= 1040 <= timeSeries[i], duration <= 107timeSeries按 非递减 顺序排列
1.1 题目解析
这是一个典型的“区间累加问题”。提莫的攻击在时间线上形成若干连续或可能重叠的中毒区间，我们要统计这些区间覆盖的总长度。抽象后就是：给定若干非递减区间的起点和固定长度，求这些区间并集的总长度。
常规解法：
-
直观想法是把每次攻击产生的区间 [timeSeries[i], timeSeries[i]+duration) 都存下来，然后合并重叠区间，再求总长度。
-
时间复杂度最坏 O(n²)（如果每次都去遍历合并区间），空间复杂度 O(n) 或更多。
问题分析：
-
因为题目保证 timeSeries 已经非递减，重叠区间只会出现在相邻攻击之间。
-
所以不不必存所有区间，只需要看相邻攻击的间隔 diff = timeSeries[i+1] - timeSeries[i]：
-
diff >= duration → 上一次中毒和下一次攻击不重叠，总长度加 duration
-
diff < duration → 重叠，总长度只加 diff
-
-
这就把问题从“全局区间合并”简化为线性扫描相邻元素，O(n) 时间即可解决。
思路转折：
-
线性扫描每个攻击时间点，并根据与下一次攻击间隔计算贡献长度 → 高效且直观
-
关键在于理解“重叠部分只计算一次”，所以用 min(diff, duration) 就可以准确累加。
1.2 解法
算法实现
-
遍历每次攻击，统计它对中毒总秒数的贡献：
贡献=min(下一次攻击间隔,duration)
-
最后一发攻击必然完整贡献 duration。
i）初始化总中毒时间 total = 0
ii）遍历 timeSeries 的每个元素：
-
对于第 i 次攻击，如果不是最后一次：total += min(timeSeries[i+1] - timeSeries[i], duration)
-
对于最后一次攻击：total += duration
iii）返回 total
1.3 代码实现
class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int n = timeSeries.length;if (n == 0) return 0;int total = 0;for (int i = 0; i < n - 1; i++) {total += Math.min(timeSeries[i + 1] - timeSeries[i], duration);}total += duration; // 最后一次攻击的完整中毒时间return total;}
}
复杂度分析：
-
时间复杂度：O(n)，只遍历一次数组
-
空间复杂度：O(1)，只使用常量额外空间
2. Z字形变换
6. Z 字形变换 - 力扣（LeetCode）
将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
P A H N A P L S I I G Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
请你实现这个将字符串进行指定行数变换的函数：
string convert(string s, int numRows);
示例 1：
输入：s = "PAYPALISHIRING", numRows = 3 输出："PAHNAPLSIIGYIR"
示例 2：
输入：s = "PAYPALISHIRING", numRows = 4 输出："PINALSIGYAHRPI" 解释： P I N A L S I G Y A H R P I
示例 3：
输入：s = "A", numRows = 1 输出："A"
提示：
1 <= s.length <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
2.1 题目解析
这是一个典型的“Z 字形字符串重排”问题，本质是按照规律将字符映射到不同的行，然后按行读取。
抽象后可以看作：
-
给定字符串 s
-
给定行数 numRows
-
将字符串按 Z 字形排列形成多行
-
最终输出每行依次拼接后的结果
常规解法：
-
最直观的做法是构造一个二维数组 char[numRows][?]，把每个字符放到对应行和列，然后按行读取。
-
复杂度分析：
-
时间：O(n) 遍历字符串
-
空间：O(numRows * len_per_row) → 多余存储，尤其 numRows 接近 n 时
-
问题分析：
-
二维数组存储浪费空间
-
规律可观察到：
-
一个完整 Z 周期长度 = 2*numRows - 2
-
第 0 行和最后一行：每周期只取一次字符
-
中间行：每周期要取两次字符（竖直 + 斜向）
-
-
因此无需显式二维存储，可以直接计算每行字符索引
思路转折：
-
线性扫描行号，每行按照周期公式取字符
-
避免二维数组 → 节省空间
-
核心在于理解周期长度和每行字符的索引规律
2.2 解法
-
Z 字形排列的规律可以用公式表示：
周期长度=d=2∗numRows−2
-
每行字符索引：
-
第一行：0, 0+d, 0+2d, ...
-
中间行 i：竖直字符 j+i，斜向字符 j+d-i（j 为周期起点）
-
最后一行：numRows-1, numRows-1+d, ...
-
i）处理特殊情况：numRows == 1 → 返回原字符串
ii）初始化 StringBuilder ret
iii）遍历第一行字符，按周期添加
iiii）遍历中间行：
-
外层循环：行号 i = 1 → numRows-2
-
内层循环：每个周期起点 j = 0, j+d, j+2d, ...
-
对每个周期 append 两次字符：竖直和斜向（若未越界）
iiiii）遍历最后一行字符，按周期添加
iiiiii）返回 ret.toString()
2.3 代码实现
class Solution {public String convert(String s, int numRows) {int n = s.length();if(numRows == 1) return s; // 特殊情况StringBuilder ret = new StringBuilder();int d = 2*numRows - 2; // 周期长度// 第一行for(int i = 0; i < n; i += d){ret.append(s.charAt(i));}// 中间行for (int i = 1; i < numRows - 1; i++) {for (int j = 0; j + i < n; j += d) {ret.append(s.charAt(j + i)); // 竖直字符if (j + d - i < n) { // 斜向字符ret.append(s.charAt(j + d - i));}}}// 最后一行for(int j = numRows - 1; j < n; j += d){ret.append(s.charAt(j));}return ret.toString();}
}
复杂度分析：
-
时间复杂度：O(n)，每个字符访问一次
-
空间复杂度：O(n)，StringBuilder 存储最终结果
——四元数、延迟函数、协同程序)
)
