C++算法
模拟算法专题：替换问号、提莫攻击、Z 字形变换、外观数列与数青蛙
模拟算法专题涵盖五个题目。替换所有问号通过遍历尝试字符避免连续重复；提莫攻击计算中毒时间间隔取最小值累加；Z 字形变换利用周期规律分行重组字符串；外观数列迭代统计连续相同字符个数生成新序列；数青蛙通过状态机模拟青蛙叫声顺序并统计所需最少青蛙数量。
模拟算法专题涵盖五个题目。替换所有问号通过遍历尝试字符避免连续重复；提莫攻击计算中毒时间间隔取最小值累加；Z 字形变换利用周期规律分行重组字符串；外观数列迭代统计连续相同字符个数生成新序列；数青蛙通过状态机模拟青蛙叫声顺序并统计所需最少青蛙数量。
题目描述： 给定一个字符串 s，其中包含小写字母和问号？。你需要将所有的问号替换为小写字母，使得最终结果中不包含连续重复的字符。
纯模拟。从前往后遍历整个字符串，找到问号之后，就用 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;
}
};
题目描述： 在《英雄联盟》的世界中，提莫的攻击可以让艾希中毒 duration 秒。给定一个非递减的整数数组 timeSeries，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个整数 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;
}
};
题目描述： 将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 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 |
不难发现，数据是以 2row-2 为一个周期进行规律变换的。 第一行、第四行为差为 2row-2 的等差数列；第二行、第三行除了第一个数取值为行数，每组下标围绕周期的倍数左右取值。
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;
}
};
题目描述： 「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。例如：
所谓【外观数列】，其实只是依次统计字符串中连续且相同的字符的个数。依照题意，依次模拟即可。
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;
}
};
题目描述： 给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 "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 (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