LeetCode 模拟章节 （持续更新中）
简单
495. 提莫攻击
在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。
当提莫攻击艾希，艾希的中毒状态正好持续
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^40 <= timeSeries[i], duration <= 10^7timeSeries按 非递减 顺序排列
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ans = 0;
int past = -1;
for (int i = 0; i < timeSeries.size(); ++i) {
int now = timeSeries[i] + duration - 1;
if (past < timeSeries[i]) // 不会重复中毒
ans += duration;
else // 重复中毒
ans += (now - past);
past = now;
}
return ans;
}
1576. 替换所有的问号
给你一个仅包含小写英文字母和
'?'字符的字符串s，请你将所有的'?'转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。注意：你 不能 修改非
'?'字符。题目测试用例保证 除
'?'字符 之外，不存在连续重复的字符。在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。
示例 1：
输入：s = "?zs" 输出："azs" 解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。示例 2：
输入：s = "ubv?w" 输出："ubvaw" 解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。提示：
1 <= s.length <= 100s仅包含小写英文字母和'?'字符
string modifyString(string s) {
for (int i = 0; i < s.size(); ++i)
if (s[i] == '?')
for (char ch = 'a'; ch <= 'c'; ++ch)
if ((i == 0 || ch != s[i - 1]) && (i >= s.size() || ch != s[i + 1]))
s[i] = ch;
return s;
}
中等
6. 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"提示：
1 <= s.length <= 1000s由英文字母（小写和大写）、','和'.'组成1 <= numRows <= 1000
通过画图找规律：
-
公差：
d = 2 * numRows - 2 -
第一行：从
0开始，每个数差d -
中间行：从
i开始，第一个数i + n * d，第二个数d - i + n * d -
最后一行：从
numRows - 1开始，每个数差d
string convert(string s, int numRows) {
if (numRows == 1)
return s;
int length = s.size();
string ans(s.size(), 0);
int pos = 0;
int d = 2 * numRows - 2;
// 第一行
for (int i = 0; i < length; i += d)
ans[pos++] = s[i];
// 中间行
for (int i = 1; i < numRows - 1; ++i) {
for (int j = 0; i + j < length; j += d) {
ans[pos++] = s[i + j];
if (j + d - i < length)
ans[pos++] = s[d - i + j];
}
}
// 最后一行
for (int i = numRows - 1; i < length; i += d)
ans[pos++] = s[i];
return ans;
}
38. 外观数列
「外观数列」是一个数位字符串序列，由递归公式定义：
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”
解释：
这是基本情况。
提示：
1 <= n <= 30**进阶：**你能迭代解决该问题吗？
递归。
string countAndSay(int n) {
if (n == 1)
return "1";
string str = countAndSay(n - 1);
string ret;
for (int i = 0; i < str.size(); ++i) {
int count = 1;
while (i + 1 < str.size() && str[i] == str[i + 1]) {
count++;
i++;
}
ret += to_string(count);
ret += str[i];
}
return ret;
}
循环迭代。
string countAndSay(int n) {
string str = "1";
for (int i = 1; i < n; ++i) {
string tmp;
for (int j = 0; j < str.size(); ++j) {
int count = 1;
while (j + 1 < str.size() && str[j] == str[j + 1]) {
count++;
j++;
}
tmp += to_string(count);
tmp += str[j];
}
str = tmp;
}
return str;
}
1419. 数青蛙
给你一个字符串
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" 的有效组合。提示：
1 <= croakOfFrogs.length <= 105- 字符串中的字符只有
'c','r','o','a'或者'k'
遍历字符串，每个字母对应当前有一个青蛙在此叫
-
c时：因为目标是不同青蛙的最少数目，所以判断有没有位于最后一个字母k的青蛙，如果有，最后一个字母青蛙 - 1，当前位置青蛙 + 1；如何没有，仅当前位置青蛙 + 1。 -
r, o, a, k时：向前查找有没有位于前一个字母的青蛙，如果有，位于前一个字母的青蛙 - 1，当前位置青蛙 + 1；如何没有，返回 -1。
int minNumberOfFrogs(string croakOfFrogs) {
// 构建索引
string s = "croak";
unordered_map<char, int> index;
for (int i = 0; i < s.size(); ++i)
index[s[i]] = i;
int hash[5] = {0};
// 模拟
for (char ch : croakOfFrogs) {
if (ch == 'c') { // c
if (hash[4] > 0) { // index['k'] = 4
hash[4]--;
hash[0]++; // index['c'] = 0
} else {
hash[0]++;
}
} else { // r, o, a, k
if (hash[index[ch] - 1] > 0) {
hash[index[ch] - 1]--;
hash[index[ch]]++;
} else {
return -1;
}
}
}
// 不能有剩余字符
for (int i = 0; i < 4; ++i)
if (hash[i] > 0)
return -1;
return hash[4];
}