【基础算法】模拟

1.替换所有的问号 

替换所有的问号

思路：

模拟实现

从a-z依次尝试替换？是否满足题意，第一个满足的就可break掉。

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

2.提莫攻击

提莫攻击

思路：

 模拟

计算两个相邻时间的差值

如果差值大于等于duration，则说明中毒要持续duration妙

如果差值小于duration，则说明中毒要持续两者的差值

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

3.Z字形变换

Z字形变换 

思路：

模拟后找规律

class Solution {
public:
    string convert(string s, int numRows) {
        
        //处理边界情况
        if(numRows == 1) return s;

        int d = 2 * numRows - 2, n = s.size();
        string ret;
        
        //处理第一行
        for(int i = 0; i < n; i += d)  ret += s[i];
        //处理中间行
        for(int k = 1; k < numRows - 1; k++)//枚举每一行
        {
            for(int i = k, j = d - k; i < n || j < n; i += d, j += d)
            {
                if(i < n) ret += s[i];
                if(j < n) ret += s[j];
            }
        }
        //处理最后一行
        for(int i = numRows - 1; i < n; i += d) ret += s[i];

        return ret;
    }
};

 4.外观数列

外观数列

思路：

模拟 + 双指针

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for(int i = 0; i < n - 1; i++)//解释n-1次即可
        {
            string tmp;
            int len = ret.size();
            for(int left = 0, right = 0; left < len;)
            {
                while(right < len && ret[left] == ret[right]) right++;
                    tmp += to_string(right - left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

5.数青蛙

数青蛙 

思路：

模拟 + 哈希

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        vector<int> hash(n);//用数组模拟哈希表

        unordered_map<char, int> index;//记录每个字符的下标
        for(int i = 0; i < n; i++)
            index[t[i]] = i;

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