【算法】模拟

个人主页 ： zxctscl

如有转载请先通知

题目

• 前言
• 1. 1576. 替换所有的问号
• • 1.1 分析
  • 1.2 代码
  • 2. 495. 提莫攻击
  • • 2.1 分析
    • 2.2 代码
    • 3. 6. Z 字形变换
    • • 3.1 分析
      • 3.2 代码
      • 4. 38. 外观数列
      • • 4.1 分析
        • 4.2 代码
        • 5. 1419. 数青蛙
        • • 5.1 分析
          • 5.2 代码

            前言

            模拟算法就是根据题目所给的照葫芦画瓢。

            考察的是代码能力。

            步骤：1.模拟算法流程（一定得自己先过一遍流程）

            2.把流程转化为代码

            1. 1576. 替换所有的问号

            1.1 分析

            题目的意思很显而易见，遍历一遍字符串如果是？，就找一个小写字母来替换它，而它的前面一个字符和它不相同，它后面一个字符和它也不能相同。得处理一下边界情况，如果?在开始位置，就不用比较它前面位置，比较后面那个位置就行。同样在结尾位置的话，就比较前面的一个字符相不相等就行。

            1.2 代码

            class Solution {public:
                string modifyString(string s) { int n =s.size();
                    for(int i=0;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;
                }
            };
            

            2. 495. 提莫攻击

            2.1 分析

            当前这个位置减去前面一个位置的差，如果大于等于中毒时间，那么就全部加上中毒时间；如果差小于中毒时间，那么就是加上这个差值。得注意最后一个值没有判断，最后的值还得再加上一个中毒时间才行。

            2.2 代码

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

            3. 6. Z 字形变换

            3.1 分析

            一、题目解析

            按题目所述，像下面图片这样的就是Z字型。

            二、算法原理

            要想得到最后为Z字型输出的字符串，可以直接开一个矩阵直接先把字符一个一个放进去再一行一行输出。

            但还可以用另外一个方式，就是找规律。

            举个例子：把字符的下标都写到矩阵里面，就发现了规律。

            第一行每间隔2n-2就出现一次，为了方便描述，就把间隔叫做公差d=2n-2,第一行只需要输出每次个d个数的字符就可以。

            最后一行和第一行一样，也是间隔d个字符数。

            来看中间几行，1和5到11和13中间间隔的也是d个数，那么直接一次性输出两个就行。

            3.2 代码

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

            4. 38. 外观数列

            4.1 分析

            模拟题目的意思

            找到连续相同的字符解释一下，可以利用双指针来进行，如果两个指针指向的位置字符相同就一直走，不一样就停下来，中间元素的个数就是指针的差值；然后让左边指针指向右边指针的位置，再重复上面的操作就可以了。

            4.2 代码

            class Solution {public:
                string countAndSay(int n) { string ret="1";
                    for(int i=1;i string tmp;
                        int len=ret.size();
                        for(int left=0,right=0;right while(right 
            5. 1419. 数青蛙
             
            5.1 分析
             
            模拟
            用一个哈希表时刻记录每一次字符出现的情况。如果青蛙叫了c时候，那么就用1记录一下有一个青蛙叫了c字符;遍历到r的时候看看前面有没有青蛙叫了c,有就让这个青蛙继续叫r,在哈希表了让c减减，r加加就行。当又遇到一个c时候，表示又有一个青蛙过来，然后继续遍历到o的时候，要看看哈希表前面有没有青蛙叫过r，有的话r减减，o加加，继续往后重复直到k。
            但是题目要求青蛙数目最少，这里k中有数的时候，此时又有c时候，就从k里面搬一个青蛙来从c开始叫，k减减，c加加，重复上面过程。k里面的数存的就刚好是结果。
            但是如果除了k里面还有非0元素，那么就返回-1。
             
            如果在在哈希表中，在r位置之前没有c那么就返回-1：
             
            总结，都得找前驱字符，如果前驱字符有，那么前驱字符减减，当前字符加加；没有就返回-1。
            最后一个字符看看它是不是在哈希表里面存在，存在就是最后一个字符减减，当前字符加加；不存在就当前字符加加。
             
            5.2 代码
             
            class Solution
            {public:
                int minNumberOfFrogs(string croakOfFrogs)
                { string t = "croak";
                    int n = t.size();
                    vector hash(n); // ⽤数组来模拟哈希表
                    unordered_map index; //[x, 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];
                }
            };