模拟算法及其优化

第一题 替换所有问号

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

第二题 提莫攻击

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int total=0;
        total+=duration;
        for(int i=1;isize();i++)
        {
            int x=timeSeries[i]-timeSeries[i-1];//计算中毒时间的差值来判断中毒伤害的叠加
            if(x
            else total+=duration;
        }
        //total+=3;
        return total;
    }
};

第三题 字形变换

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows==1) return s;//这里不进行特判一定会超时
        string ret;
        int d=(numRows-1)*2;//画图观察第一行的间距差
 
        for(int i=0;isize();i+=d)//先处理第一行
        {
            ret+=s[i];
        }
        int y=d-1;//第i行第二个数字
        for(int i=1;i-1;i++)//第i行,是numsRows而不是s数组的size
        {
            for(int j=i,k=d-j;jsize()||jsize();j+=d,k+=d)//此处一共需要两组数据，特别注意
            {
                if(jsize())
                ret+=s[j];
                if(ksize())
                ret+=s[k];
            }
 
        }
 
        for(int i=numRows-1;isize();i+=d)
        {
            ret+=s[i];
        }
        return ret;
    }
};
 
 
// class Solution {
// public:
//     string convert(string s, int numRows) {
//         if (numRows < 2)
//             return s;
//         vector rows(numRows);
//         int i = 0, flag = -1;
//         for (char c : s) {
//             rows[i].push_back(c);
//             if (i == 0 || i == numRows -1)
//                 flag = - flag;
//             i += flag;
//         }
//         string res;
//         for (const string &row : rows)
//             res += row;
//         return res;
//     }
// };

第四题 外观数列

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

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

第五题 数青蛙 

 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        int n = croakOfFrogs.size();
        vector<int> hash(5,0);//记录蛙叫状态
        string h="croak";
        unordered_map<char, int> index;//映射字符下标
 
        for(int i=0; isize(); i++)
        {
            //index[croakOfFrogs[i]]=i;这句是错误的，填表的字符串应该是“croak”
            index[h[i]]=i;
        }
        
        for(int i=0; i
        {
            // for(auto c:hash)//io了容易超时
            // {
            //     cout<
            // }
            // cout<
            if(croakOfFrogs[i]=='c')
            {
                if(hash[index['k']] > 0) hash[index['k']]--;
                hash[index['c']]++;
            }
            else
            {
                int in=index[croakOfFrogs[i]];
                if(hash[in-1] == 0) return -1;
                hash[in]++;//移动这只青蛙叫到的位置
                hash[in-1]--;
            }
        }
 
        for(int i=0; i<4; i++)
        {
            if(hash[i]>0) return -1;
        }
        return hash[4];
    }
};