【C++算法】模拟算法

替换所有的问号

• 题目链接

替换所有的问号https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

• 算法原理

• 代码步骤

class Solution {
public:string modifyString(string s) {int n = s.size();for(int i = 0; i < n; i++){if(s[i] == '?'){for(int j = 'a'; j <= 'z'; j++){if((i == 0 || s[i - 1] != j) && (i == n - 1 || s[i + 1] != j)){s[i] = j;break;}}}}return s;}
};

提莫攻击

• 题目链接

提莫攻击https://leetcode.cn/problems/teemo-attacking/description/

• 算法原理

• 代码步骤

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字形变换

• 题目链接

Z字型变换https://leetcode.cn/problems/zigzag-conversion/description/

• 算法原理

• 代码步骤

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1){return s;}int n = s.size();int d = 2 * numRows - 2;string ret;// 第一行for(int i = 0;i < n; i += d){ret += s[i];}// 中间行for(int i = 1; i < numRows - 1; i++){for(int j = i, k = d - i; j < n || k < n; j += d, k += d){if(j < n) ret += s[j];if(k < n) ret += s[k];}}// 最后一行for(int i = numRows - 1; i < n; i += d){ret += s[i];}return ret;}
};

外观数列

• 题目链接

外观数列https://leetcode.cn/problems/count-and-say/description/

• 算法原理

• 代码步骤

class Solution {
public:string countAndSay(int n) {string s = "1";for(int i = 2; i <= n; i++){string tmp;for(int left = 0, right = 0; right < s.size(); ){while(right < s.size()){if(s[left] != s[right]) break;right++;}tmp += to_string(right - left) + s[left];left = right;}s = tmp;}return s;}
};

数青蛙

• 题目链接

数青蛙https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/

• 算法原理

• 代码步骤

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string s = "croak";int n = s.size();vector<int> ret(n);// 哈希找下表unordered_map<char, int> hash;for(int i = 0; i < n; i++){hash[s[i]] = i;}for(auto ch : croakOfFrogs){if(ch == 'c'){if(ret[n - 1] != 0){ret[n - 1]--;ret[0]++;}else{ret[0]++;}}else{if(ret[hash[ch] - 1] != 0){ret[hash[ch] - 1]--;ret[hash[ch]]++;}else{return -1;}}}for(int i = 0; i < n - 1; i++){if(ret[i] != 0) return -1;}return ret[n - 1];}
};