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

• 时间复杂度：O(n)，每个字符最多尝试 26 次。
• 空间复杂度：O(n)，用于存储字符数组。

提莫攻击

题目描述：给定攻击时间序列 timeSeries 和中毒持续时间 duration，计算艾希总共处于中毒状态的时间。

思路解析：这是一个区间合并的问题。如果两次攻击的时间间隔大于等于 duration，说明前一次中毒效果已完全结束；否则，前一次中毒被后一次打断，实际贡献时间为时间差值。最后别忘了加上最后一次攻击的完整持续时间。

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

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

Z 字形变换

题目描述：将字符串按照 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) {
                if (i + row < n) {
                    sb.append(s.charAt(i + row));
                }
                if (i + cycleLen - row < n) {
                    sb.append(s.charAt(i + cycleLen - row));
                }
            }
        }
        
        // 最后一行
        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;
    }
}

数青蛙

题目描述：给定字符串 croakOfFrogs，求最少需要多少只青蛙才能发出这些叫声。如果字符串无效则返回 -1。

思路解析：这本质上是一个状态机问题。每只青蛙必须按顺序发出 c->r->o->a->k。我们需要跟踪每种字符出现的次数。当遇到 c 时，优先复用已经叫完 k 的青蛙；遇到其他字符时，必须确保其前驱字符有可用的青蛙。最终所有青蛙都必须完成叫声（即 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--;
                    else maxFrogs++;
                    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;
            }
        }
        
        return (c == 0 && r == 0 && o == 0 && a == 0) ? maxFrogs : -1;
    }
}

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