系统学习算法：专题六 模拟

模拟算法其实也不叫算法，这类题就是题目告诉你具体流程是怎么样的，让你用代码来实现，思路上不怎么难，主要考察代码能力，将想转化成做，模拟题目的操作步骤，这就是模拟

题目一：

思路：

题意很简单，就是让这个字符串中不能出现连续重复的字符，其中我们要做的就是替换所有的问号来达到前面这个要求

步骤其实也很简单，就是遍历整个字符串，如果出现了问号，就进行替换，这时有四种情况可以讨论

1.有前驱有后继，那么此时问号要替换的字符就不能等于前驱和后继，依次用a~z来比较找合适的即可，即 " abc?def " 这种情况

2.有前驱但没后继，那么此时问号要替换的字符就不能等于前驱即可，依次用a~z来比较找合适的，即 " abc? " 这种情况

3.有后继但没前驱，那么此时问号要替换的字符就不能等于后继即可，依次用a~z来比较找合适的，即 " ?abc " 这种情况

4.没前驱也没后继，其实就是" ? "这种情况，那么随便找一个字符替换就行，没有限制条件

那么接下来就将这个过程用代码进行模拟

代码：

class Solution {
    public String modifyString(String s) {
        //转化为字符数组，方便操作
        char[] ch=s.toCharArray();
        //用来替换的a~z
        String str="abcdefghigklmnopqrstuvwxyz";
        //遍历字符数组
        for(int i=0;i<ch.length;i++){
            //如果出现问号
            if(ch[i]=='?'){
                //有前驱有后继
                if((i-1>=0)&&(i+1<ch.length)){
                    for(int j=0;j<26;j++){//从a~z去找
                        if(str.charAt(j)!=ch[i-1]&&str.charAt(j)!=ch[i+1]){//符合条件就替换
                            ch[i]=str.charAt(j);
                            break;
                        }
                    }
                }else if(i+1<ch.length){//有后继没前驱
                    for(int j=0;j<26;j++){//从a~z去找
                        if(str.charAt(j)!=ch[i+1]){//符合条件就替换
                            ch[i]=str.charAt(j);
                            break;
                        }
                    }
                }else if(i-1>=0){//有前驱没后继
                    for(int j=0;j<26;j++){//从a~z去找
                        if(str.charAt(j)!=ch[i-1]){//符合条件就替换
                            ch[i]=str.charAt(j);
                            break;
                        }
                    }
                }else{//没前驱没后继
                    ch[i]='a';//随便替换一个即可
                }
            }
        }
        //返回替换后的字符串
        return new String(ch);
    }

题目二：

思路：

 题意很简单，就是算中毒时间之和，中毒时间只有两种情况

第一种：在中毒结束前没有新的攻击，则中毒时间全部加上

第二种：在中毒结束前受到新的攻击，则中毒时间加上两次攻击时间的差值

其中最后一次攻击肯定是第一种情况，所以只用遍历到数组倒数第二位即可

代码：

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        //中毒时间之和
        int sum=0;
        //遍历到倒数第二个数
        for(int i=0;i<timeSeries.length-1;i++){
            //如果中毒状态没重置，全部执行完
            if(timeSeries[i]+duration-1<timeSeries[i+1]){
                sum+=duration;
            }else if(timeSeries[i]+duration-1>=timeSeries[i+1]){//有新的攻击，重置
                sum+=timeSeries[i+1]-timeSeries[i];//加上两次攻击时间差值
            }
        }
        //最后一次攻击中毒时间肯定是全部执行完
        return sum+duration;
    }
}

题目三：

思路:

就是按照题目要求，将原字符串按照Z字排列，然后返回新的字符串

这种变换的题有行有列，那么就需要二维矩阵来方便操作，因此第一步根据题目要求，大致算出矩阵所需的行数和列数，这道题的行数为numRows，列数需要根据周期性来计算，但是太麻烦了，我们直接就用字符串的长度作为列数，保证够用只是会浪费

然后我们就开始按照要求填数就行了，从(0，0)开始填，一开始是从上到下，然后是斜着的从左下往右上，这两步为一个周期，循环下去就行了

对此画图，因为我们不关心真实构成字符串的各个字符，只关心下标走到字符串的哪里了，所以用012来代表对应的字符

很容易找到规律，竖着i+1，j不变，斜着i-1，j+1

根据规律我们就可以将字符串的字符全部填入矩阵

接下来就是遍历二维数组，如果是大小写字母，逗号或句号就拼接到要返回的字符串里

这就是比较简单的模拟思路

代码1：

