【模拟】算法实战

Love The Way You Lie 2023-10-15 11:30 5阅读 0赞

#### 文章目录 ####

*  一、算法原理
 *  二、算法实战
 *   *  1. leetcode1576 替换所有的问号
     *  2. leetcode495 提莫攻击
     *  3. leetcode6 N字形变换
     *  4. leetcode38 外观数列
     *  5. leetcode1419 数青蛙
 *  三、总结

--------------------

## 一、算法原理 ##

模拟就是用计算机来模拟题目中要求的操作，模拟题目通常具有代码量大、操作多、思路繁琐的特点。所谓的"模拟题"，用一句老话所就是"照着葫芦画瓢"，根据题目的表述进行筛选提取关键要素，按需求书写代码解决实际问题。

--------------------

## 二、算法实战 ##

### 1. leetcode1576 替换所有的问号 ###

> ![在这里插入图片描述][9c3a816b0b8b4ab4a0617f8f90589979.png]  
> [替换所有的问号][Link 1]

**解题思路：**

这是一道简单的模拟题，意思是一个字符串中有 `'?'` 字符，将些字符替换为`'a' ~ 'z'`中的任意一个字符后，使得这个字符串中不会出现连续两个以上的连续字符。首先我们遍历这个字符串，先找到字符 `'?'` 的位置，然后从`'a' ~ 'z'`中从左往右开始遍历，将该问号替换为其某个字符后看该位置左右是否一样，如果不一样，继续往后遍历寻找符合要求的字符。这里注意处理边界情况。

**代码实现：**

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

--------------------

### 2. leetcode495 提莫攻击 ###

> ![在这里插入图片描述][ec96185872e646a4953af202b54ef2de.png]  
> [提莫攻击][Link 2]

**解题思路：**

首先扫描这个数组，使用cnt统计答案，timeSeries\[i\]表示此时攻击的开始点，timeSeries\[i+1\]表示下一次攻击的开始点。

*  timeSeries\[i + 1\] - timeSeries\[i\] < duration，表示两次攻击重叠。cnt+=`timeSeries[i + 1] - timeSeries[i]`。
 *  timeSeries\[i + 1\] - timeSeries\[i\] >= duration，表示两次攻击不重叠， cnt+=duration。

因为最后一次攻击是肯定会持续完的，所以我们扫描数组的时候只需要扫描前n-1个元素。但是最后返回结果时候需要返回`cnt+duration`。

**代码实现：**

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

--------------------

### 3. leetcode6 N字形变换 ###

> ![在这里插入图片描述][b9fd9cced6194d8680a25f904fc322a9.png]  
> [N字形变换][N]

**解题思路：**

首先我们应该先搞清楚从原字符串到目标字符串是如何变换而来的。

![在这里插入图片描述][5b7f9f05cd474b348bb709d02b6c86d2.png]

我们可以看到这个过程：先将该字符串以`'N'`字形的顺序依次填入一个二维数组中，然后将该二维数组中的内容从上到下一行一行拼接起来即可。这里我们可以从中找一些规律出来：

![在这里插入图片描述][ce8f85d15d6c4892bf779b21bcc77e2f.png]

**代码实现：**

class Solution {
        
    public:
        string convert(string s, int numRows) {
        
            string ret = "";
            if(numRows == 1)
                return s;
            int sub = 2*numRows - 2;
            for(int i = 0; i < numRows; i++)
            {
        
                // 处理第一行和最后一行
                if(i == 0 || i == numRows-1){
        
                    for(int j = i; j < s.size(); j += sub){
        
                        ret += s[j];
                    }
                }else{
        
                    // 处理中间行
                    for(int k = i, p = sub - k; k < s.size() || p < s.size(); k += sub, p += sub)
                    {
        
                        if(k < s.size()) ret += s[k];
                        if(p < s.size()) ret += s[p];
                    }
                }
            }
            return ret;
        }
    };

--------------------

### 4. leetcode38 外观数列 ###

> ![在这里插入图片描述][93809e27291c411eb9a573e1287e9e8a.png]  
> [外观数列][Link 3]

**解题思路：**

题目告诉了我们数列的每一项的变换过程是通过上一项推导出来的，因此我们可以根据上一项模拟数列每一项的形成过程。在数列每一项的模拟过程中，我们依然使用滑动窗口的算法原理来实现。

**代码实现：**

class Solution {
        
