[Lc6_模拟] 替换所有的问号 | 提莫攻击 | Z 字形变换 | 外观数列

目录

1.替换所有的问号

代码

2.提莫攻击

代码

🎢3.Z 字形变换

题解

⭕4.外观数列

题解：

代码

模拟算法 —> 比葫芦画瓢

• 如果模拟题的时间复杂度和空间复杂度过高，则一般都需要进行优化
• 优化：一般都是找规律

这个算法特点：思路比较简单，考察的是代码能力。
这就决定了，

1. 一定要  模拟算法流程（一定要在演草纸上过一遍流程，注意细节！）
2. 把流程转化成代码

1.替换所有的问号

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

题目描述：

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

注意：你 不能 修改非 '?' 字符。

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

在完成所有转换（可能无需转换）后返回最终的字符串。如果有多个解决方案，请返回其中任何一个。可以证明，在给定的约束条件下，答案总是存在的。

示例 1：

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

因为 这道题目，还要考虑 重复问题，所以不能直接 std::replace(s.begin(), s.end(), '？', 'L')

我们采取 模拟数组的方法，要注意 左右边界的 防越界处理

代码

class Solution {
public:
    string modifyString(string s)
     {

        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {

               // 新增边界检查
            char left = (i > 0) ? s[i - 1] : 0;            
            char right = (i < s.size() - 1) ? s[i + 1] : 0; 
    
                // 我们来 避免重复问题
                for (char c = 'a'; c <= 'z'; c++) {
                    if (c ==right || c == left)
                        continue;
                    s[i] = c;
                }
            }
        }
        return s;
    }
};

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 。

代码

class Solution {
public:
    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
    
    //关注tS的真正有效的作用时间
    int ret=0,n=timeSeries.size();
    for(int i=0;i<n;i++)
    {
        ret+=duration;
        if(i<n-1 && timeSeries[i+1]<duration+timeSeries[i])
            ret-=(timeSeries[i]+duration-timeSeries[i+1]);
    }   
    return ret;
    }
};

减去重叠，加了两次的部分

🎢3.Z 字形变换

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

题目分析：

题解

给你一个字符串，它按照Z字形排列后，然后从左往右输出按照N字形排列之后的字符串。

解法一：模拟

• 题目要求怎么做就模拟一下，首先开辟一个n行
• 然后字符串长度的列的 二维数组。这样能保证把所有字符都能放进去。
• 但是时间复杂度和空间复杂度都是O(len*n)

class Solution {
public:
    string convert(string s, int numRows) {
        //从下往上/模拟
        //读取

        if(numRows==1) return s;
        vector<string> rows(numRows);
        //对每行 的字符串 进行尝试实现

        int cur=0;
        int dire=1;//1表示 行数移动向下

        for(char c:s)
        {
            rows[cur]+=c;//插入字符的位置

            if(cur+dire==numRows || cur+dire==-1)
            {
                //触底 反弹
                dire*=-1;
            }
            cur+=dire;//位置变化
        }
        //其实是可以将每列 压缩 重叠式看待的

        string result;
        for(string row:rows)
            result+=row;
        return result;


    }
};

想一想能不能进行优化。

模拟题的优化方式都是在模拟的基础上找规律

解法二：找规律

上面是把字符填到数组里，现在我把下标填进去

第一行从0跳到6然后在跳到12，我们发现它的间隔是一样的，这里的间隔公差设为d，d=6。

• 也就是说我们直接把下标0位置弄完，然后在找下标6的位置等等
• 就可以把第一行字符全部找完，就不用在弄一个数组然后把字符填上去了。

公差d应该怎么计算呢，我们发现 d=2*n-2（-2 是因为将中间部分移动到一列，就发现，其实就是上面和下面 都有一个空缺 ）

最后一行从下标n-1开始，n-1+d，n-1+2d，下标一定是要小于字符串长度的。

• 第一行和最后一行我们解决了，剩下就是中间行了
• 我们发现中间行公差其实也是6，但是如果一个一个算比如1+6=7，7+6=13，然后还要回头在来算5+6=11。
• 我们其实可以两个下标一起计算

上面d=2*n-2有可能不是所有情况都适应，我们再举个例子

发现这个公差公式也是正确的。

• 但是一定要注意n=1的情况，那就只有一行，如果按照上面找的规律就会死循环
• 此时原本的字符串就是最终答案，因此特殊处理一下

class Solution {
public:
    string convert(string s, int numRows) {
        //不再 重新开辟，直接利用
        //坐标的规律 优化

        if(numRows==1) return s;//边界处理

        int d=2*numRows-2;
        int n=s.size();
        string ret;

        for(int i=0;i<numRows;i++)//逐行处理
        {
        //先以第一行为例，进行 特例化代码书写
            for(int j=0;j+i<n;j+=d)
            {
        //逐列处理
            //周期 完整列字符
            ret+=s[i+j];

            //处理 中间斜线字符
            //不是 首位行  就还要中间再多一个
            if(i!=0 && i!=numRows-1 && d-i+j<n)
                ret+=s[d-i+j];
        }}
        return ret;
    }
};

• 注意 首末行的判断
• 进行 j+=d 步的跨越

想到 shellsort 中 gap 的设定，来进行 跨越排序

⭕4.外观数列

题目链接：38. 外观数列

题目分析：

外观数列」是一个数位字符串序列，由递归公式定义：

• countAndSay(1) = "1"
• countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

输入：n = 4

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

题解：

这道题具体意思是，给你一个n

返回到n的时候这个数的变化。

算法原理：

解法：模拟+双指针

• 找到了 连续相同的部分，就解释一下

代码

class Solution {
public:
    string countAndSay(int n) {
        // 处理 边界情况
        if (n == 1)
            return "1";

        // 报数
        vector<string> say(n + 1);
        say[1] = "1"; // 第一行

        for (int i = 2; i <= n; i++)
        // 从 第二行 开始生成
        {
            // 对 前一行 进行提取
            string prev = say[i - 1];
            string cur;


            int left = 0, right = 0;
            // 双指针 读取上一行

        for (right = 0; right <= prev.size(); right++) {
        if (right == prev.size() || prev[right] != prev[left])
                // 到了最后位置的时候，还要进行 最后一次的读取
                {
                    cur += to_string(right - left) + prev[left];
                    left = right;
                    // 实现 下标移动
                }
                // ！将数字 字符串化
                // 字符串 本来就可以当作 数组 通过下标 来进行读取
            }
        
        // 实现了对 第i行的读取
        say[i] = cur;
    }
    return say[n];
}
}
;

实现了 读取功能