Offer必备算法05_模拟_五道力扣OJ题详解（由易到难）

目录

模拟算法原理

①力扣1576. 替换所有的问号

解析代码

②力扣495. 提莫攻击

解析代码

③力扣6. Z 字形变换

解析代码

④力扣38. 外观数列

解析代码

⑤力扣1419. 数青蛙

解析代码1

解析代码2

本篇完。

模拟算法原理

        模拟算法是一种常用的计算机算法，它模拟了实际问题的运行过程，并通过数学模型来预测结果。模拟算法可以应用于各个领域，例如物理、化学、生物、计算机网络等等。

        模拟算法，用一句老话说，就是“照着葫芦画瓢”，官方化的诠释则是：根据题目表述进行筛选提取关键要素，按需求书写代码解决实际问题。

        模拟算法一般都是一些很基础的题目，一些大佬眼中，模拟题就是所谓的“水题”，不太需要动脑子，只要按照题目要求来就好。但是模拟题也分难易，对于一些特困难的模拟题，哪怕是大佬，也很容易做错。大部分模拟题的优化思路都是找规律。

①力扣1576. 替换所有的问号

1576. 替换所有的问号

难度 简单

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何 连续重复 的字符。

注意：你 不能 修改非 '?' 字符。

题目测试用例保证 除 '?' 字符 之外，不存在连续重复的字符。

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 "zzs" 中有连续重复的两个 'z' 。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。

提示：

• 1 <= s.length <= 100

• s 仅包含小写英文字母和 '?' 字符

class Solution {
public:
    string modifyString(string s) {

    }
};

解析代码

思路就是遍历字符串找问号，找到后依次比较前一个字母和后一个字母，都不一样就替换问号。

class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for(int i = 0; i < n; ++i)
        {
            if(s[i] == '?')
            {
                for(char c = 'a'; c < 'z'; ++c)
                {
                    if((i == 0 || s[i-1] != c) && (i == n-1 || s[i+1] != c))
                    {   // 或就是i==0就不用判断后面条件了
                        s[i] = c;
                    }
                }
            }
        }
        return s;
    }
};

②力扣495. 提莫攻击

495. 提莫攻击

难度 简单

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。

正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。

给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。

返回艾希处于中毒状态的 总 秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。
艾希在第 1、2、4、5 秒处于中毒状态，所以总中毒秒数是 4 。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

提示：

• 1 <= timeSeries.length <= 10^4
• 0 <= timeSeries[i], duration <= 10^7
• timeSeries 按 非递减 顺序排列

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {

    }
};

解析代码

（十年老玩家最先想到提莫没学E怎么让别人中毒/不是）

        当上次中毒已经结束了，那么上次「中毒」维持的时间就是 duration，如果上次中毒还没有结束，由于中毒状态将会重置，所以上次「中毒」维持的时间 = 当前中毒时间 - 上次中毒时间。

一个for循环就秒了：

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ret = 0;
        for (int i = 1; i < timeSeries.size(); ++i) 
        {
            ret += min(duration, timeSeries[i] - timeSeries[i - 1]);
        }
        return ret + duration; // 最后一次中毒持续时间加上
    }
};

③力扣6. Z 字形变换

6. Z 字形变换

难度 中等

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

class Solution {
public:
    string convert(string s, int numRows) {

    }
};

解析代码

暴力解法就是开一个n*len的二维数组，填输出然后遍历，这样时间空间复杂度都是O（N^2），

绝大部分模拟题的优化方法都是找规律，先画出下面第一个图：（数字代表数组下标）

        通过第一个图发现每隔竖着的一列都能用一个公差d来计算，公差d = 2 * numRows - 2，比如第一个图的公差d = 2 * 4 - 2 = 6，然后就发现完整竖列中间的下标和左边竖列下标加起来刚好等于d，第k行一次遍历两个下标，最后一行和第一行类似，，此时就能通过直接遍历数组的下标得到要返回的字符串：

首先遍历第一行（设下标为i，要返回的字符串为ret，原字符串为s）：ret += s[i + d];

        然后遍历中间行（设中间行为k，k>=1，k<=numRows -1，要避免数组越界）：

ret += s[k+i + d]; ret += s[d-k + d];（k++，i += d，j = k-d，j+= d）

最后遍历最后一行：ret += s[numRows-1 + i];

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) // 处理边界
            return s;

        string ret;
        int n = s.size(), 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 < n; i += d, j += d)
            {                    // i < n 和 j < n都要加到ret里
                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. 外观数列

38. 外观数列

难度 中等

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

• countAndSay(1) = "1"
• countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
第一项是数字 1 
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 "3322251" 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

• 1 <= n <= 30

class Solution {
public:
    string countAndSay(int n) {

    }
};

解析代码

就是一道需要用到双指针的模拟题，考验代码能力

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1", tmp = "";
        int cnt = n;
        while(--cnt) // 解释n-1次
        {
            int len = ret.size();
            tmp = "";
            for(int left = 0, right = 0; right < len; left = right)
            {
                while(right < len && ret[left] == ret[right])
                {   // 双指针计算个数
                    ++right;
                }
                tmp += to_string(right - left);
                tmp += ret[left];
            }
            ret = tmp;
        }
        return ret;
    }
};

⑤力扣1419. 数青蛙

1419. 数青蛙

难度 中等

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

提示：

• 1 <= croakOfFrogs.length <= 10^5
• 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

解析代码1

五个if：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        // int c = 0, r = 0, o = 0, a = 0, k = 0;
        vector<int> arr(6, 0); // 用下标1到5分别映射五个字母
        for(auto& e : croakOfFrogs)
        {
            if(e == 'c')
            {
                if(arr[5] > 0)
                    --arr[5];
                ++arr[1];
            }
            if(e == 'r')
            {
                if(arr[1] > 0)
                    --arr[1];
                else
                    return -1;
                ++arr[2];
            }
            if(e == 'o')
            {
                if(arr[2] > 0)
                    --arr[2];
                else return -1;
                ++arr[3];
            }
            if(e == 'a')
            {
                if(arr[3] > 0)
                    --arr[3];
                else  return -1;
                ++arr[4];
            }
            if(e == 'k')
            {
                if(arr[4] > 0)
                    --arr[4];
                else return -1;
                ++arr[5];
            }
        }
        if(arr[1] > 0 || arr[5] == 0)
            return -1;
        return arr[5];
    }
};

解析代码2

用哈希表：

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string str = "croak";
        int n = str.size();
        vector<int> arr(n, 0); // 数组模拟哈希表
        unordered_map<char, int> index; //映射每个字符的下标
        for(int i = 0; i < n; ++i)
            index[str[i]] = i;

        for(auto& e : croakOfFrogs)
        {
            if(e == 'c')
            {
                if(arr[n-1] != 0)
                    --arr[n-1];
                ++arr[0];
            }
            else
            {
                if(arr[index[e] - 1] == 0)
                    return -1;
                --arr[index[e] - 1];
                ++arr[index[e]];
            }
        }
        for(int i = 0; i < n-1; ++i)
        {
            if(arr[i] != 0)
                return -1;
        }
        return arr[n-1];
    }
};

本篇完。

下一部分是关于位运算的OJ。文章来源地址https://www.toymoban.com/news/detail-836860.html

到了这里，关于Offer必备算法05_模拟_五道力扣OJ题详解（由易到难）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！