模拟

1.替换所有问号

在字符串中找到问号，找到合适字母替代问号，需要满足s[i-1]!=s[i]且s[i]!=s[i+1]，同时当 i == 0 和 i == s.size()-1时处理好边界条件。

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

2.提莫攻击

数组t记录攻击时刻，两次攻击时刻之差x=t[i]-t[i-1]，持续时间为d，如果x>=d，中毒时间+=d；如果x<d，中毒状态重置，此时中毒时间+=x。

class Solution4 {
public:
    int findPoisonedDuration(vector<int>& t, int d)
    {
        int ret = 0;
        for (int i = 1;i < t.size();i++)
        {
            int x = t[i] - t[i - 1];
            if (x >= d)
                ret += d;
            else
                ret += x;
        }
        return ret += d;
    }
};

3.Z字形变换

解法一：创建numRows行的矩阵，按照题意把字符串写入矩阵，再逐行从矩阵输出字符串。

解法二：解法一的空间复杂度和时间复杂度都是比较高的，像 “模拟” 这类题的优化几乎都是找规律。把矩阵中的字母改成下标。

第0行的规律，公差d=2n-2=6，n为numRows，0，0+d，0+2d，0+kd；第numRows-1行规律，numRows-1，numRows-1+d，numRows-1+2d，numRows-1+kd。中间k行规律，(k,d-k)，(k+d,d-k+d)，(k+2d,d-k+2d) ……

class Solution5 {
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)//处理边界情况
            return s;
        string ret;
        int d = 2 * numRows - 2;
        int n = s.size();

        for (int i = 0;i < n;i += d)//处理第0行
            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)//处理numRows-1行
            ret += s[i];

        return ret;
    }
};

4.外观数列

题目进一步的解释如下。

1、11、21、1211、111221……为外观数列，数列的第一项为1，题目要我们求出第n项。要求出第n项，可以用双指针处理第n-1项。

当ret[left]!=ret[right]，right-left可得字符个数，再将其用 to_string() 转成字符串，再+=ret[left]。

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

递归：

class Solution {
public:
    string countAndSay(int n)
    {
        if (n == 1)
            return "1";
        string s = countAndSay(n - 1);

        string ret;
        for (int left = 0, right = 0;right <= s.size();right++)
        {
            if (right == s.size() || s[right] != s[left])
            {
                int count = right - left;
                ret += to_string(count);
                ret += s[left];
                left = right;
            }
        }
        return ret;
    }
};

5.数青蛙

题目要求返回最少青蛙数，字符串croakOfFrogs中，如果croak是分开的，如示例1，则说明可以一只青蛙叫两次；如果croak是混在一起的，如示例2，则说明有多个青蛙叫。

用数组创建一个哈希表hash，字符串 t=“croak” ，hash的下标对应t下标，hash[i]记录t[i]字母出现。再创建一个哈希表Index，建立t中每个字符与其下标的映射。遍历字符串croakOfFrogs，按照如下方式修改hash[i]。

例如字符串crcoakroakcroak。

可以看到，遍历字符串，如果字符串中含有croak，hash中1和0就会一直交换直到字符k，hash[Index[k]]即此时青蛙数量。如果上图的字符串仅是crcoak，则要返回-1，因为hash中除字符k外还有字符不为0，所以最后要检查hash。

遍历到某个字符，如果该字符的前一个字符在hash中对应为0，则返回-1。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs)
    {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n);

        unordered_map<char, int> Index;//字符下标
        for (int i = 0;i < n;i++)
            Index[t[i]] = i;

        for (auto& ch : croakOfFrogs)
        {
            if (ch == 'c')
            {
                if (hash[n - 1] != 0)
                    hash[n - 1]--;
                hash[0]++;
            }
            else
            {
                int i = Index[ch];
                if (hash[i - 1] == 0)
                    return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }
        for (int i = 0;i < n - 1;i++)//最后检查
            if (hash[i] != 0)
                return -1;

        return hash[n - 1];
    }
};