模拟算法（模拟算法 == 依葫芦画瓢）万字

模拟算法

• 基本思想
• 引入算法题
• • 替换所有的问号
  • 提莫攻击
  • Z字形变换
  • 外观数列
  • 数青蛙

    基本思想

      模拟算法 == 依葫芦画瓢解题思维要么通俗易懂，要么就是找规律，主要难度在于将思路转换为代码。

    • 特点：相对于其他算法思维，思路比较简单（没有很多的弯弯绕绕，考察的是代码能力）。
    • 大致做题流程
      • 模拟算法流程（一定要在演草纸上过一遍 - 容易忽略细节）
      • 把流程转换为代码

        引入算法题

        替换所有的问号

        链接:https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

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

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

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

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

        示例 1：

         输入：s = “?zs”

         输出："azs"

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

        题目分析：

          题目讲的很清楚，就是替换 '?' ，使其变为小写字母，并需保证无连续重复字符。

        解题：

        • 1、模拟算法流程

          容易忽略细节：最左端与最右端两种情况。

        • 2、把流程转换为代码

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

          提莫攻击

          链接：https://leetcode.cn/problems/teemo-attacking/description/

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

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

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

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

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

          示例 2：

           输入：timeSeries = [1,2], duration = 2

           输出：3

           解释：提莫攻击对艾希的影响如下：

            第 1 秒：提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。

            第 2 秒：提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。

            艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。

          题目分析：

            题目讲的很清楚，就是计算中毒的有效时间，但是中毒是有时效的，并且时间可能重叠。

          解题：

          • 1、模拟算法流程

            容易忽略细节：两次投毒时间之间的时间与，中毒有效时间duration的关系。

          • 2、把流程转换为代码

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

            Z字形变换

            链接：https://leetcode.cn/problems/zigzag-conversion/

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

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

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

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

                string convert(string s, int numRows);

            示例 1：

             输入：s = “PAYPALISHIRING”, numRows = 3

             输出：“PAHNAPLSIIGYIR”

            题目分析：

              题目讲的很清楚，从上往下、从左到右进行Z 字形排列。之后，从左往右逐行读取。

            解题：

            • 1、模拟算法流程

                最直接暴力的方式就是：利用二维数组进行解题 - 可想而知空间复杂度与时间复杂度都是极高的！

              99.99%的模拟题的优化方式都是找规律。

                以此可以发现一个规律。

              • 2、把流程转换为代码

                class Solution {public:
                    string convert(string s, int numRows) { if(numRows == 1)
                            return s;
                        int size = s.size();
                        int d = 2 * numRows - 2;
                        string ret;
                        // 第一行
                        for(int i = 0; i < size; i += d)
                        { ret += s[i];
                        }
                        // (1, numRows - 1)行
                        for(int k = 1; k < numRows - 1; k++)
                        { for(int i = k, j = d - k; i < size; i += d, j += d)
                            { if(i < size)
                                    ret += s[i];
                                if(j < size)
                                    ret += s[j];
                            }
                        }
                        // 第numRows - 1行
                        for(int i = numRows - 1; i < size; i += d)
                        { ret += s[i];
                        }
                        return ret;
                    }
                };
                

                外观数列

                链接:https://leetcode.cn/problems/count-and-say/description/

                  给定一个正整数 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"

                   解释：这是一个基本样例。

                  题目分析：

                    题目讲的很清楚，从上往下、从左到右下一行是上一行的元素描述。

                  解题：

                  • 1、模拟算法流程

                      该题通过寻找发现并无任何规律，是模拟 + 双指针的方法。

                    • 模拟： 依葫芦画瓢，对上一行数据进行描述。
                    • 双指针： 通过分三块，分为[已被记录区域]，[等待记录区域]，[等得被记录区域]。
                    • 2、把流程转换为代码

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

                      数青蛙

                      链接:https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/

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

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

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

                      示例 1：

                       输入：croakOfFrogs = “croakcroak”

                       输出：1

                       解释：一只青蛙 “呱呱” 两次

                      题目分析：

                        需要按序组成以此青蛙叫"croak"，才算一只青蛙，但是一只叫完的青蛙可以再接着再"croak"一次，所以青蛙的数量不算增加！

                      解题：

                      • 1、模拟算法流程

                        需要使用到 哈希

                          当遇到 ‘r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1 ；

                          当遇到 ‘c’ 这个字符的时候，我们去看看 ‘k’ 这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 ‘c’ 这个字符；如果没有的话，就重新搞⼀个青蛙。

                        总结：

                        • r, o, a, k：找一下前驱字符，是否在哈希表中存在？
                          • 存在：前驱--，当前++。
                          • 不存在：返回-1。
                          • c：找最后一个字符，是否在哈希表中存在？
                            • 存在：最后一个--，当前++。
                            • 不存在：当前++。
                            • 2、把流程转换为代码

                              class Solution {public:
                                  int minNumberOfFrogs(string croakOfFrogs) { vector hash(5, 0);
                                      string tmp = "croak";
                                      int n = tmp.size();
                                      unordered_map index; //[x, x这个字符对应的下标]
                                      for(int i = 0; i < n; i++)
                                          index[tmp[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[4];
                                  }
                              };