算法分析 ——《模拟》

《替换所有的问号》

题目描述：

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

代码演示：

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

代码解析：

因为该系列为模拟专题，其实这部分还是要寻找规律，然后就是仔细读题，剩下的还是很容易的，那么我们就从最简单的一道模拟题开始进行分析。

题目说的是把字符串中的「问号」字符转换成小写字母，
而这个小写字母不能与他的前一个和后一个一样。
但是这个「问号」可能会出现在第一个和最后一个

因此我们只需要满足条件：
1、当「问号」出现在第一个位置时，只需要看「问号」后的那个元素即可。
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 。

代码演示：

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

代码解析：

对于这道题，我们只需要在自己的草稿本上画画图，就能很快理解题目，并想出算法思路：

通过图就能很清楚的看到所谓的中毒时间是会有重复的问题，但是我们可以发现：

1、如果两个时间点之间的距离 >= duration，那么「中毒时间」就代表**前一个时间点**可以满足duration这个时间段

2、如果两个时间点之间的距离 < duration，那么「中毒时间」就代表前一个时间点到后一个时间点的距离

3、因为我们是要从第二个时间点开始算，然后比较前一个，因此在最后还要加上最后一个时间点的中毒持续时间。

《Z 字形变换》

题目描述：

将一个给定字符串 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"

代码演示：

class Solution 
{
public:// 找规律！string convert(string s, int numRows) {// numRows为1时 需单独讨论if(numRows == 1) return s;int d = 2 * numRows - 2;string ret; // 接收答案for(int i = 0; i < numRows; ++i){int j = i;if(i == 0 || i == numRows - 1){while(j < s.size()) {ret += s[j];j += d;}}else{int k = d - j;while(j < s.size() || k < s.size()){if(j < s.size()) ret += s[j];if(k < s.size()) ret += s[k];j += d;k += d;}}}return ret;}
};

代码解析：

据我所知的模拟题一般都是这种，是需要我们找规律的，这道题还是很好读懂和理解的，那接下来我就介绍介绍这道题的算法思路：

我们将字母按照下标顺序来模拟，那么不难发现有一个重要的规律：

第一行和最后一行，每个下标之间都差 2(numRows - 1)距离

拿第一个numRows为4举例子
1、第一行和最后一行每个元素之间差了6，正好满足公式2(numRows - 1)
2、中间的这些行，1和5相差4，7和11相差4，而5和11相差了6.

第一行和最后一行好求，难求的点也只在于中间各个元素之间的规律，还是拿numRows为4的时候举例，1和7也相差6，那就可以得知0123和6789这两列永远相差2(numRows - 1)距离。

我们将2(numRows - 1)的计算结果计为 d，那么1要想到5就得取(d - 1)，同理2要想到4就得取(d - 2)，

所以在计算中间的规律时，只需要一对一对的比较即可，意思就是加上1号下标后再加上(d - 1)号下标的，然后他们都加上d，这时就加上7号和11号即可。

《外观数列》

题目描述：

「外观数列」是一个数位字符串序列，由递归公式定义：

• countAndSay(1) = "1"
• countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

**输入：**n = 4

输出：“1211”

解释：

countAndSay(1) = “1”

countAndSay(2) = “1” 的行程长度编码 = “11”

countAndSay(3) = “11” 的行程长度编码 = “21”

countAndSay(4) = “21” 的行程长度编码 = “1211”

示例 2：

**输入：**n = 1

输出：“1”

代码演示：

class Solution 
{
public:string countAndSay(int n) {if(n == 1) return "1";string s = countAndSay(n - 1); // 获取上一次数据string ret;for(int left = 0, right = 0; right < s.size(); ){while(right < s.size() && s[left] == s[right]) right++;ret += to_string(right - left) + s[left];left = right;}        return ret;}
};

代码解析：

这道题目的描述完全就是阅读理解，我先来介绍下题目是让我们干嘛的。

简单来说，就是去描述第n - 1时的字符串个数，如果n - 1的字符串是21，那么就是1个2、1个1，变成字符串就是1211.

那在这里有两种做法，一种就是循环 + 双指针，因为每次都是对上一次结果的统计，那就从1开始慢慢统计，然后就是用递归也就是迭代的方法来解决，方法都是一致的。

就简单来讲讲双指针的逻辑：

《数青蛙》

题目描述：

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

代码演示：

class Solution 
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> hash(n);// 记录下标unordered_map<char, int> index; for(int i = 0; i < n; ++i) index[t[i]] = i;for(const auto& ch : croakOfFrogs){if(ch == 'c'){if(hash[n - 1]) hash[n - 1]--;hash[0]++;}else{// 针对r, o, a, kint pos = index[ch]; // 找到当前字母对应的下标if(hash[pos - 1]){hash[pos - 1]--;hash[pos]++;}else return -1;}}// 额外判断for(int i = 0; i < n - 1; ++i) if(hash[i]) return -1;return hash[n - 1];}
};

代码解析：

这题意对我来说又是一道阅读理解，我先简单讲讲题目意思吧。
简单来说，就是有一声蛙叫"croak"，一只青蛙可以连续叫多次"croak"，但是当一只青蛙在叫"croak"的过程中，这时又来了一个c，那么就得叫另外一只青蛙过来了。同时一定要满足字符串排序完之后肯定可以出现一个或多个"croak"。

所以具体的解决方法其实就是去一个一个的判断

第一步我们需要去给每个 croak 每个字符都编一个号，从0开始，然后利用哈希表讲给的的字符串一个一个比较