初识算法 · 模拟（2）

_lazy

发布于 2024-11-19 10:49:03

1660

文章被收录于专栏：Initial programmingInitial programming

前言：

本文的主题是模拟，通过两道题目讲解，一道是Z字形变化，一道是数青蛙。链接分别为：

1419. 数青蛙 - 力扣（LeetCode）

6. Z 字形变换 - 力扣（LeetCode）题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

Z字形变换

题目解析

该题目的要求相当于让我们将字符串分成一个一个的字符串，进行Z字形排列只需要让我们创建一个n * col的矩阵，可是col是多少我们并不知道。但是不影响。

题目要求我们转换字符串之后，将字符串从左到右依次读取字符串，最后返回即可。

这就是题目解析部分，我们进入到算法原理部分。

算法原理

因为是一道典型的模拟题目，所以我们只需要模拟一下这个过程就可以了：

解法一的话，直接就老老实实的模拟呗，不过这种方法的时间复杂度和空间复杂度都是比较高的，就拿创建的矩阵来说，我们都不知道矩阵的长究竟有多长，保险的创建方式就是让长等于length，毕竟N是有可能等于1的。

但是第一种方式在leetcode里面还真的是可以跑过去的，只是效率方面来说确实没有那么好而已。

接下来我们介绍一种优化方式，其实也是模拟大多数题目的一种优化方式，就找规律嘛，找规律之前，我们应该是否可以让所谓的字符变成一个一个的下标呢？当然是可以的。

就像是这样，转换成了下标之后，我们找规律就可以了，从第一行开始，发现是从0到6，也就是公差为6，此时的n是2，那么公差d是等于2 * n - 2的，其他n的取值也是这种情况，这里就不验证了。

那么第一行的规律我们找到了，那么最后一行一样的，无非开始的部分变成了n - 1而已，对于中间来说稍微是有一点麻烦的，因为有两个数字嘛。

同样的找规律，我们拿1举例，后面依旧是1 7 13，也是满足加d的这个规律的，对于5 11来说，我们拿1 5举例，1 + 5等于公差，对吧，所以第二个数的取值就是d - i，所以对于中间两个的取值我们只需要i d - i就可以了。

不过！我们还需要处理一下特殊情况，如果n = 1的话，那么我们就不需要变化了，并且n = 1的时候，公差d是等于0的。我们直接返回字符串就行了。

算法编写

class Solution 
{
public:
    string convert(string s, int numRows) 
    {
        // 处理边界情况
        if(numRows == 1) return s;
        // 开始解释
        string ret;
        int d = 2 * numRows - 2;
        // 处理第一行
        for (int i = 0; i < s.size(); i += d)
            ret += s[i];
        // 处理中间行
        for (int i = 1; i < numRows - 1; i++)
        {
            for (int m = i, n = d - m; m < s.size() || n < s.size(); m += d, n += d)
            {
                if(m < s.size()) ret += s[m];
                if(n < s.size()) ret += s[n];
            }
        }
        // 处理最后一行
        for(int i = numRows - 1; i < s.size(); i += d)
            ret += s[i];
        return ret;
    }
};

数青蛙

题目解析

数青蛙这道题目，青蛙的输出顺序是croak，每只青蛙都是一个一个的输出的，让我们在一个输出序列里面找到最少需要多少只青蛙才可能输出对应的输出序列。

那么要求是最少的青蛙，找到返回就可以了。

算法原理

对于这道题目来说，是不是和提莫攻击这道题目有点类似，因为都是模拟一个序列，提莫攻击模拟的是提莫的攻击，对于这道题目来说模拟的是青蛙的蛙鸣行为。

那么总共的输出序列是croak，可能一只青蛙在叫的时候，另一只青蛙穿插着叫了。

但是，这并不影响青蛙的叫声是非常死板的，死板到只能从croak这个字符串序列里面输出，也就是青蛙叫r的时候，需要看前面是否存在c，如果存在c的话，它才能从r继续。

那么

当我们遍历这个序列的时候，用一个哈希数组来映射，当遍历到某个元素，判断前面是否存在元素，如果存在，那么前面的元素--，当前元素++，代表青蛙叫到了哪个位置。

其中比较特殊的是，当我们遍历到了c，那么我们应该是从k里面找是否存在青蛙空闲下来了，如果空闲了，那么K--，C++即可，因为我们是要找最少的青蛙个数。

所以现在一个哈希表是肯定要的，那么映射的时候，我们需要一种映射关系是吧？所以我们可以使用unordered_map映射字符和下标的关系即可。

这里的唯一作用就是遍历的时候判断前面的字符而已。

算法编写

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string s = "croak";
        int len = s.size();
        vector<int> hash(len);
        unordered_map<char, int> index;
        for (int i = 0; i < len; i++)
            index[s[i]] = i;
        for (auto ch : croakOfFrogs) 
        {
            if (ch == 'c') 
            {
                if (hash[len - 1] != 0)
                    hash[len - 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 < len - 1; i++)
            if (hash[i] != 0)
                return -1;
        return hash[len - 1];
    }
};

感谢阅读！

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除

字符串