模拟算法实战：替换问号、提莫攻击、N 字形变换、外观数列与数青蛙

1. 替换所有的问号（LC1576）

题目描述

解题思路

按照题目要求，双层循环，外层遍历字符串；内层从 a 到 z 依次尝试，与前后不等则填入。

代码实现

public String modifyString(String s) {
    char[] ss = s.toCharArray();
    int n = ss.length;
    for (int i = 0; i < n; i++) {
        if (ss[i] != '?') continue;
        for (char ch = 'a'; ch <= 'z'; ch++) {
            if ((i == 0 || ch != ss[i - 1]) && (i == n - 1 || ch != ss[i + 1])) {
                ss[i] = ch;
                break;
            }
        }
    }
    return new String(ss);
}

2. 提莫攻击（LC495）

题目描述

解题思路

计算两次'受到攻击'之间的差值 x：

• x >= d，则 ret += d
• x < d，则 ret += x

最后要加上一个 d，表示最后一次'攻击'的时间。

代码实现

public int findPoisonedDuration(int[] timeSeries, int duration) {
    int ret = 0;
    for (int i = 1; i < timeSeries.length; i++) {
        int x = timeSeries[i] - timeSeries[i - 1];
        ret += (x >= duration) ? duration : x;
    }
    ret += duration;
    return ret;
}

3. N 字形变换（LC6）

题目描述

解题思路

• 解法二：依据模拟过程找规律，把字符的下标模拟到矩阵中：
  • 第 0 行：公差就是一个周期中字符个数 d = n + n - 2 = 2n - 2
    • 0 -> 0+d -> 0+2d -> 0+3d -> …-> 0+kd
  • 第 i 行：一个周期内有两个元素
    • i -> i+d -> i+2d -> … -> i+kd
    • d - i -> d - i +d -> d - i + 2d -> … -> d - i + kd
  • 第 n-1 行:
    • n-1 -> n-1+d -> n-1+2d -> …-> n-1+kd

解法一：创建二维数组，按照 N 形依次填入。时间复杂度和空间复杂度都是字符串长度 * numRow。

注意： n=1 直接返回原字符串，按照上面的规律会陷入死循环。

代码实现

public String convert(String s, int numRows) {
    if (numRows == 1) return s;
    StringBuilder ret = new StringBuilder();
    int n = s.length();
    int d = 2 * numRows - 2; // 公差
    int n1 = (n + d - 1) / d; // 周期个数，向上取整
    
    // 第 0 行
    for (int k = 0; k < n1; k++) ret.append(s.charAt(k * d));
    
    // 中间行
    for (int i = 1; i < numRows - 1; i++) {
        for (int k = 0; k < n1; k++) {
            if (i + k * d < n) ret.append(s.charAt(i + k * d));
            if (d - i + k * d < n) ret.append(s.charAt(d - i + k * d));
        }
    }
    
    // 最后一行
    for (int k = 0; k < n1; k++) {
        if (numRows - 1 + k * d < n) ret.append(s.charAt(numRows - 1 + k * d));
    }
    return ret.toString();
}

4. 外观数列（LC38）

题目描述

解题思路

利用双指针来模拟过程：left，right 初始为 0

• right 向右移动，直到与 left 指向的字符不同，停止移动
• right - left 就是中间的个数，接着 left 移动到 right 的位置，循环这个过程

代码实现

public String countAndSay(int n) {
    String s = "1";
    for (int i = 1; i < n; i++) {
        StringBuilder tmp = new StringBuilder();
        int len = s.length();
        int count = 0;
        for (int left = 0, right = 0; right < len;) {
            while (right < len && s.charAt(left) == s.charAt(right)) right++;
            tmp.append(String.valueOf(right - left));
            tmp.append(s.charAt(left));
            left = right;
        }
        s = tmp.toString();
    }
    return s;
}

5. 数青蛙（LC1419）

题目描述

解题思路

使用哈希表来存 c r o a k 每个字符：

• 遇到 r o a k 这四个字符的时候，看每一个字符对应的前驱字符，有没有青蛙叫出来。如果有青蛙叫出来，那就让这个青蛙接下来喊出来这个字符；如果没有，直接返回 -1；
• 遇到 c 这个字符的时候，看'k'这个字符有没有青蛙叫出来。如果有，就让这个青蛙继续去喊 c 这个字符；如果没有，就重新搞一个青蛙。

代码实现

public int minNumberOfFrogs(String c) {
    char[] croakOfFrogs = c.toCharArray();
    int[] croak = new int[5];
    String s = "croak";
    Map<Character, Integer> index = new HashMap<>();
    for (int i = 0; i < 5; i++) index.put(s.charAt(i), i);
    
    for (char ch : croakOfFrogs) {
        if (ch == 'c') {
            if (croak[4] != 0) croak[4]--;
            croak[0]++;
        } else {
            int i = index.get(ch);
            if (croak[i - 1] != 0) {
                croak[i - 1]--;
                croak[i]++;
            } else {
                return -1;
            }
        }
    }
    
    for (int i = 0; i < 4; i++) {
        if (croak[i] != 0) return -1;
    }
    return croak[4];
}