【优选算法】Simulation-Phoenix：模拟算法的重生涅槃

概念解析

🚩什么是模拟算法？

简单来说就是照葫芦画瓢，题目说啥就照着写代码就行，所以很考察代码能力

替换所有的问号

✏️题目描述：

✏️示例：

传送门：替换所有的问号

题解:

这题很简单，显然是先遍历一遍数组，然后在遍历的时候，如果遇到？就替换为与该位置前后都不相同的数，所以也要对要替换的数遍历一遍，直到发现合适的数

💻细节问题：

注意边界情况，没有两个相邻的数

💻代码实现：

#include <iostream>
#include <vector>
using namespace std;

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

提莫攻击

✏️题目描述：

✏️示例：

传送门：提莫攻击

题解:

做模拟算法题的精髓就是要画图，只有图画明白了，才能找到规律，而不是凭空想象

所以根据规律发现相邻两数之差是突破点，如果相邻两数之差大于duration，那么不用重置中毒时间；如果相邻两数之差小于duration，那么要重置中毒时间

💻代码实现：

#include <iostream>
#include <vector>
using namespace std;

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

Z字形变换

✏️题目描述：

✏️示例：

传送门：Z字形变换

题解:

本题的意思是要你根据题目给出的Z字形字符串，将其从上到下，从左至右的方式以一个新字符串的方式返回，显然这是一个找规律性极强的题目，所以画图！画图！画图！

💻第一步：

首先我们将每个数的索引按照Z字形填入，我们是从第一行开始录入，所以可以发现第一行和最后一行都是一个等差数列，然后发现规律，公差是0~6之间元素的个数，所以得出d=2n-2

💻第二步：

接下来处理中间的行数，发现如图的1 ~ 7 ~ 13，5 ~ 11 ~ 17也是以6为公差，只不过是两个数两个数的差，所以得出规律（k，d-k）

💻细节问题：

注意for循环的判断条件为i < n || j < k，而不是&&，因为当一个越界之后，另一个可能还没越界判断完

💻代码实现：

#include <iostream>
#include <vector>
using namespace std;

class Solution 
{
public:
    string convert(string s, int numRows)
    {
        if (numRows == 1)
        {
            return s;
        }
        string ret;
        int n = s.size();
        int d = 2 * numRows - 2;
        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 < k; 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;
    }
};

外观序列

✏️题目描述：

✏️示例：

传送门：外观序列

题解:

其实题目意思就是对上一行的序列进行解释，比如第三行为21，那么第四行的意思就是一个2一个1

💻细节问题：

所以很明显这题要用双指针解决，因为要持续向后查找有几个相同的，直到不同为止

left和right都从0开始，然后right向后移动，直到该位置和前一个位置不相同，然后记录长度和数字，直接让left=right，开始下一段

💻代码实现：

#include <iostream>
#include <string>
using namespace std;

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

数青蛙

✏️题目描述：

✏️示例：

传送门：数青蛙

题解:

要理解本题题意，就是一只青蛙要完整叫完croak，如果一只青蛙没叫完，那么就需要另一只青蛙来发出叫声

💻第一步：

首先，以如图所示为例子，第一个c，计入该位置为1，接下来到r，该位置变为1，上一个位置变为0，可以理解为一个1一直在移动，表示这个叫声遍历到哪里了，直到遍历到k为止

💻第二步：

注意在遍历过程中注意要像图中分类，对于字符c，若k位置不为0，那么表示有青蛙闲置，那么之前叫完的青蛙就可以再次叫；对于其他字符，要找该字符的前一个字符符不符合croak的顺序和字符，若不符合字符，直接返回-1

💻细节问题：

注意处理完所有字符时，要判断一下是否还有没叫完的叫声

💻代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
using namespace std;

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

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！