【C++刷题】优选算法——模拟

1. 替换所有的问号

string modifyString(string s)
{if (s.size() == 1){if (s[0] != '?') return s;else return "a";}for (int i = 0; i < s.size(); ++i){if (s[i] == '?') // 遇到'?'{if (i != 0) // '?' 不在 0 位置 说明左边有字母{if (i + 1 < s.size()) // 说明右边有元素{for (int c = 'a'; c <= 'z'; ++c){if (s[i - 1] != c && s[i + 1] != c){s[i] = c;break;}}}else // 右边没有元素{for (int c = 'a'; c <= 'z'; ++c){if (s[i - 1] != c){s[i] = c;break;}}}}else // '?' 在 0 位置 (此时右边肯定有元素){if (s[i + 1] != '?') // 右边元素是字母{for (int c = 'a'; c <= 'z'; ++c){if (s[i + 1] != c){s[i] = c;break;}}}else // 右边元素是'?'{s[i] = 'a';}}}}return s;
}

2. 提莫攻击

int findPoisonedDuration(vector<int>& timeSeries, int duration)
{int time = 0;int start = timeSeries[0], end = start + duration - 1; // [start, end]for(int i = 1; i < timeSeries.size(); ++i){if(timeSeries[i] <= end){end = timeSeries[i] + duration - 1;}else{time += end - start + 1;start = timeSeries[i];end = start + duration - 1;}}time += end - start + 1;return time;
}int findPoisonedDuration(vector<int>& timeSeries, int duration)
{int time = 0;for(int i = 1; i < timeSeries.size(); ++i){int interval = timeSeries[i] - timeSeries[i-1];if(interval >= duration) time += duration;else time += interval;}return time + duration;
}

3. Z 字形变换

// tips:当发现一个模拟策略复杂度太高，大多数情况下都是在模拟中找规律来进行优化
string convert(string s, int numRows)
{if(s.size() <= numRows || numRows == 1) return s;string ret;int interval = 2 * numRows - 2; // 公差间隔for(int i = 0; i < s.size(); i += interval) ret += s[i];for(int i = 1; i < numRows - 1; ++i){for(int left = i, right = interval - left; left < s.size() || right < s.size(); left += interval, right += interval){if(left < s.size()) ret += s[left];if(right < s.size()) ret += s[right];}}for(int i = numRows - 1; i < s.size(); i += interval) ret += s[i];return ret;
}

4. 外观数列

string RLE(const string& str)
{string ret;int start = 0, end = start + 1;for( ; end < str.size(); ++end){if(str[end] != str[start]){ret += to_string(end - start);ret += str[start];start = end;}            }ret += to_string(end - start);ret += str[start];return ret;
}
// 递归
string countAndSay(int n)
{if(n == 1) return "1";return RLE(countAndSay(n-1));
}
// 迭代
string countAndSay(int n)
{string ret = "1";for(int i = 2; i <= n; ++i){ret = RLE(ret);}return ret;
}

5. 数青蛙

int minNumberOfFrogs(string croakOfFrogs)
{unordered_map<char, int> hash = {{'c', 0},{'r', 1},{'o', 2},{'a', 3},{'k', 4}};vector<int> v(5);for(char ch : croakOfFrogs){if(ch != 'c'){if( v[ hash[ch] - 1 ] != 0 ){v[hash[ch]]++;v[hash[ch] - 1]--;}else return -1;}else // ch == 'c'{if( v[hash['k']] > 0 ) v[hash['k']]--;v[hash['c']]++;}}for(int i = 0; i < v.size() - 1; ++i){if(v[i] != 0) return -1;}return v[hash['k']];
}