【优选算法】模拟 问题算法

​一：替换所有的问号

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]) || ( i>0 && i<n-1 && ch != s[i-1] && ch != s[i+1])){s[i] = ch;break;}}}}return s;}
};

二：提莫攻击

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

三：Z字形变换

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;string ret;int n = s.size();int d = 2*numRows-2;// 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;}
};

四：外观数列

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

五：数青蛙​

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";int n = t.size();// 使用数组来模拟哈希表vector<int> hash(n);// 使用 map 来表示 字符的下标unordered_map<char, int> char_Index;for(int i = 0; i < n; i++)char_Index[t[i]] = i;// 开始操作for(auto& ch : croakOfFrogs){if(ch == 'c'){if(hash[n-1] != 0)hash[n-1]--;        // 一个青蛙叫完之后，继续叫hash[0]++;}else{int i = char_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];}
};