【优选算法】（第二十篇）

提莫攻击（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();
 }
}