【算法系列篇】模拟算法

前言

前面我们学习的算法，当读完题目之后可就能就会知道使用哪种算法，这种算法就类似于一种模板，而有一类算法却不能称为特定的模板，这种就叫做模拟算法。模拟算法是指：根据题目提供的信息，将该题目的解决过程模拟出来就能够得到最终的结果，模拟算法比较简单，只要能够根据题目的意思将题目给模拟出来，一般都能够解决这个问题。

模拟算法是一种计算机算法，用于模拟或仿真现实世界中的某个过程、系统或现象。它通过运行一系列的步骤或规则来模拟目标对象的行为，并生成与真实情况相似的结果。

1.替换所有问号

https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/

1.1 题目要求

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

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

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 100

• s 仅包含小写英文字母和 ‘?’ 字符

class Solution {
    public String modifyString(String s) {

    }
}
1
2
3
4
5

1.2 做题思路

这个题目的思路很简单，我们只需要遍历一遍字符串，然后将字符为 ? 的字符更改为除 ? 之外的其他 26 个小写英文字母，并且保证相邻的字符不能重复。通过模拟算法，我们是可以直接解决这个问题的，需要多加注意的就是下标的越界问题，当下标为字符串的第一个字符的时候，它只有右边的一个相邻字符；当字符为中间的 n 个字符的时候，它需要考虑左右两个相邻字符；而当字符为最后一个字符的时候，则只有左边一个相邻的字符。

1.3 Java代码实现

class Solution {
    public String modifyString(String ss) {
    //因为Java代码操作字符串较复杂，所以我们可以将字符串转换为数组来操作
        char[] s = ss.toCharArray();
        int n = s.length;
        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])) {
                        s[i] = ch;
                        break;
                    }
                }
            }
        }

        return String.valueOf(s);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 提莫攻击

https://leetcode.cn/problems/teemo-attacking/

2.1 题目要求

在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。

当提莫攻击艾希，艾希的中毒状态正好持续 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 。
1
2
3
4
5
6

示例 2：

输入：timeSeries = [1,2], duration = 2
输出：3
解释：提莫攻击对艾希的影响如下：
- 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。
- 第 2 秒，提莫再次攻击艾希，并重置中毒计时器，艾希中毒状态需要持续 2 秒，即第 2 秒和第 3 秒。
艾希在第 1、2、3 秒处于中毒状态，所以总中毒秒数是 3 。
1
2
3
4
5
6

提示：

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

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {

    }
}
1
2
3
4
5

2.2 做题思路

这道题目也就是需要根据提莫攻击的时间和次数来计算受到伤害的时间，只需要根据题目给的timeSeries数组来知道受到攻击的时间的次数，然后结合给定的 duraction 来计算总共时间。

但是，我们需要考虑一个特殊的情况，当两次攻击的间隔时间小于受到伤害的持续时间的话，那么受到伤害的持续时间就会被重置。

根据上面的两种情况我们可以将提莫的攻击间隔分为两种情况：攻击间隔时间大于伤害持续时间；攻击间隔时间小于等于伤害持续时间。当攻击间隔时间大于伤害持续时间的时候，我们只需要加上这个duraction就行了，当间隔时间小于等于伤害持续时间的话，就加上这两次的攻击间隔时间的差，而不是duraction。

2.3 Java代码实现

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

        return ret += duration;
    }
}
1
2
3
4
5
6
7
8
9
10
11

3. N 字形变换

https://leetcode.cn/problems/zigzag-conversion/

3.1 题目要求

将一个给定字符串 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"
1
2

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I
1
2
3
4
5
6
7

示例 3：

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

提示：

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

class Solution {
    public String convert(String s, int numRows) {

    }
}
1
2
3
4
5

3.2 做题思路

这个题目是什么意思呢？就是将给定的字符串变换成 numRows 行 N 型图形，举个例子：

我们可以使用二维数组来模拟出来结果，但是这样的时间复杂度和空间复杂度都很高，那么时候有一种方法可以降低时间复杂度和空间复杂度呢？是有的，我们只需要多观察，然后找出其中的规律：那些字符处于第一行，哪些字符处于最后一行，然后再将这些重新组合的字符拼接在一起就可以了，所以这道题的关键就在于如何找到其中的规律。

3.3 Java代码实现

