算法笔记(四)——模拟

文章目录

  • 替换所有的问号
  • 提莫攻击
  • Z字形变换
  • 外观数列
  • 数青蛙

模拟算法就是根据题目的要求,题目让干神马就做神马,一步一步来

替换所有的问号

题目:替换所有的问号

在这里插入图片描述

思路

  • 从左到右遍历整个字符串,找到问号之后,就⽤ a ~ z 的每⼀个字符去尝试替换

C++代码

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

提莫攻击

题目:提莫攻击

在这里插入图片描述
思路

  • 遍历数组当前位置减去前一个位置, 如果差值
  • 大于中毒时长,就加上中毒时间
  • 如果小于,就加上差值
  • 最后,加上最后一次中毒时间

C++代码

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

        return res + duration;
    }
};

Z字形变换

题目:Z字形变换

在这里插入图片描述
思路

  • 如果横着看,就是数学法,找通项公式;
  • 如果竖着看,在按列读取的时候,为每一行维护一个字符串,读到哪一行就在后面追加字符
  • 设置两个边界,在增长到或者减小到某个边界的时候,读取行的顺序进行反转,不断地从上到下,再从下到上读取,直到取完所有字串
class Solution 
{
public:
    string convert(string s, int numRows) 
    {
        if(numRows == 1) return s;

        vector<string> rows(numRows);
        int i = 0;
        int flag = -1;
        for(auto ch : s)
        {
            rows[i].push_back(ch);
            if(i == 0 || i == numRows - 1)
            {
                flag = -flag;
            }

            i += flag;
        }

        string res;
        for(auto x : rows) 
        {
            res += x;
        }
        
        return res;
    }
};

外观数列

题目:外观数列

在这里插入图片描述
思路
模拟 + 双指针,模拟实现
C++

class Solution 
{
public:
    string countAndSay(int n) 
    {
        string ret = "1";
        for(int i = 1; i < n; i ++)
        {
            string tmp;
            int len = ret.size();
            
            for(int l = 0, r = 0; r < len; )
            {
                while(r < len && ret[l] == ret[r]) r++;

                tmp += to_string(r - l) + ret[l];
                l = r;
            }
            ret = tmp;
        }
        return ret;
    }
};

数青蛙

题目:数青蛙

在这里插入图片描述

思路

  • 模拟将c、r、o、a、k存入哈希表;
  • 遍历字符串,
  • 如果遇到c,找最后一个字符,即k是否在哈希表中存在,若存在最后一个字符,即k--,当前字符,即c++
  • 遇到其他字符,若其前驱存在,前驱个数--,当前++;若不存在,返回-1

C++代码
纯暴力

class Solution 
{
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
       int hash[5]={0};
       int n = croakOfFrogs.size();
       for(int i = 0;i < n;i++)
       {
           if(croakOfFrogs[i] == 'c')
           {
               if(hash[4] > 0)
               {
                   hash[4]--;
                   hash[0]++;
               }
               else hash[0]++;
           }
           else if(croakOfFrogs[i] == 'r')
           {
               if(hash[0] > 0)
               {
                   hash[0]--;
                   hash[1]++;
               }
               else return -1;
           }
           else if(croakOfFrogs[i] == 'o')
           {
               if(hash[1]>0)
               {
                   hash[1]--;
                   hash[2]++;
               }
               else return -1;
           }
           else if(croakOfFrogs[i] == 'a')
           {
               if(hash[2] > 0)
               {
                   hash[2]--;
                   hash[3]++;
               }
               else return -1;
           }
           else if(croakOfFrogs[i] == 'k')
           {
               if(hash[3] > 0)
               {
                   hash[3]--;
                   hash[4]++;
               }
               else return -1;
           }
           else return -1;
       }
       if(hash[0]||hash[1]||hash[2]||hash[3]) return -1;
       
       return hash[4]; 
    }
};

借助unordered_map

class Solution 
{
public:
   int minNumberOfFrogs(string croakOfFrogs) 
   {
       string t = "croak";
       int n = t.size();
       vector<int> hash(n);
       unordered_map<char, int> mp = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};

       for(auto ch : croakOfFrogs)
       {
           if(ch == 'c')
           {
               if(hash[n - 1] != 0) hash[n - 1]--;
               hash[0]++;  
           }
           else
           {
               int i = mp[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];

   }
};
上一篇:墙绘交易平台设计:SpringBoot技术要点


下一篇:EnvoyFilter 是 Istio 中用于直接修改 Envoy 配置的一种资源类型