模拟练习题

模拟，顾名思义，这种题一般侧重于直接实现题目给的条件，即题目给什么，就实现什么。

替换所有的问号

1576. 替换所有的问号 - 力扣（LeetCode）

思路

从头到尾遍历字符串，如果看到问号，就对26个字母进行循环遍历，再排除里面不需要的字母即可。

代码

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

提莫攻击 

495. 提莫攻击 - 力扣（LeetCode）

思路

以如图为例，4-1 > duration ,两数字中间中毒状态即为duration

以如图为例，3-1<duration,两数字间中毒状态即为两数之间的距离3-1=2了

需要注意的是，最后一个元素需要再加一个duration，因为没有后面的间隔了。

代码

int findPoisonedDuration(vector<int>& timeSeries, int duration)
{
    int sum = 0, n = timeSeries.size(), dec = 0;
    for (int i = 1; i < n; i++)
    {
        dec = timeSeries[i] - timeSeries[i - 1];
        if (dec >= duration) sum += duration;
        else sum += dec;
    }
    return sum + duration;
}

Z字形变换 

6. Z 字形变换 - 力扣（LeetCode）

思路

我们可以将z字形的数画进一个矩阵，观察矩阵可得到，每一数列之间的公差d是2num-2(num是行数)。所以我们可以将每一行的数表示出来.

第一行和最后一行即为ret += s[i].

对于中间的num- 2行, 每一行一次循环有两个数，一个是k，另一个是t-k.

代码

string convert(string s, int numRows)
{
    //处理numRows等于1
    if (numRows == 1) return s;
    string ret;
    int d = 2 * numRows - 2, n = s.size();
    //第一行
    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 < 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;
}

外观数列

38. 外观数列 - 力扣（LeetCode）

思路

双指针，right碰到不相同的停止，相同的向右走，再将距离用to_string函数转化为字符加上左指针指向的字符，最后再将left指针跳到right指针即可。

代码

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

数青蛙

1419. 数青蛙 - 力扣（LeetCode）

思路

先用一个数组代替哈希表记录字符串t（t为青蛙的叫声这个字符串）中的每个字符，并且我们将分两种情况讨论：

（里面的数字1移动）（即前面--，后面++）

出现c，看最后一个字符k是否为0，如果不为0，说明已经至少出现了一只青蛙，如果为0，hash[0]++即可，代表已经出现了一个c,哈希表将其记录。

出现其他字符，如果前面存在其在哈希表顺序中的前面的字符，那么数字1向后移动。

对于任何一个在最后一个字符前面的位置，如果其值不为0，则直接返回-1即可，因为这代表叫声在这里面断了。

代码

int minNumberOfFrogs(string croakOfFrogs)
{
    string t = "croak";
    int n = t.size();
    vector<int> hash(n);//每一位代表t中的每一个字母，其值即为字符出现次数

    unordered_map<char, int> index;//x字符对应下标
    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];
}