目錄
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(n2)（如果每次都去遍歷合并區間），空間復雜度 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 存儲最終結果
——四元數、延遲函數、協同程序)
)