class Solution {
    public String convert(String ss, int numRows) {
        if(numRows == 1) return ss;
        char[] s = ss.toCharArray();
        int n = s.length;
        int d = 2 * numRows - 2;
        StringBuilder ret = new StringBuilder();
        //处理第一行数据
        for(int i = 0; i < n; i += d) ret.append(s[i]);
        //处理中间 numRows-2 行数据
        for(int i = 1; i < numRows - 1; i++) {
            for(int j = i, k = d - j; j < n || k < n; j += d, k += d) {
                if(j < n) ret.append(s[j]);
                if(k < n) ret.append(s[k]);
            }
        }
        //处理最后一行数据
        for(int i = numRows - 1; i < n; i += d) ret.append(s[i]);

        return ret.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4. 外观数列

https://leetcode.cn/problems/count-and-say/

4.1 题目要求

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

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

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1. 1
   1

2. 11
   1

3. 21
   1

4. 1211
   1

5. 111221
   1

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 “3322251” 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。
1
2
3

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"
1
2
3
4
5
6
7

提示：

• 1 <= n <= 30

class Solution {
    public String countAndSay(int n) {

    }
}
1
2
3
4
5

4.2 做题思路

这道题可以使用双指针来管理相同数字的区间，left 指针和 right 指针都从 0 位置开始，当 right 所指向的内容和 left 所指的内容相同时，right 继续向后移，如果不相等，则可以更新字符串中的内容，更新完成之后，left 指针指向 right 指针所指的位置，然后 right 指针继续向后移动，直到 right 指向字符串的末尾。

4.3 Java代码实现

class Solution {
    public String countAndSay(int n) {
        String ret = "1";
        for(int i = 1; i < n; i++) {
            StringBuilder tmp = new StringBuilder();
            int left = 0, right = 0;
            while(right < ret.length()) {
                while(right < ret.length() && ret.charAt(left) == ret.charAt(right)) right++;
                //相同数字的数量
                tmp.append(Integer.toString(right - left));
             	//数字
                tmp.append(ret.charAt(left));
                left = right;
            }
            ret = tmp.toString();
        }
        return ret;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5. 数青蛙

https://leetcode.cn/problems/minimum-number-of-frogs-croaking/

5.1 题目要求

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。

请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成，请返回 -1 。

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次
1
2
3

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"
1
2
3
4
5

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。
1
2
3

提示：

• 1 <= croakOfFrogs.length <= 105
• 字符串中的字符只有 ‘c’, ‘r’, ‘o’, ‘a’ 或者 ‘k’

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {

    }
}
1
2
3
4
5

5.2 做题思路

这道题目的意思是根据叫声来判断最少的青蛙数，那么如何才能判断是否是青蛙呢？就根据他的叫声，当听到 ‘c’ 的时候，如果后面依次出现’r’ ‘o’ ‘a’ ‘k’ 字符，那么这就可以算作一个青蛙，如果在 croak 后面又出现了 croak ，可以认为是一只青蛙叫了两声,“croakcroak”，但是如果在第一只青蛙叫的过程中又出现了 ‘c’ 的时候，这只能是第二只青蛙的叫声——“crocakroak”，这就是有两只青蛙 。因为‘c’ ‘r’ ‘o’ ‘a’ ‘k’ 需要是按顺序出现，所以当遇到 ‘r’ 的时候，需要知道前面 ‘c’ 是否出现了最少一次，后面的 ‘o’ ‘a’ ‘k’ 也是如此，如果前面的字母并没有出现，就直接返回 -1。

但是这样做的话，统计的不是最少的青蛙数，如果想要统计出最少的青蛙数，当遇到 ‘c’ 字符的时候，可以判断字符 ‘k’ 是否存在，如果存在就说明一个青蛙已经叫完了，它可以再叫第二声，也就是 k 的数量–，c 的数量++。

5.3 Java代码实现

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        String s = "croak";
        int n = s.length();
        Map<Character,Integer> map = new HashMap<>();
        //这个哈希表中存放叫声对应的字符和下标
        for(int i = 0; i < n; i++) {
            map.put(s.charAt(i),i);
        }
        //这个哈希表用来统计字符出现的次数，也就是模拟出蛙叫的过程
        int[] hash = new int[n];
        for(int i = 0; i < croakOfFrogs.length(); i++) {
            char ch = croakOfFrogs.charAt(i);
            //当遇到 'c' 字符的时候，需要判断 'k' 字符是否出现
            if(map.get(ch) == 0) {
                if(hash[n - 1] != 0) {
                    hash[n - 1]--;
                    hash[0]++;
                }else {
                    hash[0]++;
                }
            }else {
                if(hash[map.get(ch) - 1] == 0) return -1;
                hash[map.get(ch) - 1]--;
                hash[map.get(ch)]++;
            }
        }

		//当字符串遍历完之后，如果除 k 位置可以不为0之外，其他字符位置数量如果不为0，
		//则说明有不正确的叫声，直接返回-1
        for(int i = 0; i < n - 1; i++) {
            if(hash[i] != 0) return -1;
        }

        return hash[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

总结

在本篇博客中，我们深入探讨了模拟算法的定义、应用和实现。模拟算法是一种强大的工具，可以帮助我们模拟复杂系统、解决优化问题以及验证和测试系统的行为。

通过模拟算法，我们可以模拟现实世界中的各种过程、系统或现象，并生成与真实情况相似的结果。这使得我们能够更好地理解和预测复杂系统的行为，优化解决方案，并验证系统的正确性和性能。

在设计和实现模拟算法时，我们需要选择适当的模型，定义合适的步骤和规则，并进行数据收集和结果分析。这些步骤的正确性和准确性对于生成可靠的模拟结果至关重要。

模拟算法在多个领域中有着广泛的应用，包括科学研究、工程设计、优化和决策等方面。它们为我们提供了一种强大的工具，可以帮助我们理解和探索复杂系统的行为，并支持我们做出更加明智的决策。

尽管模拟算法有着诸多优点，但我们也要认识到它们的局限性。模拟算法往往基于假设和简化，可能无法完全精确地模拟现实情况。因此，在使用模拟算法时，我们需要谨慎地评估结果的可靠性，并结合领域知识和实际数据进行综合分析。

总而言之，模拟算法是一种强大的计算机算法，通过模拟目标对象的行为和规则来生成与真实情况相似的结果。它在科学研究、工程设计、优化和决策等领域中扮演着重要角色。通过善用模拟算法，我们可以更好地理解和应对复杂系统，为未来的发展和创新提供有力支持。