【LeetCode热题100】模拟

这篇博客记录了模拟相关的题目，也就是按照题目的描述写代码，很锻炼代码实现能力，包括了替换所有的问号、Z字形变换、外观数列、数青蛙4道题。

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])){s[i] = ch;break;}}}}return s;}
};

题目分析：这道题很简单，从前往后扫描字符串，直到遇到‘?’，然后从a-z字符中选取一个符合要求的字符，也就是这个字符既不能和前一个字符一样，又不能和后一个字符一样。需要特殊考虑的是，如果‘?’是第一个字符，就不需要考虑其前一个字符，同样的，如果如果‘?’是最后一个字符，就不需要考虑其后一个字符。

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

我们把字符串的下标按题目要求写成‘Z’字，然后去寻找规律：

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

题目分析：假设我们现在有数列 4 4 4 5 5 8 7 7 7 7，我们可以这样得到它的迭代，使用双指针，left = 0，right=0，然后right++，直到nums[right] != nums[left]，此时双指针区间的就是right-left哥nums[left]，记录下来，然后让left=right，继续right++，直到nums[right] != nums[left]，依次往复这个过程，直到走到最后。

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string str = "croak";int n = str.size();//vector<int> hash(n);int hash[5] = {0};unordered_map<char,int> map;for(int i = 0; i < n ; i++)map[str[i]] = i;for(auto ch : croakOfFrogs){if(ch == str[0]){if(hash[n-1]) hash[n-1]--;hash[0]++;}else{if(hash[map[ch]-1]) {hash[map[ch]-1]--;hash[map[ch]]++;}else return -1;}}for(int i = 0 ; i < n-1 ; i++){if(hash[i]) return -1;}return hash[n-1];}
};

题目分析：这道题仍然是采用模拟的方法解决。我们要创建一个哈希表，这个哈希表存放"c","r","o","a","k"五个字符出现的个数。

具体来说，从前往后遍历所给字符串，如果这个字符是"r","o","a","k"，就去哈希表中找一下前驱字符（比如“r”的前驱字符是“c”，“k”的前驱字符是“a”，找前驱字符我们需要另外创建一个哈希表），如果其前驱字符存在，那么前驱字符个数--，当前字符个数++；如果其前驱字符不存在，则返回-1，表明这个字符无效，因为其前驱字符未被叫出来。

如果这个字符是“c”，我们需要找最后一个字符，是否在哈希表中存在，如果存在，表明现在有空闲的青蛙，让这个空闲的青蛙去叫，也就是最后一个字符--，当前字符++；如果不存在，那么当前字符++。