模擬算法：題目中已經(jīng)告訴應(yīng)該怎么做了，只需要模擬即可，思路比較簡單，比較考察代碼能力。

一般先在草稿紙上模擬流程，如果直接寫代碼，容易忽視細(xì)節(jié)，并且不容器調(diào)試！

優(yōu)化策略：找規(guī)律！

Z 形變換

?Z 字形變換

• 暴力模擬
• 找規(guī)律

// 暴力模擬
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;}
};

// 找規(guī)律
class Solution {
public:string convert(string s, int numRows) {// 模擬類題目的優(yōu)化思路：找規(guī)律if(numRows == 1) return s;int d = 2 * numRows - 2; // 計(jì)算公差  第一行和最后一行元素相隔的距離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++){// 循環(huán)處理每一行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;}
};

數(shù)青蛙

數(shù)青蛙

• 暴力模擬
• 哈希模擬

// 暴力模擬
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)//沒有青蛙叫結(jié)束了hash['c' - 'a']++;else{hash['c' - 'a'] ++;hash['k' - 'a'] --; // 有 叫結(jié)束的青蛙}}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" 順序的字符對(duì)應(yīng)的字符個(gè)數(shù) 
// unordered_map 中存字符和字符對(duì)應(yīng)于 hash 中的下標(biāo)
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 存這個(gè)字符對(duì)應(yīng)的下標(biāo)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為下標(biāo)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];}
};

外觀數(shù)列?

外觀數(shù)列

用遞歸來模擬

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

替換所有的問號(hào)

替換所有的問號(hào)

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; // 中毒總秒數(shù)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;}
};