《算法题讲解指南：优选算法-模拟》--38.替换所有问号，39.提莫攻击，40.Z 字形变换

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》

《C++入门到进阶&自我学习过程记录》《算法题讲解指南》--从优选到贪心

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

目录

38.替换所有问号

题目链接：

题目描述：

题目示例：

解法（模拟）：

算法思路：

C++算法代码：

算法总结及流程解析：

39.提莫攻击

题目链接：

题目描述：

题目示例：

解法（模拟+分情况讨论）：

算法思路：

C++算法代码：

算法总结及流程解析：

40.Z 字形变换

题目链接：

题目描述：

题目示例：

解法（模拟+找规律）：

算法思路：

C++算法代码：

算法总结及流程解析：

结束语

38.替换所有问号

题目链接：

1576. 替换所有的问号 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟）：

算法思路：

      就是模拟这个过程就行。从前往后遍历整个字符串，找到问号之后，就用 a~z 的每一个字符去尝试替换即可。 

C++算法代码：

class Solution { public: string modifyString(string s) { for(int i = 0; i < s.size(); i++) { if(s[i] == '?') { for(char c = 'a'; c <= 'z'; c++) { if((i == 0 || s[i - 1] != c) && (i == s.size() - 1 || s[i + 1] != c)) { s[i] = c; break; } } } } return s; } };

算法总结及流程解析：

39.提莫攻击

题目链接：

495. 提莫攻击 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟+分情况讨论）：

算法思路：

      模拟+分情况讨论。
      计算相邻两个时间点的差值：

• 如果差值大于等于中毒时间，说明上次中毒可以持续 duration 秒。
• 如果差值小于中毒时间，那么上次的中毒只能持续两者的差值

      还可以这样想，我们每次加上 min(duration,差值) 就行。

C++算法代码：

class Solution { public: int findPoisonedDuration(vector<int>& timeSeries, int duration) { int sum = 0; for(int i = 0; i < timeSeries.size() - 1; i++) { // if(timeSeries[i + 1] - timeSeries[i] >= duration) // { // sum += duration; // } // else // { // sum += timeSeries[i + 1] - timeSeries[i]; // } sum += min(timeSeries[i + 1] - timeSeries[i], duration); } sum += duration; return sum; } };

算法总结及流程解析：

40.Z 字形变换

题目链接：

6. Z 字形变换 - 力扣（LeetCode）

题目描述：

题目示例：

解法（模拟+找规律）：

算法思路：

      找规律，用 row 代替行数，row = 4 时画出的 N 字形如下：
0 2row - 2 4row - 4
1 2row - 3 2row - 1 4row - 5 4row - 3
2 2row-4 2row 4row - 6 4row - 2
3 2row + 1 4row - 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) { // string ret; // int d = 2 * numRows - 2; // if(d == 0) // { // return s; // } // for(int i = 0; i < numRows; i++) // { // int j = i; // int flag = 0; // if(i == numRows - 1) // { // flag = 1; // } // while(j < s.size()) // { // ret.push_back(s[j]); // if(flag == 0) // { // j += (d - 2 * i); // if(i != 0) // { // flag = 1; // } // } // else // { // j += (2 * i); // if(i != numRows - 1) // { // flag = 0; // } // } // } // } // return ret; //代码优化： 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; } };

算法总结及流程解析：

结束语

      到此，38.替换所有问号，39.提莫攻击，40.Z 字形变换 这三道算法题就讲解完了。替换所有问号(1576题)：通过遍历字符串，对每个问号使用a-z字符尝试替换，确保不与前后字符重复。提莫攻击(495题)：计算中毒总时间，通过比较相邻攻击时间差与中毒持续时间，取较小值累加。Z字形变换(6题)：通过模拟和找规律，将字符串按Z字形排列后逐行读取。核心思路是识别以2*numRows-2为周期的下标规律，分首行、中间行和末行处理。 希望大家能有所收获！