专题六_模拟_算法详细总结

模拟算法

1.模拟算法流程（一定要在草稿纸上演算一遍流程）

2.把流程转换成代码

1. 替换所有的问号（easy）

解析：

1.暴力：

2.优化：（找规律）

总结：

2. 提莫攻击（easy）

解析：

1.暴力：

2.优化：

3. N 字形变换（medium）

解析：

1）暴力：

2）优化：

总结：

4. 外观数列 (medium)

解析：

1）暴力：

2）优化（小demo）：

总结：

5. 数⻘蛙（medium）

解析：

1）暴力：

2）优化：

总结：

模拟算法

特点就是思路比较简单，特别考验的是如何把里路转换成代码的能力。

1.模拟算法流程（一定要在草稿纸上演算一遍流程）

2.把流程转换成代码

相对来说，模拟题读题就知道是跟着题目的意思一步一步走，但是但凡觉得只是暴力求解时间复杂度和空间复杂度太高了，那么就要转换思想去找规律。模拟题的优化，就是不断的找规律。

1. 替换所有的问号（easy）

就是遍历整个字符串，然后替换里面的所有 '?' ，但是不能存在重复的字符。

解析：

1.暴力：

我开始第一次做的时候，就是创建了心得字符串str，然后每次再遇到不是'?' 的时候就加入，是就改变这个字符，但是在这之前为了保证字符不连续重复，我就用a和b来分别定义字符串中没有出现过的字符，然后用下标奇偶的关系就可以保证a，b交错不连续重复。

class Solution {
public:
    string modifyString(string _s) {
        string s;
        unordered_map<char,int> hash;
        for(auto e : _s) if(e!='?') hash[e]++;
        char a='a',b='a';
        while(hash[a]) a++; hash[a]++;
        while(hash[b]) b++;
        int i=1;
        for(auto e : _s)
        {
            if(e!='?') s+=e;
            else
            {
                if(i%2==0) s+=a;
                else s+=b;
            }
            i++;
        }
        return s;
    }
};

2.优化：（找规律）

线性时间复杂度，而且空间复杂度为O(1)，只在原来的字符串s上进行修改，那么时间复杂度很低O(N)，只需要早原串的基础上进行修改就行。

class Solution {
public:
    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;
    }
};

总结：

像这种模拟题，就要尽可能的想到简便的办法来进行优化，其实很简单。

2. 提莫攻击（easy）

这题题意很简单，就是再中毒时间内，如果继续被攻击，那么就刷新中毒时间，从头开始，那么只需要计算数组每两个数之间的间隙大小是否大于中毒时间即可。

解析：

1.暴力：

想暴力，就是求出每个时间间隔然后再与中毒时间进行比较，小于中毒时间的就只加上这个间隙，否者就加上完整的中毒时间。

2.优化：

根据题目意思就是要看判断再你的下一次攻击时，对方是否再中毒期间，如果是，那么就要进行重置，就只要加上从上一次中毒到这次中毒的间隙，若这个间隙大于或等于中毒时间，那么就只能加上这个中毒时间即可，最后遍历完整个数组后就再加上最后一次的中毒时长就是最后的结果，其实跟暴力没啥区别。

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

3. N 字形变换（medium）

题意就是将字符串按照给出的行数，形成N行大小的Z字形，然后一行一行的读出字符，再进行输出。

解析：

1）暴力：

暴力肯定最开始想到就是按照字符串的下标顺序来进行存入二维数组里面，比如：这个字符串按照下标开始存入二维数组的第一列然后再开始斜边存入，再存入第二列，再次斜边存入等接下来存完整个二维数组，时间复杂度和空间复杂度都达到O(N^2)，但是这题数据量小，可以试试，还是能过的，但是这种办法，我想这就头疼。必须要优化一下

2）优化：

