Java 模拟算法实战：LeetCode 经典题解 | 极客日志

Javajava算法

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

本文通过五个典型 LeetCode 案例，深入讲解 Java 中的模拟算法。涵盖字符替换边界处理、时间区间重叠计算、Z 字形变换规律推导、外观数列生成逻辑以及青蛙叫声状态机模拟。重点在于细节把控与数学规律挖掘，提供可直接运行的优化代码及复杂度分析，帮助读者掌握模拟类问题的通用解题思路。

RefactorPro发布于 2026/3/240 浏览

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

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

模拟算法的核心在于严格按照题目描述的规则进行一步步操作。这类问题通常逻辑直观，但容易在边界条件和细节处理上出错。下面我们通过五个典型例题，梳理解题思路与代码实现。

替换所有的问号

题目描述：将字符串 s 中的所有 ? 替换为小写字母，要求替换后的字符不能与其相邻的字符相同。

思路解析：遍历字符串，遇到 ? 时尝试从 a 到 z 寻找一个不与左右邻居冲突的字符即可。这里需要特别注意首尾两个边界情况，即第一个字符只检查右边，最后一个字符只检查左边。

class Solution {
    public String modifyString(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        
        for (int i = 0; i < n; i++) {
            if (chars[i] == '?') {
                // 尝试 a-z 找到不重复的字符
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    boolean leftOk = (i == 0 || chars[i - 1] != ch);
                    boolean rightOk = (i == n - 1 || chars[i + 1] != ch);
                    
                    if (leftOk && rightOk) {
                        chars[i] = ch;
                        break;
                    }
                }
            }
        }
        return new (chars);
    }
}

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;
    }
}

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();
    }
}

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;
    }
}

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;
    }
}