【优选算法】模拟 问题算法

​一：替换所有的问号

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 && ch !=s[i+1]) || (i==n-1 && ch != s[i-1]) || ( i>0 && i<n-1 && ch != s[i-1] && ch != s[i+1]))
                    {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }
        return s;
    }
};

二：提莫攻击

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

三：Z字形变换

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;

        string ret;
        int n = s.size();
        int d = 2*numRows-2;
        // 1.先处理第一行
        for(int i = 0; i < n; i+=d)
            ret += s[i];
        // 2.处理中间行
        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];
            }
        }
        // 3.处理最后一行
        for(int i = numRows-1; i < n; i+=d)
        {
            ret += s[i];
        }
        return ret;
    }
};

四：外观数列

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 left = 0, right = 0; right < len; )
            {
                while(right < len && ret[left] == ret[right])
                    right++;
                tmp += to_string(right-left) + ret[left];
                left = right;
            }
            ret = tmp;
        }
        return ret;
    }
};

五：数青蛙​

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        // 使用数组来模拟哈希表
        vector<int> hash(n);
        // 使用 map 来表示 字符的下标
        unordered_map<char, int> char_Index;
        for(int i = 0; i < n; i++)
            char_Index[t[i]] = i;
        
        // 开始操作
        for(auto& ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                if(hash[n-1] != 0)
                    hash[n-1]--;        // 一个青蛙叫完之后，继续叫
                hash[0]++;
            }
            else
            {
                int i = char_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];
    }
};

原文地址：https://blog.csdn.net/2302_78684687/article/details/146373937

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！