【算法一周目】破解谜题如同雕刻思想：一步步还原模拟题的真谛

HZzzzzLu

发布于 2025-07-21 08:35:19

1420

文章被收录于专栏：codingcoding

1. 替换所有的问号

题目链接：1576. 替换所有的问号

题目描述：

给你一个仅包含小写英文字母和 '?' 字符的字符串 s，请你将所有的 '?' 转换为若干小写字母，使最终的字符串不包含任何连续重复的字符。注意：你不能修改非 '?' 字符。

题目测试用例保证除 '?' 字符外，不存在连续重复的字符。

请你返回最终的字符串。题目数据保证答案存在且唯一。

示例 1：

输入：s = "?zs"
输出："azs"
解释：该示例共有 25 种解决方案，从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改，因为字符串 “zzs” 中有连续重复的两个 'z'。

示例 2：

输入：s = "ubv?w"
输出："ubvaw"
解释：该示例共有 24 种解决方案，只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww"都包含连续重复的字符。

提示：

1 <= s.length <= 100
s 仅包含小写英文字母和 '?' 字符

解题思路

模拟题目要求的过程，遍历字符串，遇到 '?' 后用a到z的字符尝试进行替换，确保替换的字符与前一个和后一个字符不重复即可。

特殊情况的处理：

当'?'是第一个字符时，替换字符只需要与后一个字符不重复。
当'?'是最后一个字符时，替换字符只需要与前一个字符不重复。

代码实现

class Solution {
public:
    string modifyString(string s) {
        int n = s.size();
        for(int i = 0; i < n; ++i)
        {
            //遇到'?'时用a到z替换
            if(s[i] == '?')
            {
                for(char ch = 'a'; ch <= 'z'; ch++)
                    //替换字符与前一个和后一个字符不重复
                    if((i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1]))
                    {
                        //替换后跳出循环
                        s[i] = ch;
                        break;
                    } 
            }
        }
        return s;
    }
};

时间复杂度：

O(n)

空间复杂度：

O(1)

2. 提莫攻击

题目链接：495. 提莫攻击

题目描述：

在《英雄联盟》的世界中，有一个叫提莫的英雄。他的攻击可以让敌方英雄艾希（寒冰射手）进入中毒状态。当提莫攻击艾希时，艾希的中毒状态会持续 duration 秒。具体来说，提莫在 t 秒发起攻击，意味着艾希在时间区间 [t, t + duration - 1] 内（包含 t 和 t + duration - 1）处于中毒状态。如果提莫在之前的中毒影响结束前再次攻击，则中毒状态计时器会重置，中毒影响将在新的攻击后 duration 秒后结束。

给定一个非递减的整数数组 timeSeries，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，和一个表示中毒持续时间的整数 duration。返回艾希处于中毒状态的总秒数。

示例 1：

输入：timeSeries = [1,4], duration = 2
输出：4
解释：
- 第 1 秒，提莫攻击艾希并使其立即中毒，中毒状态持续 2 秒，即第 1 秒和第 2 秒。
- 第 4 秒，提莫再次攻击艾希，艾希中毒状态又持续 2 秒，即第 4 秒和第 5 秒。艾希在第 1, 2, 4, 5 秒处于中毒状态，总中毒秒数为 4。

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：
- 第 1 秒，提莫攻击艾希并使其立即中毒，中毒状态持续 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，重置中毒计时器，中毒状态持续到第 2 秒和第 3 秒。艾希在第 1, 2, 3 秒处于中毒状态，总中毒秒数为 3。

提示：

1 <= timeSeries.length <= 104
0 <= timeSeries[i], duration <= 107 timeSeries 按非递减顺序排列

解题思路

提莫攻击艾希后，艾希的中毒状态会持续 duration 秒，timeSeries数组记录了提莫在第几秒发起攻击，对于任意两个相邻的时间间隔

和

，其时间间隔为

gap = x2 - x1

，我们通过

gap

来讨论中毒持续时间。

用变量

ret

来记录总的中毒时间。

gap \geqslant duration

时，两次攻击间隔大于等于

duration

秒，本次攻击导致的中毒状态持续

duration

秒，

ret += duration

。

gap < duration

时，两次攻击间隔小于

duration

秒，本次攻击导致的中毒状态只能持续

x2 - x1

秒，

ret += x2 - x1

。

注意：最后一次的攻击导致的中毒时间一定有

duration

秒。

代码实现

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int ret = 0, n = timeSeries.size();
        for(int i = 1; i < n; ++i)
        {
            //两次攻击之间的时间间隔
            int gap = timeSeries[i] - timeSeries[i-1];
            if(gap >= duration) ret += duration;
            else ret += gap;
        }
        //将最后一次的攻击的中毒时间也加上
        return ret + duration;
    }
};

时间复杂度：

O(n)

空间复杂度：

O(1)

3. N 字形变换

题目链接：6. N 字形变换

题目描述：

将一个给定字符串 s 根据给定的行数 numRows，以从上往下、从左到右进行 Z 字形排列。例如，输入字符串为 "PAYPALISHIRING"，行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：

P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、, 和 . 组成
1 <= numRows <= 1000

解题思路

对于这道题，我们可以使用模拟去解决，但是这样空间的损耗会比较大（需要额外开辟一个

n \times m

