当前位置：首页 > article >正文

算法：模拟的巧妙演绎

article 2025/1/28 3:19:04

1. 基本思想

模拟的基本思想是通过代码模拟问题的实际过程，将问题的描述转化为具体的计算步骤，逐步还原问题的解决路径。模拟算法的核心是细致地分解问题，将每一步操作用代码精确实现。

2. 替换所有的问号

遍历数组，当遇到“ ？”时，用不等于左右字母的字母替换“ ？”，如果处于数组的第一个或最后一个位置，只需要不等于右边或左边字母即可。

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

1576. 替换所有的问号 - 力扣（LeetCode）

3. 提莫攻击

1. 特殊情况处理

如果攻击时间点数组只有一个元素，则直接返回 duration，因为只有一次毒药攻击。

2. 遍历数组，计算总中毒时间

遍历数组，从第 1 个时间点开始，计算当前攻击与前一次攻击的间隔时间 gap。
如果间隔时间 gap 大于等于 duration，两次毒药攻击之间互不干扰，可以将 duration 加入总时间。
如果间隔时间 gap 小于 duration，说明毒药效果重叠了，只加上 gap 的时间。

3. 补充最后一次毒药的持续时间

遍历结束后，需要把最后一次毒药攻击的 duration 加入总时间。

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

495. 提莫攻击 - 力扣（LeetCode）

4. Z字变形

1. 特殊情况处理

当行数 numRows 为 1 时，字符串无需变换，直接返回原字符串即可。

2. 处理第一行

第一行的索引是 0, d, 2d, 3d...，按照每隔 d 个字符取值，加入结果中。

3. 处理中间行

遍历从第 k 行到倒数第 2 行 (1 <= k <= numRows - 2)。
每一行有两种类型的索引：
- 正向索引：i = k + d * m，即从第 k 个开始，每隔 d 跳一个。
- 反向索引：j = d - k + d * m，即对应“Z字形”反折的索引。
检查 i 和 j 是否小于字符串长度 n，如果是，就将对应字符加入结果字符串。

4. 处理最后一行

最后一行的索引是 numRows - 1, numRows - 1 + d, numRows - 1 + 2d...，直接按照周期跳跃取值。

class Solution {
public:
    string convert(string s, int numRows) {
        if(numRows == 1) return s;
        string ret;
        int n = s.size(), d = 2 * numRows - 2;
        //处理第一行
        for(int i = 0; i < n; i += d)
            ret += s[i];
        //处理第k行
        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;
    }
};

6. Z 字形变换 - 力扣（LeetCode）

5. 外观数列

left 和 right：这两个指针用于遍历字符串 ret（上一项的报数结果）。

left 用来标记当前字符的开始位置。
right 用来扫描直到遇到不同的字符或遍历完字符串。

内层 while 循环：在当前字符相同的情况下，right 向右移动，直到遇到不同的字符或达到字符串末尾。

描述当前字符段：当找到一段相同字符时，通过 to_string(right - left) 得到该字符段的长度，再加上字符本身 ret[left]，拼接到临时字符串 tmp 中。
更新 left：每次描述完一段相同字符后，更新 left 为 right，继续查找下一段字符。

class Solution {
public:
    string countAndSay(int n) {
        string ret = "1";
        for(int i = 1; i < n; ++i)
        {
            int len = ret.size();
            string tmp;
            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;
    }
};

38. 外观数列 - 力扣（LeetCode）

6. 数青蛙

字符映射初始化：
- s 是 "croak" 字符串，n 是该字符串的长度（5）。
- hash 数组用于存储青蛙在每个阶段的数量，初始化为 0。
- index 是字符到阶段索引的映射，方便后续查找。
遍历字符串并更新状态：
- 对于每个字符 ch，根据字符类型更新 hash 数组。
- 如果是 c，说明一只新的青蛙开始叫，直接增加 hash[0]。
- 对于其他字符，检查前一个阶段是否有青蛙，如果没有则返回 -1，表示不合法；否则，更新对应阶段的青蛙数量。
检查是否有未完成的青蛙：
- 遍历 hash 数组，检查是否有未完成的青蛙。如果有，则返回 -1。

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        vector<int> hash(n);
        unordered_map<char, int> index;
        for(int i = 0; i < n; ++i)
            index[s[i]] = i; 
        for(char ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                if(hash[n - 1] > 0) {hash[n - 1]--;}
                hash[0]++;
            }
            else 
            {
                int in = index[ch];
                if(hash[in - 1] == 0) return -1;
                else hash[in - 1]--, hash[in]++;
            }
        }
        for(int i = 0; i < n - 1; ++i)
            if(hash[i] != 0) return -1;
        return hash[4];
    }
};

1419. 数青蛙 - 力扣（LeetCode）

查看全文

http://www.kler.cn/a/519320.html