算法——模拟

发布于:2025-02-23 ⋅ 阅读:(69) ⋅ 点赞:(0)

本篇文章,我们来分享一个新的算法——模拟,所谓模拟,就是将题目给出的条件要求,转化为代码实现即可


一.替换所有的问号

来看题目(出自力扣):

题目要求我们将字符串s中的所有的问号替换为小写字母,且替换之后字符串中不能存在连续重复的字符,意思就是每个字符都不能和自己相邻的字符相同。

根据题目要求,就需要我们遍历字符串寻找 '?' ,然后在小写字母中寻找一个能够同时满足不合前边和后边字母相同的字母,值得注意的是,当该 '?' 处于字符串开头或者结尾的位置时,我们仅需判断其一侧就好,代码如下

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

 二.提莫攻击

来看题目(出自力扣):

 题目很容易理解,提莫攻击一次艾希,都会使艾希中毒一定时间,当艾希在中毒时间内再次被提莫攻击,中毒的持续时间将被重置,让我们求艾希中毒的总时间。

举个简单的例子,如果中毒的持续时间为两秒,那艾希在1秒时被攻击,那么中毒的持续时间就会是1秒和2秒。如果艾希在第二秒时再次受到攻击,那么中毒的总持续时间就会是1秒,2秒和3秒。

由此我们能够得出,当艾希受到攻击的两个时间点的差值大于等于毒的持续时间时,那么总持续时间就加上毒的持续时间,反之,当艾希受到攻击的两个时间点的差值小于毒的持续时间时,总的持续时间要加上这个差值

值得注意的是,上述方法计算的时间不包括艾希受到最后一次攻击后毒的持续时间,所以最后还需再加一次

    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ret = 0;
        for(int i = 0;i < timeSeries.size() - 1;i++)
        {
            ret += timeSeries[i + 1] - timeSeries[i] > duration ? duration : timeSeries[i + 1] - timeSeries[i];
        }
        ret += duration;
        return ret;
    }

三.外观数列

来看题目(出自力扣):

看到这个题目啊,可能有些不好理解,没关系,我们来看它的一个实例:

 

简单来说,就是一个字符串初始为 “1” ,然后我们要将它循环往复的将其更新替换

 初始字符串为“1”,然后将它读出来,即“1个1”,将其作为第二个字符串“11”,然后再读,即“2个1”,将其作为第三个字符串“21”,不断重复执行n次。

简单来说,就是统计一个字符串中连续字符的个数,将这个个数与该字符串联成为新的字符串

那么本题,我们就可以借助模拟+双指针的算法来解决。

    string countAndSay(int n) {
        string s = "1";
        if(n == 1)
            return s;
        while(--n)
        {
            int left = 0,right = 0;
            string temp;
            while(right <= s.size())
            {
                if(right == s.size())
                {
                    temp += to_string(right - left);
                    temp += s[left];
                    break;
                }
                if(s[right] != s[left])
                {
                    temp += to_string(right - left);
                    temp += s[left];
                    left = right;
                }
                right++;
            }
            s = temp;
        }
        return s;
    }

模拟算法没有什么特殊技巧,就是将题目给出的解题思路和方法转换成代码实现


网站公告

今日签到

点亮在社区的每一天
去签到