【优选算法】模拟

题目描述：

思路讲解：
本题的可以使用模拟算法来解决本题，模拟算法就依葫芦画瓢，思路比较简单，但是比较考验代码能力。

对题目进行解释就是在数组中找到每一个?，将这个?变为26个小写字母中的任意一个，但是它不能与左右两边的字母相同，例如：a?b中的?只要不变为a/b中的其中一个，就可以变为除a和b以外的其他任意的小写字母。需要注意两个特别的位置，数组的开头和结尾，数组的开头位置左边没有数据，数组的结尾位置右边没有数据，需要对这两个位置进行特殊处理。

编写代码：

class Solution {
public:
    string modifyString(string s) {
        int sLen = s.size();

        for(int i = 0 ; i <= sLen - 1; i++)
        {
            if(s[i] == '?')
            {
                for(int ch = 'a' ; ch <= 'z' ;ch++)
                {
                    if((i == 0 || s[i - 1] != ch) && (i == sLen - 1 || s[i + 1] != ch) )
                    {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }

        return s;
    }
};

题目描述：

思路讲解：
本题同样是使用模拟算法来解决，提莫对艾希进行攻击后，艾希会进入长达duration秒的中毒状态，当在艾希处于中毒状态的期间继续攻击，那么艾希的中毒时间会被重置，继续中毒duration秒。例如：艾希在1秒的时候进入中毒状态，中毒状态持续时间duration为2秒，则艾希在第三秒时就会解除中毒状态，但是若提莫在第二秒时继续攻击艾希，那么艾希的中毒时间被重置，从第二秒开始中毒2秒，则艾希在第四秒时就会解除中毒状态。

通过上面的描述我们可以得知，当提莫两次攻击的时间（t1，t2）差大于等于中毒持续时间（duration），则艾希的第一次中毒时间会持续duration秒，反之当提莫两次攻击的时间差大于等于中毒持续时间（duration），则艾希的第一次中毒时间会持续t1 - t2秒。需要注意的是提莫最后一次攻击后，艾希的中毒状态必定有duration秒。接下来就可以将思路转化为代码了。

编写代码：

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ans = 0;
        int timeSeriesLen = timeSeries.size();
        
        for(int i = 1 ; i < timeSeriesLen ;i++)
        {
            if(timeSeries[i] - timeSeries[i-1] < duration)
            {
                ans += timeSeries[i] - timeSeries[i-1];
            }
            else
            {
                ans += duration;
            }
        }
        // 最后一个攻击后必定中毒duration秒
        ans += duration;

        return ans;
    }
};

题目描述：

思路讲解：
本题同样是使用模拟算法来解决，将题目给的字符串，以从上往下、从左到右进行 Z 字形排列，说是Z字形但是看起来却像N字形。

以下图为例，我们可以创建一个n行len列的二位数组（这里的len是字符串的长度，实际上可能并不需要这么长，大家可以找一个方法来计算出len的大小），按照特定的方法将字符串中放到二维数组中，再一行一行的遍历，组成新的字符串返回即可。但是这样本题的复杂度为：时间复杂度O(n * len) + 空间复杂度O(n * len)，并不是一个很好的解决方案。

我们根据上面的解法进行优化，我们不将字符串放入二维数组中，而是将字符串每个字符的下标放入二维数组进行观察，仔细观察每一行，发现第0行中每一个数相差6也就是2n-2，我们设公差d=2n-2，同样第n-1行每一个数相差的也是2n-2，再看中间几行，以每两个数为一组，第一组的两个下标相加等于公差d，后面每一组下标都是在前一组对应数的基础上加上公差d，通过这里的描述就可以得出下面的结论。

1. 第0行：0 --> 0+d --> 0+2d --> ... -> 0 + xd
2. 第k行：{k，d-k} --> {k+d，d-k+d} --> {k+2d，d-k+2d} -> ... --> {k+xd，d-k+xd}
3. 第n-1行：n-1 --> n-1+d --> n-1+2d --> ... -> n-1 + xd

然后再测试其他行的情况，发现上面的结论同样适用，除了只有n=1的情况，n=1时公差d=0，会导致代码陷入死循环，需要特殊处理。总结出上面的规律后，实际上这个二维数组就不用定义了，可以使用上面这个结论来解决本题。

编写代码：

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1)
            return s;

        string ans;
        int sLen = s.size();
        int d = 2 * numRows - 2;  // 公差，寻找下一个字母需要移动的位置
        // 第一行
        for(int i = 0 ; i < sLen ; i += d)
            ans += s[i];

        for(int i = 1 ; i < numRows - 1;i++)
        {
            for(int num1 = i , num2 = d - i ; num1 < sLen ; num1 +=d , num2 += d)
            {
                ans += s[num1];
                if(num2 < sLen)
                    ans += s[num2];
            }            
        }
        // 最后一行
        for(int i = numRows-1 ; i < sLen ; i += d)
            ans += s[i];

        return ans;
    }
};