大小的数组），所以我们可以通过找规律的办法来优化。

通过上图，可以得以下的规律：

第一行和最后一行：0、0+gap、0+2*gap、…
中间的行：两两一组，行号为n ，(n, gap - n)、(n + gap, 2*gap-n)、…

代码实现

class Solution {
public:
    string convert(string s, int numRows) {
        int gap = 2 * numRows - 2, n = s.size();
        //处理numRows的情况，不然程序会死循环
        if(gap == 0) return s;
        string ret;

        //1.处理第一行
        for(int i = 0; i < n; i += gap)
            ret += s[i];

        //2.处理中间的行,k最多能取到n-2
        for(int k = 1; k < numRows - 1; ++k)
        {
            for(int i = k, j = gap - k; i < n || j < n; i += gap, j += gap)
            {
                if(i < n) ret += s[i];
                if(j < n) ret += s[j];
            }
        }

        //3.处理最后一行
        for(int i = numRows - 1; i < n; i += gap)
            ret += s[i];

        return ret;
    }
};

时间复杂度：

O(n)

空间复杂度：

O(1)

4. 外观数列

题目链接：38. 外观数列

题目描述：

给定一个正整数 n，输出外观数列的第 n 项。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = "1"
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

前五项如下：

1
11
21
1211
111221

说明：

第 1 项是数字 1
第 2 项描述前一项 1，即“一个 1”，记作 "11"
第 3 项描述前一项 11，即“两个 1”，记作 "21"
第 4 项描述前一项 21，即“一个 2 一个 1”，记作 "1211"
第 5 项描述前一项 1211，即“一个 1 一个 2 两个 1”，记作 "111221"

示例 1：

输入：n = 1
输出："1"

示例 2：

输入：n = 4
输出："1211"

提示：

1 <= n <= 30

解题思路

对于外观数列，其实就是对前一项字符串的相同字符进行统计，题目要求我们输出第

项外观数列，只需要从第一项字符串 "1" 进行

n - 1

次翻译即可。

具体如下：

对前一项字符串统计相同字符的数量，将得到的数量和该字符加入新的字符串，直到对上一串的字符串统计完。
对第一项字符串 "1" 进行

n - 1

次如上的操作即可。

代码实现

递归写法

class Solution {
public:
 
    string countAndSay(int n) {
        if(n == 1) return "1";

        string prev = countAndSay(n-1), tmp;
        int len = prev.size();
        for(int left = 0, right = 0; right < len; )
        {
            while(right < len && prev[left] == prev[right]) right++;
            tmp += to_string(right - left) + prev[left];
            left = right;
        }
        return tmp;
    }
};

迭代写法

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;
    }
};

时间复杂度：

O(n \times m)

，

为生成字符串的最大长度

空间复杂度：

O(m)

，存储临时字符串数组的额外空间开销

5. 数青蛙

题目链接：1419. 数青蛙

题目描述

给定一个字符串 croakOfFrogs，表示青蛙发出的 “croak” 叫声的组合。可以有多只青蛙同时叫，因此字符串中可能会包含多个 “croak”。要求返回完成所有叫声所需的最少青蛙数量。如果字符串不是有效的 “croak” 组合，则返回 -1。

示例：

输入："croakcroak"，输出：1
输入："crcoakroak"，输出：2
输入："croakcrook"，输出：-1

解题思路

对于这道题，我们需要从青蛙叫声 "croak" 字符串的第一个字符 'c' 模拟青蛙叫声从而获取完成所有叫声所需的最少青蛙数量。

具体如下：

创建青蛙叫声 "croak" 字符串 t ，一个 hash 数组记录青蛙叫到了哪个字符和一个记录其中每一个字符的对应下标 index 哈希表。
遍历 "croakOfFrogs" 字符串，根据字符的不同来分情况处理：
- 若字符为 'c' ，检查有没有青蛙完成了一次叫声，如果有则复用该青蛙，没有则让新一只青蛙开始叫。
- 若字符为除 'c' 以外的字符，检查上一个字符有没有青蛙叫到，没有说明字符串不合法，返回 -1 ，有的就让叫到上一个字符青蛙叫该字符。
检查 hash 数组除字符 'k' 以外的字符是否存在青蛙，存在说明字符串不合法，返回 -1 ，合法就返回字符 'k' 对应有多少只青蛙。

代码实现

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string t = "croak";
        int n = t.size();
        //青蛙叫到了哪个字符，0下标对应字符'c'，1下标对应字符'r'，依次类推
        //hash[i]的值代表的是有多少只青蛙叫出i对应的字符，叫出'k'完成一次叫声
        vector<int> hash(n);
        //存储的是ch在字符串t的下标，方便快速找出前一个字符    
        unordered_map<char, int> index; 

        for(int i = 0; i < n; ++i) index[t[i]] = i;

        for(auto ch : croakOfFrogs)
        {
            if(ch == 'c')
            {
                //查看'k'有没有青蛙叫到（完成一次叫声），有则复用青蛙，没有则新的一只开始叫
                if(hash[n-1] != 0) hash[n-1]--;
                hash[0]++;
            }
            else
            {
                //当前字符在t中的下标
                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]) return -1;

        //字符'k'对应的青蛙个数即为不同青蛙的最少数目
        return hash[n-1];
    }
};