【C++算法】模拟算法

替换所有的问号

• 题目链接

替换所有的问号https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/

• 算法原理

• 代码步骤

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

提莫攻击

• 题目链接

提莫攻击https://leetcode.cn/problems/teemo-attacking/description/

• 算法原理

• 代码步骤

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字形变换

• 题目链接

Z字型变换https://leetcode.cn/problems/zigzag-conversion/description/

• 算法原理

• 代码步骤

class Solution {
public:
    string convert(string s, int numRows) 
    {
        if(numRows == 1)
        {
            return s;
        }
        int n = s.size();
        int d = 2 * numRows - 2;
        string ret;
        // 第一行
        for(int i = 0;i < n; i += d)
        {
            ret += s[i];
        }
        // 中间行
        for(int i = 1; i < numRows - 1; i++)
        {
            for(int j = i, k = d - i; j < n || k < n; j += d, k += d)
            {
                if(j < n) ret += s[j];
                if(k < n) ret += s[k];
            }
        }
        // 最后一行
        for(int i = numRows - 1; i < n; i += d)
        {
            ret += s[i];
        }
        return ret;
    }
};

外观数列

• 题目链接

外观数列https://leetcode.cn/problems/count-and-say/description/

• 算法原理

• 代码步骤

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

数青蛙

• 题目链接

数青蛙https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/

• 算法原理

• 代码步骤

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) 
    {
        string s = "croak";
        int n = s.size();
        vector<int> ret(n);
        // 哈希找下表
        unordered_map<char, int> hash;
        for(int i = 0; i < n; i++)
        {
            hash[s[i]] = i;
        }
        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                if(ret[n - 1] != 0)
                {
                    ret[n - 1]--;
                    ret[0]++;
                }
                else
                {
                    ret[0]++;
                }
            }
            else
            {
                if(ret[hash[ch] - 1] != 0)
                {
                    ret[hash[ch] - 1]--;
                    ret[hash[ch]]++;
                }
                else
                {
                    return -1;
                }
            }
        }
        for(int i = 0; i < n - 1; i++)
        {
            if(ret[i] != 0) return -1;
        }
        return ret[n - 1];
    }
};