算法笔记（四）——模拟

模拟算法就是根据题目的要求，题目让干神马就做神马，一步一步来

替换所有的问号

题目：替换所有的问号

思路

• 从左到右遍历整个字符串，找到问号之后，就⽤ a ~ z 的每⼀个字符去尝试替换

C++代码

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;}
};

提莫攻击

题目：提莫攻击

思路

• 遍历数组当前位置减去前一个位置， 如果差值
• 大于中毒时长，就加上中毒时间
• 如果小于，就加上差值
• 最后，加上最后一次中毒时间

C++代码

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

Z字形变换

题目：Z字形变换

思路

• 如果横着看，就是数学法，找通项公式；
• 如果竖着看，在按列读取的时候，为每一行维护一个字符串，读到哪一行就在后面追加字符
• 设置两个边界，在增长到或者减小到某个边界的时候，读取行的顺序进行反转，不断地从上到下，再从下到上读取，直到取完所有字串

class Solution 
{
public:string convert(string s, int numRows) {if(numRows == 1) return s;vector<string> rows(numRows);int i = 0;int flag = -1;for(auto ch : s){rows[i].push_back(ch);if(i == 0 || i == numRows - 1){flag = -flag;}i += flag;}string res;for(auto x : rows) {res += x;}return res;}
};

外观数列

题目：外观数列

思路
模拟 + 双指针，模拟实现
C++

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 l = 0, r = 0; r < len; ){while(r < len && ret[l] == ret[r]) r++;tmp += to_string(r - l) + ret[l];l = r;}ret = tmp;}return ret;}
};

数青蛙

题目：数青蛙

思路

• 模拟将c、r、o、a、k存入哈希表；
• 遍历字符串，
• 如果遇到c，找最后一个字符，即k是否在哈希表中存在，若存在最后一个字符，即k，--，当前字符，即c，++
• 遇到其他字符，若其前驱存在，前驱个数--，当前++；若不存在，返回-1

C++代码
纯暴力

class Solution 
{
public:int minNumberOfFrogs(string croakOfFrogs) {int hash[5]={0};int n = croakOfFrogs.size();for(int i = 0;i < n;i++){if(croakOfFrogs[i] == 'c'){if(hash[4] > 0){hash[4]--;hash[0]++;}else hash[0]++;}else if(croakOfFrogs[i] == 'r'){if(hash[0] > 0){hash[0]--;hash[1]++;}else return -1;}else if(croakOfFrogs[i] == 'o'){if(hash[1]>0){hash[1]--;hash[2]++;}else return -1;}else if(croakOfFrogs[i] == 'a'){if(hash[2] > 0){hash[2]--;hash[3]++;}else return -1;}else if(croakOfFrogs[i] == 'k'){if(hash[3] > 0){hash[3]--;hash[4]++;}else return -1;}else return -1;}if(hash[0]||hash[1]||hash[2]||hash[3]) return -1;return hash[4]; }
};

借助unordered_map

class Solution 
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();vector<int> hash(n);unordered_map<char, int> mp = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};for(auto ch : croakOfFrogs){if(ch == 'c'){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;  }else{int i = mp[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];}
};