class Solution {
    public String convert(String s, int numRows) {
        //如果行数为1,那么直接返回
        if(numRows==1){
            return s;
        }
        //构建矩阵
        char[][] ch=new char[numRows][s.length()];
        //循环
        for(int i=0,j=0,index=0;index<s.length();){
            //竖着
            while(i<numRows&&index<s.length()){
                ch[i++][j]=s.charAt(index++);
            }
            //调整i的位置
            i--;
            //斜着
            while(i>1&&j<s.length()-1&&index<s.length()){
                ch[--i][++j]=s.charAt(index++);
            }
            //调整ij的位置
            i--;
            j++;
        }
        //要返回的新字符串
        String str=new String();
        //遍历矩阵
        for(int i=0;i<numRows;i++){
            for(int j=0;j<s.length();j++){
                //如果有填入的字符就拼接到字符串
                if((ch[i][j]>='a'&&ch[i][j]<='z')||(ch[i][j]>='A'&&ch[i][j]<='Z')
                ||ch[i][j]==','||ch[i][j]=='.'){
                    str+=ch[i][j];
                }
            }
        }
        //返回字符串
        return str;
    }
}

其中有个特例需要解决，那就是行数为1，此时原字符串就是答案，直接返回就行

但是这种方法时间复杂度和空间复杂度都很高

直接就来到末尾了 ，因此我们就需要优化

而模拟算法的题想要优化，基本都是找规律，然后根据规律直接找到答案

有了前面的分析步骤，我们就思考能不能得到下标的规律

 以这个为例，我们可以发现第一行和最后一行的排布一样，其中第一行的第一个数为0，第二个数为6，我们就来思考什么样的公式能得到0，6，12

先找到公差ｄ＝6，6又是怎么来到，因为前面0～5在前三列，5假设也移到第2列，就相当于有两列，其中第二列缺2个，因此ｄ＝2ｎ－2，ｎ为行数

这个例子符合了，不保证其他例子符合，所以要再举个例，假设为3行，会发现第一行是0，4，

2ｎ－2＝4，公式正确

然后就是中间的行，可以将两个数看作一对，1，5一对，7，11一对，1到7为公差ｄ＝6，5到11为公差ｄ＝6，依次类推

最后一行和第一行的规律一样，接下来就将规律转化成代码即可

代码2：