    public:
        string countAndSay(int n) {
        
            // 使用双指针算法进行模拟
            string start = "1";
            while(--n)
            {
        
                string tmp;
                for(int left = 0, right = 0; left < start.size(); right++)
                {
        
                    if(start[left] != start[right])
                    {
        
                        tmp += to_string(right - left);
                        tmp += start[left];
                        left = right;
                    }
                }
                start = tmp;
            }
            return start;
        }
    };

--------------------

### 5. leetcode1419 数青蛙 ###

> ![在这里插入图片描述][5b18ab027ad842ec9a2e51b815ef9bea.png]  
> [数青蛙][Link 4]

**解题思路：**

这道题目属于典型的比较难的模拟题，先开一个哈希表，然后将`"croak"`按照<char, int>的方式映射进哈希表，这里的int指的是"croak"中字符的下标。开一个cnt来计数，统计每一个字符出现的次数。

从前向后遍历字符串，如果`ch=='c'`，说明需要一只青蛙开始发出蛙鸣，如果前面统计cnt\[n - 1\]，这里的n-1表示"croak"字符串的最后一个’k’的下标，意思是如果cnt\[n - 1\]已经出现过了，说明前面有一只青蛙已经将"croak"，这个字符串全部叫了一遍，那么我们让前面的青蛙继续从头开始叫就可以了，不需要增加青蛙的数量，因此让`cnt[n - 1]--，cnt[0]++`，如果cnt\[n - 1\] == 0, 则直接让cnt\[0\]++。

如果`ch!='c'`，则说明一只青蛙正在发出蛙鸣的过程中，此时我们让此时青蛙发出蛙鸣的字符的前一个字符的下标cnt\[c前面的字符\]- -，然后让正在遍历的字符数量cnt\[c\]++，如果中途发现cnt\[c前面的字符\] == 0， 说明该字符连续出现了两次以上，或者字幕出现的顺序有问题。直接返回-1即可。

最后我们统计的时候只需要关心"croak"中最后一个’k’出现了几次即可，同时，我们还需要遍历cnt中除最后一个元素外，看前面的字母出现的次数是否为0，若不为0，说明字幕出现的顺序不符合要求，直接返回-1。

**代码实现：**

class Solution {
        
    public:
        int minNumberOfFrogs(string croakOfFrogs) {
        
            string t = "croak";
            int n = t.size();
            vector<int> cnt(n);
    
            unordered_map<char, int> hash;
            for(int i = 0; i < n; i++) hash[t[i]] = i;
    
            for(char ch : croakOfFrogs)
            {
        
                if(ch == 'c'){
        
                    if(cnt[n - 1]) cnt[n - 1]--;
                    cnt[0]++;
                }else{
        
                    int i = hash[ch];
                    if(cnt[i - 1])
                        cnt[i - 1]--, cnt[i]++;
                    else return -1;
                }
            }
            for(int i = 0; i < n - 1; i++)
                if(cnt[i] != 0) return -1;
            return cnt[n - 1];
        }
    };

--------------------

## 三、总结 ##

模拟的过程就是对真实场景尽可能的模拟，但我们需要注意的是：模拟题并没有我们所想象的那么简单，它的代码中可能会有很多的`'坑'`，我们在写模拟算法的过程中需要谨慎。

[9c3a816b0b8b4ab4a0617f8f90589979.png]: https://img-blog.csdnimg.cn/9c3a816b0b8b4ab4a0617f8f90589979.png
[Link 1]: https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/
[ec96185872e646a4953af202b54ef2de.png]: https://img-blog.csdnimg.cn/ec96185872e646a4953af202b54ef2de.png
[Link 2]: https://leetcode.cn/problems/teemo-attacking/description/
[b9fd9cced6194d8680a25f904fc322a9.png]: https://img-blog.csdnimg.cn/b9fd9cced6194d8680a25f904fc322a9.png
[N]: https://leetcode.cn/problems/zigzag-conversion/
[5b7f9f05cd474b348bb709d02b6c86d2.png]: https://img-blog.csdnimg.cn/5b7f9f05cd474b348bb709d02b6c86d2.png
[ce8f85d15d6c4892bf779b21bcc77e2f.png]: https://img-blog.csdnimg.cn/ce8f85d15d6c4892bf779b21bcc77e2f.png
[93809e27291c411eb9a573e1287e9e8a.png]: https://img-blog.csdnimg.cn/93809e27291c411eb9a573e1287e9e8a.png
[Link 3]: https://leetcode.cn/problems/count-and-say/
[5b18ab027ad842ec9a2e51b815ef9bea.png]: https://img-blog.csdnimg.cn/5b18ab027ad842ec9a2e51b815ef9bea.png
[Link 4]: https://leetcode.cn/problems/minimum-number-of-frogs-croaking/