Java 模拟算法实战：经典题型深度解析

复杂度分析：时间复杂度 O(n)，空间复杂度 O(n)。每个字符最多尝试 26 次，常数级操作。

提莫攻击

题目核心：计算中毒总时长。技能有持续时间，若新技能在旧技能结束前释放，则重叠部分只算一次。

这里有一个常见的思维陷阱：直接累加每次技能的 duration 会重复计算重叠时间。正确的做法是判断两次攻击的时间差。如果间隔大于等于持续时间，说明上一次攻击已完全生效；否则，只能加上时间差值。最后别忘了加上最后一次攻击的完整持续时间。

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;
        
        int total = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            int diff = timeSeries[i] - timeSeries[i - 1];
            // 取时间差和持续时间的较小值
            total += Math.min(diff, duration);
        }
        // 加上最后一次攻击的完整持续时间
        return total + duration;
    }
}

复杂度分析：时间复杂度 O(n)，只需遍历一次数组。空间复杂度 O(1)。

Z 字形变换

题目核心：将字符串按 Z 字形排列后，按行读取成新字符串。

暴力解法是构建二维矩阵，但这会浪费大量空间。观察规律可以发现，字符的行索引变化呈现周期性：从上到下再折返。周期长度为 2 * numRows - 2。利用这个公差，我们可以直接通过下标公式定位每一行的字符，无需额外存储结构。

注意当行数小于 2 时，Z 字形退化为一行，直接返回原字符串即可。

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

复杂度分析：时间复杂度 O(n)，每个字符访问一次。空间复杂度 O(n) 用于存储结果。

外观数列

题目核心：第 n 项是对第 n-1 项的描述（如 1 -> 11 -> 21...）。

这是一个典型的递归转迭代问题。我们需要用双指针来统计连续相同字符的数量。左指针标记当前字符开始位置，右指针向后移动直到遇到不同字符或到达末尾，此时记录数量并追加字符内容。

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

数青蛙

题目核心：给定一串 croak 混合字符串，求最少需要多少只青蛙才能完成所有叫声。

这本质上是一个状态机问题。每只青蛙必须按 c -> r -> o -> a -> k 的顺序发声。我们可以维护五个计数器，分别代表当前处于各个状态的青蛙数量。当遇到某个字符时，检查其前驱状态是否有可用的青蛙：如果有，该青蛙进入下一状态；如果没有，则需要新起一只青蛙（仅针对 c）。最终所有青蛙都应回到初始状态（即 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;
                default: return -1;
            }
            maxFrogs = Math.max(maxFrogs, c + r + o + a + k);
        }
        
        return (c == 0 && r == 0 && o == 0 && a == 0) ? k : -1;
    }
}

优化思路：上述代码使用独立变量清晰展示了状态流转。在实际工程中，若状态较多，可改用数组 count[5] 配合字符映射表来减少冗余代码。

模拟算法虽然看似简单，但往往是考察工程严谨性的试金石。掌握这些基础模式，有助于在处理复杂业务逻辑时快速定位问题边界。