class Solution {
    public String convert(String s, int numRows) {
        //特殊处理一下
        if(numRows==1){
            return s;
        }
        //stringbuffer的append比string的+=快很多，且线程安全
        StringBuffer ret=new StringBuffer();
        //求出公差
        int d=2*numRows-2;
        //处理第一行
        for(int i=0;i<s.length();i+=d){
            ret.append(s.charAt(i));
        }
        //处理第2到k行
        for(int k=1;k<numRows-1;k++){
            //添加第k行的所有元素
            for(int i=k,j=d-k;i<s.length()||j<s.length();i+=d,j+=d){
                if(i<s.length()){
                    ret.append(s.charAt(i));
                }
                if(j<s.length()){
                    ret.append(s.charAt(j));
                }
            }
        }
        //处理最后一行
        for(int i=numRows-1;i<s.length();i+=d){
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
}

内存上根本没有创建矩阵，时间上复杂度也很低 

题目四：

思路：

题意就是输入一个整数n代表递归次数，然后通过递归公式，返回经过n次递归后的字符串结果

其中递归公式的操作步骤就是将一个字符串化为“个数”+“字符”

比如题目举例的3322251

就是遍历该字符串

33为2个“3”，所以返回23

222为3个“2”，所以返回32

5为1个“5”，所以返回15

1为1个“1”，所以返回11

所以最后要返回的字符串为23321511

那么接下来的关键就是如何用代码模拟上述操作

其中递归结束的条件为n==1，然后操作就是遍历字符串，然后用一个变量count记录该字符有多少个，初始值为1，因为被遍历到那么至少为1个，接下来就循环往后一个字符进行比较，如果相同就count++，下标也往后移动，直到出现不同，这时就将个数和字符拼接到字符串，然后继续扫描后面的字符串，最后返回这次递归的字符串

代码1（递归）：

class Solution {
    //递归方法
    public String dg(int n){
        //递归结束条件
        if(n==1){
            return "1";
        }else{//递归
            //拿到上一次递归的结果
            String s = dg(n-1);
            StringBuffer str=new StringBuffer();
            //扫描字符串
            for(int i=0;i<s.length();i++){
                //count代表个数
                int count=1;
                //扫描有多少个相同的字符
                while(i<s.length()-1 && s.charAt(i)==s.charAt(i+1)){
                    count++;
                    i++;
                }
                //拼接个数+字符
                str.append(Integer.toString(count));
                str.append(s.charAt(i));
            }
            //返回这次递归的结果
            return str.toString();
        }
    }
    public String countAndSay(int n) {
        //调用递归方法
        return dg(n);
    }
}

递归是从后往前递，然后再从前往后归，还有一个与它相似的方法，就是迭代，即从前往后迭代，通常通过循环就可以解决

思路也是一样的就不多赘述了，上面的count记录个数可以改用双指针来计算，就当多练习一下其他算法

代码2（迭代）：

class Solution {
    public String countAndSay(int n) {
        //初始为"1"
        String ret = "1";
        //第一层循环代表第i次迭代
        for (int i = 2; i <= n; i++) {
            //记录这一次迭代的字符串结果
            StringBuffer str = new StringBuffer();
            //这一层循环代表遍历整一个字符串
            for (int left = 0, right = 0; right < ret.length();) {
                //这一层循环代表扫描该字符出现了多少个
                while (right < ret.length() && ret.charAt(left) == ret.charAt(right)) {
                    right++;
                }
                //拼接个数+字符
                str.append(Integer.toString(right - left));
                str.append(ret.charAt(left));
                //换到下一个字符
                left = right;
            }
            //更新这一次迭代结果
            ret=str.toString();
        }
        //返回迭代n次的结果
        return ret;
    }
}

题目五：

 思路：

题意也比较好理解，就是要判断是否是有效组合，如果是则返回至少需要多少只青蛙，不是则返回-1

这个不能简单的数出现了多少次croak就返回有多少只青蛙，因为一只青蛙叫完还可以继续叫，比如示例1

可以用哈希表来记录当前叫声的出现次数，判断是否是有效组合，只用看看该字符的前驱有没有出现，如果没有出现就无效，返回-1，如果有出现就前驱次数--，当前次数++，如此循环

叫到k的时候代表有一只青蛙叫完了，就变为闲置状态，而这时如果又遍历到了c，表示又有一次新的叫声，那么此时就可以让闲置的青蛙去叫，此时k--，c++，如果k为0，说明没有闲置的青蛙，是一只新的青蛙来叫了，c++就行

最后如果c~a还有次数，则说明不是有效组合，因为如果是有效的话，最后叫声全部叫完，都应该堆积在k位置

代码1：

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        //创建哈希表
        HashMap<Character,Integer> map=new HashMap<>();
        char[] arr=croakOfFrogs.toCharArray();
        //遍历字符串
        for(int i=0;i<arr.length;i++){
            //如果为一开始的叫声
            if(arr[i]=='c'){
                //如果没有青蛙处于休闲状态
                if(map.getOrDefault('k',0)==0){
                    //又有新的青蛙加入
                    map.put('c',map.getOrDefault('c',0)+1);
                }else{//有青蛙闲置，再次利用
                    map.put('k',map.get('k')-1);
                    map.put('c',map.getOrDefault('c',0)+1);
                }
            }else if(arr[i]=='r'){
                //如果前面没有对应的叫声，则不是有效组合
                if(map.getOrDefault('c',0)==0){
                    return -1;
                }else{//前面对应叫声减1，来到当前叫声
                    map.put('c',map.get('c')-1);
                    map.put('r',map.getOrDefault('r',0)+1);
                }
            }else if(arr[i]=='o'){//全部类似上述操作，复制修改
                if(map.getOrDefault('r',0)==0){
                    return -1;
                }else{
                    map.put('r',map.get('r')-1);
                    map.put('o',map.getOrDefault('o',0)+1);
                }
            }else if(arr[i]=='a'){
                if(map.getOrDefault('o',0)==0){
                    return -1;
                }else{
                    map.put('o',map.get('o')-1);
                    map.put('a',map.getOrDefault('a',0)+1);
                }
            }else{
                if(map.getOrDefault('a',0)==0){
                    return -1;
                }else{
                    map.put('a',map.get('a')-1);
                    map.put('k',map.getOrDefault('k',0)+1);
                }
            }
        }
        //如果还有剩余叫声没叫完（叫了一半）
        if(map.getOrDefault('c',0)!=0||map.getOrDefault('r',0)!=0||
        map.getOrDefault('o',0)!=0||map.getOrDefault('a',0)!=0){
            return -1;
        }else{//返回至少有多少只青蛙
            return map.getOrDefault('k',0);
        }
    }
}

虽然这么看比较清晰明了，通俗易懂，但是还是不够简洁，且如果叫声不是croak五个字符，而是更长的字符串，那么if else就为字符串的长度，太冗杂了，于是搞一个比较通用的方法，根据总结的分为两种情况

代码2：

class Solution {
    public int minNumberOfFrogs(String c) {
        char[] croakOfFrogs = c.toCharArray();
        String t = "croak";
        int n = t.length();
        int[] hash = new int[n]; // 数组模拟哈希表
        Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标]
        //放入每一个字符对应的下标
        for (int i = 0; i < n; i++){
            index.put(t.charAt(i), i);
        }
        //遍历字符串
        for (char ch : croakOfFrogs) {
            //如果是c
            if (ch == t.charAt(0)) {
                //如果有多余的k
                if (hash[n - 1] != 0){
                    hash[n - 1]--;
                }
                hash[0]++;
            } else {//前驱--，当前++
                int i = index.get(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;
            }            
        }
        //返回k位置的次数（即至少有多少只青蛙） 
        return hash[n - 1];
    }
}

总结

到此模拟算法就学习完了，就是锻炼代码能力，模拟题目要求的操作，如果空间时间复杂度高了，那么基本就要去找规律，根据规律来简化