【刷题】模拟

模拟算法：题目中已经告诉应该怎么做了，只需要模拟即可，思路比较简单，比较考察代码能力。

一般先在草稿纸上模拟流程，如果直接写代码，容易忽视细节，并且不容器调试！

优化策略：找规律！

Z 形变换

 Z 字形变换

• 暴力模拟
• 找规律

// 暴力模拟
class Solution {
public:string convert(string s, int numRows) {vector<vector<char>> v(numRows, vector<char>(s.size()));int j = 0, k = 0; // j 为行，k 为列int count = 0;int i = 1;v[j][k] = s[0];while (i < s.size()){while (j + 1 < numRows){j++;v[j][k] = s[i];if (i < s.size()) i++;else break;}if(j == 0) {k++;v[j][k] = s[i];if (i < s.size()) i++;}while (j > 0){j--, k++;if(k < s.size()) {v[j][k] = s[i];}if (i < s.size()) i++;else break;}}string str;for (int i = 0; i < numRows; i++){for (int j = 0; j < s.size(); j++){if (v[i][j] != 0) str.push_back(v[i][j]);}}return str;}
};

// 找规律
class Solution {
public:string convert(string s, int numRows) {// 模拟类题目的优化思路：找规律if(numRows == 1) return s;int d = 2 * numRows - 2; // 计算公差  第一行和最后一行元素相隔的距离int n = s.size();string ret;// 处理第一行for(int i = 0; i < n; i += d) ret += s[i];// 处理中间行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];}}// 处理最后一行for(int i = numRows - 1; i < n; i += d) ret += s[i];return ret;}
};

数青蛙

数青蛙

• 暴力模拟
• 哈希模拟

// 暴力模拟
class Solution {
public:int minNumberOfFrogs(string s) {int hash[26] = { 0 };int n = s.size();for(int i = 0; i < n; i++){if(s[i] == 'c'){if(hash['k'-'a'] == 0)//没有青蛙叫结束了hash['c' - 'a']++;else{hash['c' - 'a'] ++;hash['k' - 'a'] --; // 有 叫结束的青蛙}}else if(s[i] == 'r'){if(hash['c' - 'a'] != 0){hash['c' - 'a'] --;hash['r' - 'a'] ++;}else return -1;} else if(s[i] == 'o'){if(hash['r' - 'a'] != 0){hash['r' - 'a'] --;hash['o' - 'a'] ++;}else return -1;} else if(s[i] == 'a'){if(hash['o' - 'a'] != 0){hash['o' - 'a'] --;hash['a' - 'a'] ++;}else return -1;} else if(s[i] == 'k'){if(hash['a' - 'a'] != 0){hash['a' - 'a'] --;hash['k' - 'a'] ++;}else return -1;} }if(hash['k' - 'a'] == 0) return -1;if(hash['c' - 'a'] != 0 || hash['r' - 'a'] != 0 || hash['o' - 'a'] != 0 || hash['a' - 'a'] != 0) return -1;return hash['k' - 'a'];}
};

// 哈希模拟
// hash 中存按 "croak" 顺序的字符对应的字符个数 
// unordered_map 中存字符和字符对应于 hash 中的下标
class Solution {
public:int minNumberOfFrogs(string s) {string t = "croak";int n = t.size();vector<int> hash(n);unordered_map<char ,int> index; // first 存字符; second 存这个字符对应的下标for(int i = 0; i < n; i++) index[t[i]] = i;for(int i = 0; i < s.size(); i++){if(s[i] == 'c'){if(hash[n - 1] == 0) hash[index[s[i]]]++;else {hash[n - 1]--;hash[index[s[i]]]++;}}else{int k = index[s[i]]; // k为下标if(hash[k - 1] != 0){hash[k - 1]--;hash[k]++;}else return -1;}}for(int i = 0; i < n - 1; i++){if(hash[i] != 0) return -1;}return hash[n - 1];}
};

外观数列 

外观数列

用递归来模拟

class Solution {
public:void _countAndSay(int n, string& str){if(n == 1) {str += "1";return;}_countAndSay(n - 1, str);int count = 0;string s_ret;for(int i = 0; i < str.size(); i++){count = 1;while(i + 1 < str.size() && str[i] == str[i + 1]){count++;i++;}s_ret += ('0' + count);s_ret += str[i];}str = s_ret;}string countAndSay(int n) {string str;_countAndSay(n, str);return str;}
};

替换所有的问号

替换所有的问号

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

提莫攻击

提莫攻击

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int count = 0; // 中毒总秒数int ret = duration;for(int i = 0; i < timeSeries.size(); i++){for(int j = 0; j < duration; j++){if(i + 1 < timeSeries.size() && timeSeries[i] + j != timeSeries[i + 1]){count++;} else break;}ret = duration;}count += duration;return count;}
};