目录
1、模拟算法简介
2、替换所有问号
3、提莫攻击
4、Z字形变换
5、外观数列
6、数青蛙
1、模拟算法简介
模拟算法是一种基本的算法设计方法,它的核心思想是按照问题描述的规则,逐步模拟问题的发展过程,从而得到问题的解决方案。这种算法通常不依赖于复杂的数学公式或高级的数据结构,而是通过直接模拟现实世界中的操作或规则来解决问题。
2、替换所有问号
1576. 替换所有的问号
从前往后遍历整个字符串,找到问号之后,就用 a ~ z 的每⼀个字符去尝试替换即 可
class Solution {
public:string modifyString(string s) { // 模拟,算法流程int n = s.size();for(int i = 0;i < n;i++){ // 遍历数组,找到?,替换if(s[i] == '?'){for(char ch = 'a';ch <= 'z';ch++){ // (?在开头||替换值与前面的字符不同) // && (?在结尾||替换值与后面字符不同)if((i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1])){s[i] = ch;break;}}}}return s;}
};
3、提莫攻击
495. 提莫攻击
class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int T = 0;for(int i = 1;i < timeSeries.size();i++){ // 计算两次中毒的时间间隔int time = timeSeries[i] - timeSeries[i-1];// 间隔大于标准中毒时间,按标准计时 if(time > duration) T += duration;// 否则,计时会重置,所以只记录间隔时间else T += time;}// 别忘了最后一次中毒T += duration;return T;}
};
4、Z字形变换
6. Z 字形变换
方法一:用字符串数组vector<string>模拟Z字形存入数据,再将字符串数组中的字符串按行号顺序连接。
遍历字符串s时:用 flag 来做索引标记,到达Z字形转折点时的时候 (第一行 / 最后一行),执行反向 (flag = -flag) 。更新下标索引时,用 i += flag 。
class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;// 1.将数据存入字符串数组vector<string> vs(numRows);int i = 0,flag = -1;for(auto& x: s){vs[i] += x; // 刚进循环,第一个数据flag是-1if(i == 0 || i == numRows-1) // 第一/最后一行是转折点flag = -flag; // 用flag控制存储的方向,位置i += flag;}// 2.将字符串数组中所有字符串按行号顺序接合起来string str;for(string& rows: vs)str += rows;return str;}
};
方法二:找规律:
第1/numRows行,隔2*numRows-2是一个元素。
中间行,两组数据从(k,d-k)开始,每次隔2*numRows-2是一组数据,可能最后会有一个数据越界。
class Solution {
public:string convert(string s, int numRows) {// 边界情况if(numRows == 1) return s;// 找规律:第1/numRows行,隔2*numRows-2是一个元素// 中间行,两组数据从(k,d-k)开始,每次隔2*numRows-2是一组数据,// 可能最后会有一个数据越界string str;int d = 2 * numRows - 2; // 计算步长int n = s.size();// 处理第一行,从s[0]开始for(int i = 0;i < n;i += d)str += s[i];// 处理中间行的每一行,从(s[k],s[d-k])开始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) str += s[i];if(j < n) str += s[j];}}// 处理最后一行,从s[numRows-1]开始for(int i = numRows-1;i < n;i += d)str += s[i];return str;}
};
5、外观数列
. - 力扣(LeetCode)
模拟 + 双指针,双指针用来模拟顺序读取下字符的连续次数。
class Solution {
public:string countAndSay(int n) {// 模拟 + 双指针string ret = "1"; // 初始值for (int i = 1;i < n; i++) // 模拟n-1次,因为第一次就是1{string tmp;int len = ret.size(); // 限定区域是在ret内for(int left = 0,right = 0;right < len;){while (right < len && ret[left] == ret[right]) right++;// 确定重复次数tmp += to_string(right - left); // 重复次数tmp += ret[left]; // 对应字符left = right; // 重置指针}ret = tmp; // 更换新字符串}return ret;}
};
6、数青蛙
. - 力扣(LeetCode)
方法:模拟 + 分情况讨论
用哈希表模拟寻找青蛙叫声的过程,开始时,青蛙开始发出叫声【c】,在哈希表中映射记录一次【c】叫声,假设紧接着发出【r】时,就要先在哈希表中找【r】的前驱字符【c】是否已经记录过叫,如果有记录就把这个记录传承下来,前驱【c】的叫声次数-1,当前【r】的叫声+1次;如果没有记录,就说明此时字符串记录的叫声是不完整的,不是有效组合。后续【o】...叫声与上面演示的【r】的处理方式类似。
但因为我们要找的是最少的青蛙数,青蛙在叫完完整一次“croak”后可以紧接着继续蛙鸣,所以,当读到【c】时还有一种情况是先查看哈希表中对应的【k】叫声个数,如果不是0,说明有青蛙可以重新开始一轮蛙鸣,对应我们的操作就是把记录到的【k】叫声个数-1,给【c】叫声个数+1。
总结:
1、r o a k ---> 查看前序字符是否在哈希表中存储个数
(1)存在:前驱个数--,当前个数++
(2)不存在:返回-1
2、c ---> 找最后一个字符 k 在哈希表中是否存储
(1)存在:k字符个数--,c字符个数++
(2)不存在:c字符个数++
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) { // 用哈希表模拟string str = "croak"; // 先把叫声存储起来int n = str.size();vector<int> hash(n); // 数组模拟哈希表,用下表对应存储str的每个字符(‘c’对应0...)unordered_map<char,int> index(n); // 存储 [x,x对应的下标] 方便寻找前驱字符(通过下标)for(int i = 0;i < n; i++)index[str[i]] = i;for(auto ch : croakOfFrogs){if(ch == 'c'){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{int prev = index[ch] - 1; // 找到前驱字符的下标if(hash[prev] == 0) return -1;hash[prev]--;hash[index[ch]]++;}}for(int i = 0;i < n - 1;i++)if(hash[i] != 0) return -1;return hash[n - 1];}
};
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {unordered_map<char,int> vv;for(auto e : "croak"){vv[e] = 0;}int cur = 0,len = croakOfFrogs.size();while(cur < len){if(croakOfFrogs[cur] == 'r'){if(vv['c'] > 0) {vv['c']--;vv['r']++;} else return -1;}else if(croakOfFrogs[cur] == 'o'){if(vv['r'] > 0) {vv['r']--;vv['o']++;} else return -1;}else if(croakOfFrogs[cur] == 'a'){if(vv['o'] > 0) {vv['o']--;vv['a']++;} else return -1;}else if(croakOfFrogs[cur] == 'k'){if(vv['a'] > 0) {vv['a']--;vv['k']++;} else return -1;}else if(croakOfFrogs[cur] == 'c'){if(vv['k'] > 0){vv['k']--;vv['c']++;}else vv['c']++;}cur++;}for(auto e: "croa"){if(vv[e] > 0) return -1;}return vv['k'];}
};