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

Javajava算法

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

本文通过五道 LeetCode 经典题目深入讲解 Java 模拟算法。涵盖替换问号、提莫攻击、Z 字形变换、外观数列及数青蛙五个案例。重点分析了边界条件处理、时间重叠计算、数学规律推导、双指针迭代以及状态机计数等核心技巧。代码经过规范化整理，附带详细思路解析与复杂度分析，适合希望提升算法细节把控能力的开发者参考。

DevStack发布于 2026/3/21更新于 2026/4/251 浏览

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

Java 模拟算法实战

模拟算法的核心在于严格按照题目描述进行步骤操作。这类问题通常逻辑直观，但容易在边界条件和细节处理上出错。下面通过五道经典题目，梳理一下模拟算法的常见套路和注意事项。

替换所有的问号

题目核心 将字符串中的 ? 替换为小写字母，要求替换后的字符不能与相邻字符重复。

思路解析 遍历字符串，遇到 ? 时尝试从 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  (chars);
    }
}

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        if (timeSeries.length == 0) return 0;
        
        int totalDuration = 0;
        for (int i = 1; i < timeSeries.length; i++) {
            int diff = timeSeries[i] - timeSeries[i - 1];
            // 取间隔和持续时间的较小值
            totalDuration += Math.min(diff, 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 k = 1; k < numRows - 1; k++) {
            for (int i = k, j = cycleLen - k; i < n || j < n; i += cycleLen, j += cycleLen) {
                if (i < n) sb.append(s.charAt(i));
                if (j < n) sb.append(s.charAt(j));
            }
        }
        
        // 最后一行
        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 current = "1";
        
        for (int i = 1; i < n; i++) {
            StringBuilder next = new StringBuilder();
            int len = current.length();
            int left = 0, right = 0;
            
            while (right < len) {
                // 移动右指针直到字符不同
                while (right < len && current.charAt(left) == current.charAt(right)) {
                    right++;
                }
                // 记录个数和字符
                next.append(right - left).append(current.charAt(left));
                left = right;
            }
            current = next.toString();
        }
        return current;
    }
}

class Solution {
    public int minNumberOfFrogs(String croakOfFrogs) {
        if (croakOfFrogs.length() % 5 != 0) return -1;
        
        // 使用数组模拟状态计数，对应 c, r, o, a, k
        int[] count = new int[5];
        int frogs = 0;
        int maxFrogs = 0;
        
        for (char ch : croakOfFrogs.toCharArray()) {
            int index = getCharIndex(ch);
            if (index == 0) {
                // 开始叫，青蛙数量 +1
                count[0]++;
                frogs++;
                maxFrogs = Math.max(maxFrogs, frogs);
            } else {
                // 检查前驱是否存在
                if (count[index - 1] == 0) return -1;
                count[index - 1]--;
                count[index]++;
                
                if (index == 4) {
                    // 叫完，青蛙数量 -1
                    frogs--;
                }
            }
        }
        
        // 检查是否所有青蛙都叫完了
        return frogs == 0 ? maxFrogs : -1;
    }
    
    private int getCharIndex(char ch) {
        switch (ch) {
            case 'c': return 0;
            case 'r': return 1;
            case 'o': return 2;
            case 'a': return 3;
            case 'k': return 4;
            default: return -1;
        }
    }
}