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

关键点 最后一次攻击的持续时间一定会完整计入，因此循环结束后需要额外加上一次 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];
            // 取时间差和持续时间的较小值
            sum += Math.min(diff, duration);
        }
        // 加上最后一次技能的完整持续时间
        return sum + duration;
    }
}

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

Z 字形变换

题目思路 将字符串按 Z 字形排列后按行读取。直接构建二维矩阵效率较低，可以通过数学规律直接定位字符位置。Z 字形的周期是 2 * numRows - 2。

关键点 第一行和最后一行每个周期只出现一次，中间行每个周期会出现两次（一次向下，一次向上）。需注意 numRows < 2 的特殊情况。

class Solution {
    public String convert(String s, int numRows) {
        if (numRows < 2) return s;
        int n = s.length();
        int d = 2 * numRows - 2;
        StringBuilder ret = new StringBuilder();

        // 第一行
        for (int i = 0; i < n; i += d) {
            ret.append(s.charAt(i));
        }

        // 中间行
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n) ret.append(s.charAt(i));
                if (j < n) ret.append(s.charAt(j));
            }
        }

        // 最后一行
        for (int i = numRows - 1; i < n; i += d) {
            ret.append(s.charAt(i));
        }
        return ret.toString();
    }
}

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

外观数列

题目思路 每一行都是对上一行的描述。例如 "1" -> "11" (1 个 1) -> "21" (2 个 1)。可以使用双指针来统计连续相同字符的数量。

关键点 外层循环控制生成第几行，内层使用左右指针扫描当前字符串，记录连续字符个数并拼接结果。

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

数青蛙

题目思路 给定字符串，判断是否能由若干只青蛙发出完整的 "croak" 组成，求最少青蛙数量。这实际上是一个状态机问题，需要跟踪每个字母出现的顺序。

关键点

1. 字符串长度必须是 5 的倍数。
2. 必须按 c->r->o->a->k 的顺序匹配。
3. 当遇到 'c' 时，优先复用已经叫完 'k' 的青蛙，否则增加新青蛙。
4. 最后所有青蛙必须都完成叫声（即 '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 frogs = 0;
        
        for (char ch : croakOfFrogs.toCharArray()) {
            switch (ch) {
                case 'c':
                    if (k > 0) { k--; } else { frogs++; }
                    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) ? k : -1;
    }
}

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