题目描述：

思路讲解：
本题的解题思路依旧是模拟，将题目内容转换为下图，那么本题的就可以使用双指针遍历字符串，记录每一段的数字和相同数字的个数并添加到一个新的字符串即可解决本题。

编写代码：

class Solution {
public:
    string countAndSay(int n) {
        string ans("1");
        int left = 0 , right = 0;
        int count = 0; // 记录连续相同数字的个数

        while(--n)
        {
            string tmp;
            while(right < ans.size())
            {
                while(right < ans.size() && ans[left] == ans[right])
                {
                    count++;
                    right++;
                }

                tmp += (count + '0');
                tmp += ans[left];
                count = 0;
                left = right;
            }
            left = right = 0;
            ans = tmp;
        }
        return ans;
    }
};

题目描述：

思路讲解：
本题的解题思路依旧是模拟，本题需要得到模拟字符串中所有蛙鸣所需不同青蛙的最少数目，从上面题目示例的演示可以得到，当一个青蛙叫完后可以继续叫，当没有青蛙处于叫完状态并且还继续需要蛙叫时，就需要增加新的青蛙了。

这里我们定义一个哈希表（这里可以使用数组）来记录处于每种字符下青蛙的个数，接下来对遍历到某个字符时，进行处理的方法进行分类讨论。

1. 当遍历到r、o、a、k时，查看前一个字符下有多少个青蛙，若为非0，则将前一个字符中的一个青蛙放到当前字符下，若为0，说明给出的字符串不是 “croak” 的有效组合，返回-1。
2. 当遍历到c时，查看字符k下有多少个青蛙，字符k下的青蛙个数代表已经叫完青蛙的个数，也就是可以重新开始叫的青蛙的个数，若为非0，则将字符k中的一个青蛙放到字符c中重新开始叫，若为0，则说明需要新的青蛙，引入一个新的青蛙放到字符c中即可。

当字符串遍历完后，再遍历一下哈希表，查看字符c、r、o、a下的青蛙是否为0，为非0，说明给出的字符串不是 “croak” 的有效组合，返回-1，为0说明给出的字符串是 “croak” 的有效组合，返回字符k下的青蛙个数即可。

编写代码：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<int,int> um;
        int count = 0;
        for(int i = 0 ; i < croakOfFrogs.size() ; i++)
        {
            // k为0则说明没有已经叫完的蛙
            // 那么需要有一只新的蛙
            if(croakOfFrogs[i] == 'c')
            {
                if(um['k'] != 0)
                    um['k']--;
                else
                    count++;

                um['c']++;
            }
            // 若前面有蛙叫出了c,那么这里继续叫r
            // 且叫c的蛙要少一个，叫r的蛙多一个
            // 否则则出错返回-1
            else if(croakOfFrogs[i] == 'r')
            {
                if(um['c'] != 0)
                {
                    um['c']--;
                    um['r']++;
                }
                else
                {
                    return -1;
                }
            }
            else if(croakOfFrogs[i] == 'o')
            {
                if(um['r'] != 0)
                {
                    um['r']--;
                    um['o']++;
                }
                else
                {
                    return -1;
                }
            }
            else if(croakOfFrogs[i] == 'a')
            {
                if(um['o'] != 0)
                {
                    um['o']--;
                    um['a']++;
                }
                else
                {
                    return -1;
                }
            }
            else // croakOfFrogs[i] == 'k'
            {
                if(um['a'] != 0)
                {
                    um['a']--;
                    um['k']++;
                }
                else
                {
                    return -1;
                }
            }
        }

        // 叫完后，所有的蛙必须是叫完k
        // 若其他叫声中还有蛙，则说明无效，返回-1
        if(um['c'] || um['r'] || um['o'] || um['a'])
            return -1;
        return count;
    }
};