那么说是优化，其实就是找规律，模拟，现根据题目意思进行模拟运算，比如创建一个二维数组来分别进行填入字符串的每一位，但是这一不管是时间复杂度还是空间复杂度都是O(N^2)都太过于复杂
那么就要对他进行优化，对于模拟题，优化都是采用找规律的形式，
1）首先看第一行，每两个数字之间都是由一个公差来决定的，那么就要想办法求出公差，公差就是两倍的行数减去2，或者，就是（二维矩阵行数-1）*2得到公差
2）那么最后一行同样是由一个公差来得到。
3）那么其间的k行[1,n-1]行就都是由两个数，来分别+公差d来组成的，第一个数就是k行的首元素，第二个数就是 d-k 为下标的元素

class Solution {
public:
    string convert(string s, int numRows) {
        int n=s.size();
        if(numRows==1) return s;
        string ret;
        //第一行
        //求公差
        int d=numRows*2-2;
        int prelude=0;
        while(prelude<n) ret+=s[prelude],prelude+=d;

        //中间行
        for(int k=1;k<=numRows-2;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];
            }
        }

        //最后一行
        int k=numRows-1;
        while(k<n) ret+=s[k],k+=d;

        return ret;
    }
};

总结：

对于这种题目有点复杂的模拟，就一定要耐心找到规律，就会变得很简单，重点就是如何把规律变成代码的形式。

4. 外观数列 (medium)

这题相对来说真的比较简单了，只要理解题目意思，真的模拟起来so easy~

题目就是说按照读法生成下一个字符串 "1" -> "1个1" -> "11"

那么"11" -> "2个1" -> "21"等

解析：

1）暴力：

暴力下就是不停的求出每一个次数条件下的字符串，其实优化也大差不差，都是再while里进行。

2）优化（小demo）：

就是要再while外面记录s，每次循环一次们都要记录s，最后返回s。再就是在while里面，要记住每次循环完都要swap(ret,str) ,这样能保证ret每次都是要更新的新字符串，str每次都是上一次的字符串。

模拟这个字符串生成的规律，设置三个字符串，每次都更新str，用双指针left和right来记录重复的字符，并更新到ret里面，然后每次当right走到结尾时候，就把ret赋值给s，并且交换ret跟str，来达到再次更新的目的，最后返回s即可。

class Solution {
public:
    string countAndSay(int _n) {
        string ret;
        string str=to_string(1);
        if(_n==1) return str;
        string s;
        while(--_n)
        {
            int n=str.size();
            for(int left=0,right=0;right<n;right++)
            {
                if(str[left]!=str[right])
                {
                    ret+=to_string(right-left);
                    ret+=str[left];
                    left=right;
                }
                if(right==n-1)
                {
                    ret+=to_string(right-left+1);
                    ret+=str[left];
                }
            }
            s=ret;
            swap(str,ret);
            ret.clear();
        }
        return s;
    }
};

总结：

有些比较简单的模拟，真的一眼就能只知道怎么写，可能这就是提升吧。

5. 数⻘蛙（medium）

题目意思就是用最少的青蛙喊出最长的字符串，并且要满足"croak" 并且顺序要正确才行。

解析：

1）暴力：

这题如果想不上优化，那还真有点暴力，5个else if() 来判断条件，判断前面是否有字符存在满足条件是我当前字符的前一个，如果是就继续，不是就直接返回-1

2）优化：

首先就是解决5个else if()的问题，可以用一个unordered_map<char,int> index;来将字符串装起来，将字符串的字符与下标进行映射，然后创建一个hash表，这个hash表专门装入五个字符“蛙叫”

hash表，来记录最少青蛙的只数。

eg:

我现在读到的字符是ch=‘o’，那么我就要判断前面的字符‘r’是否存在过，如果现在存在，就证明这一只青蛙可以喊道我这个‘o’，否则就说明是错误的，返回-1

又比如：我已经有青蛙喊完了一遍，又碰到一个字符是ch，此时我的hash['k']==1，就说明有一次青蛙已经喊完了，但是，有碰到ch=='c' ，又要从头开始叫，那么就可以让这只已经叫过的青蛙重叫，就不会增加青蛙只数。

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