Java 模拟算法实战：LeetCode 经典题解

时间复杂度： O(n)，其中 n 为字符串长度。 空间复杂度： O(n)，用于存储字符数组。

提莫攻击

题目： 提莫会对艾希释放技能，让艾希处于中毒状态，求出中毒的总时间。

思路解析： 这是一个典型的区间合并问题。每次攻击持续 duration 时间。如果下一次攻击的时间点在当前攻击结束之前，那么中毒时间会被重叠覆盖。我们只需要比较当前攻击与上一次攻击的时间差：

1. 如果时间差 >= duration，说明上次攻击已完全结束，累加 duration。
2. 如果时间差 < duration，说明上次攻击被中断，只累加时间差。 最后别忘了加上最后一次攻击的完整持续时间。

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;
        
        int sum = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            int diff = timeSeries[i] - timeSeries[i - 1];
            // 取实际生效时间：要么持续 duration，要么就是间隔时间
            sum += Math.min(diff, duration);
        }
        // 加上最后一次攻击的完整持续时间
        return sum + duration;
    }
}

时间复杂度： O(n) 空间复杂度： O(1)

Z 字形变换

题目： 给定一个字符串和一个行数 numRows，将其按 Z 字形排列后，按行读取生成新字符串。

思路解析： 直接构建二维矩阵会消耗过多空间。观察规律可以发现，字符是按周期变化的。一个完整的 Z 字周期长度为 2 * numRows - 2。

1. 第一行和最后一行比较简单，每隔一个周期取一个字符。
2. 中间行每周期有两个字符，一个是正向斜下的，一个是反向斜上的。 注意当 numRows < 2 时，直接返回原字符串即可。

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

时间复杂度： O(n) 空间复杂度： O(n)

外观数列

题目： 第 n 项是对第 n-1 项的描述。例如 1 -> 11 -> 21 -> 1211...

思路解析： 使用双指针法遍历上一行的字符串。左指针指向当前数字的起始位置，右指针向右移动直到遇到不同数字。统计相同数字的个数，拼接'个数 + 数字'作为下一行的内容。

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

数青蛙

题目： 给定一个字符串 croakOfFrogs，求最小青蛙数量。完整的 croak 才算一次叫声，若无法组成完整 croak 则返回 -1。

思路解析： 这本质上是一个状态机问题。字符 c -> r -> o -> a -> k 代表青蛙叫声的不同阶段。每当出现 'k'，说明有一只青蛙完成了叫声，可以复用；否则需要增加新的青蛙。我们需要记录当前各个阶段正在叫的青蛙数量。

方案一：变量计数 直接用 5 个变量分别记录 c, r, o, a, k 的数量。遇到前驱字符时检查是否有对应状态的青蛙可用。

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if (croakOfFrogs.length() % 5 != 0) return -1;
        
        int c = 0, r = 0, o = 0, a = 0, k = 0;
        int maxFrogs = 0;
        
        for (char ch : croakOfFrogs.toCharArray()) {
            switch (ch) {
                case 'c':
                    if (k > 0) { k--; c++; } else { c++; }
                    break;
                case 'r':
                    if (c == 0) return -1; c--; r++; break;
                case 'o':
                    if (r == 0) return -1; r--; o++; break;
                case 'a':
                    if (o == 0) return -1; o--; a++; break;
                case 'k':
                    if (a == 0) return -1; a--; k++; break;
            }
            maxFrogs = Math.max(maxFrogs, c + r + o + a);
        }
        
        return (c == 0 && r == 0 && o == 0 && a == 0) ? k : -1;
    }
}

方案二：哈希映射 使用数组模拟哈希表，通过字符下标关系来管理状态流转，代码更紧凑。

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        String t = "croak";
        int n = t.length();
        int[] hash = new int[n];
        Map<Character, Integer> map = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            map.put(t.charAt(i), i);
        }
        
        for (char ch : croakOfFrogs.toCharArray()) {
            int index = map.get(ch);
            if (index == 0) {
                // 如果是 c，检查是否有完成叫声的青蛙可复用
                if (hash[n - 1] > 0) hash[n - 1]--;
                hash[0]++;
            } else {
                // 中间字符，必须依赖前驱状态
                if (hash[index - 1] == 0) return -1;
                hash[index - 1]--;
                hash[index]++;
            }
        }
        
        // 检查是否所有青蛙都完成了叫声
        for (int i = 0; i < n - 1; i++) {
            if (hash[i] != 0) return -1;
        }
        return hash[n - 1];
    }
}

总结： 模拟算法重在细节。无论是边界检查还是状态流转，都需要仔细验证。建议在实际编码前先画出流程图或状态转换图。