C++算法
模拟算法专题：替换所有的问号、提莫攻击、Z 字形变换等
模拟算法专题涵盖替换所有的问号、提莫攻击、Z 字形变换、外观数列及数青蛙五道题目。通过遍历字符串、计算时间差值、寻找周期规律、统计字符序列及模拟青蛙叫声状态等方法解决。代码实现采用 C++，包含边界条件处理与逻辑推导过程。适合算法初学者练习模拟类问题思路。
模拟算法专题涵盖替换所有的问号、提莫攻击、Z 字形变换、外观数列及数青蛙五道题目。通过遍历字符串、计算时间差值、寻找周期规律、统计字符序列及模拟青蛙叫声状态等方法解决。代码实现采用 C++，包含边界条件处理与逻辑推导过程。适合算法初学者练习模拟类问题思路。
题目链接：1576. 替换所有的问号
纯模拟。从前往后遍历整个字符串，找到问号之后，就用 a~z 的每一个字符去尝试替换即可。
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;
}
};
题目链接：495. 提莫攻击
思路：模拟 + 分情况讨论。
我们只要计算相邻两个时间点的差值即可：
duration 秒；class Solution {
public:
int findPoisonedDuration(vector<int>& timeSeries, int duration) {
int ret = 0;
int n = timeSeries.size();
for (int i = 1; i < n; i++) {
int x = timeSeries[i] - timeSeries[i - 1];
if (x >= duration) {
ret += duration;
} else {
ret += x;
}
}
return ret + duration;
}
};
题目链接：6. Z 字形变换
| 行号 | 数字（表达式） | 数字（值，row=4） |
|---|---|---|
| 1 | 0, 2row-2, 4row-4 | 0, 6, 12 |
| 2 | 1, 2row-3, 2row-1, 4row-5, 4row-3 | 1, 5, 7, 11, 13 |
| 3 | 2, 2row-4, 2row, 4row-6, 4row-2 | 2, 4, 8, 10, 14 |
| 4 | 3, 2row+1, 4row-1 | 3, 9, 15 |
| 行号 (i) | 数字序列（用 T 表示） | 说明 |
|---|---|---|
| i=0 | 0, T, 2T | 公差为 T 的等差数列 |
| i=1 | 1, T-1, T+1, 2T-1, 2T+1 | 第一个数为 i，之后每组两个数围绕 T 的倍数对称 |
| i=2 | 2, T-2, T+2, 2T-2, 2T+2 | 同上 |
| i=3 | 3, T+3, 2T+3 | 公差为 T 的等差数列 |
第一行、第四行为差为 2row-2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标为 (2n - 1 , 2n) 的数围绕 (2row - 2) 的倍数左右取值。
class Solution {
public:
string convert(string s, int numRows) {
if (numRows == 1) return s;
string ret;
int d = 2 * numRows - 2;
int 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;
}
};
题目链接：38. 外观数列
所谓【外观数列】，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。
class Solution {
public:
string countAndSay(int n) {
string ret = "1";
for (int i = 1; i < n; i++) {
string tmp;
int len = ret.size();
for (int left = 0, right = 0; right < len;) {
while (right < len && ret[left] == ret[right]) right++;
tmp += to_string(right - left) + ret[left];
left = right;
}
ret = tmp;
}
return ret;
}
};
题目链接：1419. 数青蛙
模拟青蛙的叫声。
'r', 'o', 'a', 'k' 这四个字符的时候，我们要去看看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1;'c' 这个字符的时候，我们去看看 'k' 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 'c' 这个字符；如果没有的话，就重新搞一个青蛙。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 (auto ch : croakOfFrogs) {
if (ch == 'c') {
if (hash[n - 1] != 0) hash[n - 1]--;
hash[0]++;
} else {
int i = index[ch];
if (hash[i - 1] == 0) return -1;
hash[i - 1]--, hash[i]++;
}
}
for (int i = 0; i < n - 1; i++)
if (hash[i] != 0) return -1;
return hash[n - 1];
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online