【优选算法】（第二十篇）
目录
提莫攻击（easy）
题目解析
讲解算法原理
编写代码
N字形变换（medium）
题目解析
讲解算法原理
编写代码
提莫攻击（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
在《英雄联盟》的世界中，有⼀个叫“提莫”的英雄。他的攻击可以让敌⽅英雄艾希（编者注：寒冰射⼿）进⼊中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续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<=10^4
0<=timeSeries[i],duration<=10^7
timeSeries按⾮递减顺序排列
讲解算法原理
解法（模拟+分情况讨论）：
算法思路：
模拟+分情况讨论。
计算相邻两个时间点的差值：
i. 如果差值⼤于等于中毒时间，说明上次中毒可以持续 duration 秒；
ii. 如果差值⼩于中毒时间，那么上次的中毒只能持续两者的差值。
编写代码
c++算法代码：
class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret = 0;
for(int i = 1; i < timeSeries.size(); i++)
{
int tmp = timeSeries[i] - timeSeries[i - 1];
if(tmp >= duration) ret += duration;
else ret += tmp;
}
return ret + duration;
}
};java算法代码：
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int ret = 0;
for(int i = 1; i < timeSeries.length; i++) {
int x = timeSeries[i] - timeSeries[i - 1];
if(x >= duration) ret += duration;
else ret += x;
}
return ret + duration;
}
}N字形变换（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
将⼀个给定字符串s根据给定的⾏数numRows，以从上往下、从左到右进⾏Z字形排列。⽐如输⼊字符串为"PAYPALISHIRING"⾏数为3时，排列如下：
PAHN
APLSIIG
YIR
之后，你的输出需要从左往右逐⾏读取，产⽣出⼀个新的字符串，⽐如："PAHNAPLSIIGYIR"。请你实现这个将字符串进⾏指定⾏数变换的函数：
stringconvert(strings,intnumRows);
⽰例1：输⼊：s="PAYPALISHIRING",numRows=3输出："PAHNAPLSIIGYIR"
⽰例2：输⼊：s="PAYPALISHIRING",numRows=4输出："PINALSIGYAHRPI"
解释：PINALSIGYAHR
PI
⽰例3：
输⼊：s="A",numRows=1
输出："A"
提⽰：
1<=s.length<=1000
s由英⽂字⺟（⼩写和⼤写）、','和'.'组成
1<=numRows<=1000
讲解算法原理
解法（模拟+找规律）：
算法思路：
找规律，⽤row代替⾏数，row=4时画出的N字形如下：02row-24row-4
12row-32row-14row-54row-3
22row-42row4row-64row-2
32row+14row-1
不难发现，数据是以2row-2为⼀个周期进⾏规律变换的。将所有数替换成⽤周期来表⽰的变量：第⼀⾏的数是：0,2row-2,4row-4；
第⼆⾏的数是：1,(2row-2)-1,(2row-2)+1,(4row-4)-1,(4row-4)+1；第三⾏的数是：2,(2row-2)-2,(2row-2)+2,(4row-4)-2,(4row-4)+2；第四⾏的数是：3,(2row-2)+3,(4row-4)+3。
可以观察到，第⼀⾏、第四⾏为差为2row-2的等差数列；第⼆⾏、第三⾏除了第⼀个数取值为⾏数，每组下标为(2n-1,2n)的数围绕（2row-2）的倍数左右取值。
以此规律，我们可以写出迭代算法。
编写代码
c++算法代码：
class Solution
{
public:
string convert(string s, int numRows)
{
// 处理边界情况
if(numRows == 1) return s;
string ret;
int d = 2 * numRows - 2, n = s.size();
// 1. 先处理第⼀⾏
for(int i = 0; i < n; i += d)
ret += s[i];
// 2. 处理中间⾏
for(int k = 1; k < numRows - 1; k++) // 枚举每⼀⾏
{
for(int i = k, j = d - k; i < n || j < n; i += d, j += d)
{
if(i < n) ret += s[i];
if(j < n) ret += s[j];
}
}
// 3. 处理最后⼀⾏
for(int i = numRows - 1; i < n; i += d)
ret += s[i];
return ret;
}
};java算法代码：
class Solution
{
public String convert(String s, int numRows)
{
// 处理⼀下边界情况
if(numRows == 1) return s;
int d = 2 * numRows - 2, n = s.length();
StringBuilder ret = new StringBuilder();
// 1. 处理第⼀⾏
for(int i = 0; i < n; i += d)
ret.append(s.charAt(i));
// 2. 处理中间⾏
for(int k = 1; k < numRows - 1; k++) // 依次枚举中间⾏
{
for(int i = k, j = d - i; i < n || j < n; i += d, j += d)
{
if(i < n) ret.append(s.charAt(i));
if(j < n) ret.append(s.charAt(j));
}
}
// 3. 处理最后⼀⾏
for(int i = numRows - 1; i < n; i += d)
ret.append(s.charAt(i));
return ret.toString();
}
}