目录一、模拟题的核心把自然语言拆成状态变化二、题目一替换所有的问号三、题目二提莫攻击四、题目三N 字形变换五、题目四外观数列六、题目五数青蛙七、5 道模拟题中可以总结出的规律规律一题目描述中的“每一步”就是循环的一轮规律二需要修改字符串时使用 char[]规律三需要频繁拼接字符串时使用 StringBuilder规律四连续相同字符可以使用左右两个指针规律五多个对象交错完成固定流程可以记录每个阶段的数量规律六发现不可能时可以立即返回八、这 5 道题使用到的 Java 方法九、这一阶段的总结模拟题看起来不像排序、动态规划那样有明显的算法名称但它并不等于“没有算法”。这类题目通常把一个过程讲得很具体要求我们按照顺序维护状态并在每一步做出正确判断。这篇文章通过 5 道题整理我对模拟题的理解替换字符、计算重叠时间、处理字符串排列、连续字符分组以及多个对象交错完成固定流程。本文涉及的题目链接1576替换所有的问号495提莫攻击6N 字形变换38外观数列1419数青蛙一、模拟题的核心把自然语言拆成状态变化遇到模拟题时我现在会先问自己四个问题题目中的“一个对象”是什么是一个字符、一个时间段、一行字符还是一只正在叫的青蛙处理顺序是什么通常是从左到右也可能是根据上一轮结果继续生成下一轮结果。当前元素需要参考哪些信息可能是左邻居、右邻居、上一个时间点或者某个对象当前进行到哪一步。每次处理之后哪些信息要保留下来这些信息就是代码中的状态变量。模拟题的基本代码结构通常如下初始化状态; 遍历输入; 根据当前元素分情况; 修改状态; 发现不可能时及时返回; 返回最终结果;这类题最容易错的地方往往是边界和顺序。例如访问一个字符的左边和右边时必须先判断当前位置是不是第一个或最后一个字符从右边交换元素时换过来的元素还没有检查指针就不能急着向后移动。二、题目一替换所有的问号1. 题目描述给定一个只包含小写字母和问号?的字符串把所有问号替换成小写字母使最终字符串中不存在连续相同的字符。原本不是问号的字符不能修改。例如输入?zs 输出azs 输入ubv?w 输出ubvaw题目链接1576替换所有的问号2. 算法思路从左到右遍历字符串只有遇到?时才需要处理。对于一个问号从a到z依次尝试字母。候选字符合法需要满足两个条件如果左边有字符候选字符不能和左边相同如果右边有字符候选字符不能和右边相同。写成判断条件就是(i 0 || ch ! s[i - 1]) (i n - 1 || ch ! s[i 1])只检查左右邻居就足够了因为新放入下标i的字符只可能和相邻位置形成连续重复。3. 为什么要先转换成char[]Java 的String创建以后不能直接修改其中的某个字符。例如不能直接写ss[i] ch;所以需要把字符串转换成字符数组char[] s ss.toCharArray();字符数组中的元素可以通过下标修改s[i] ch;4. Java 代码class Solution { public String modifyString(String ss) { char[] s ss.toCharArray(); int n s.length; for(int i 0; i n; i) { if(s[i] ?) { for(char ch a; ch z; ch) { if((i 0 || ch ! s[i - 1]) (i n - 1 || ch ! s[i 1])) { s[i] ch; break; } } } } return String.valueOf(s); } }5. 边界为什么要写在前面如果i 0当前位置没有左边字符不能访问s[i - 1]否则会出现数组下标越界。如果i n - 1当前位置没有右边字符不能访问s[i 1]。因此代码先判断i 0或者i n - 1这些条件成立时就不再访问不存在的位置。6. 复杂度每个位置最多尝试 26 个字母时间复杂度是O(26n)通常写作O(n)。字符数组需要O(n)的额外空间。三、题目二提莫攻击1. 题目描述提莫在timeSeries[i]秒攻击一次每次攻击会让对方中毒duration秒。如果下一次攻击发生在上一次中毒结束之前中毒时间会重叠重叠部分只能计算一次。例如timeSeries [1, 2] duration 2第一次攻击覆盖第 1、2 秒第二次攻击覆盖第 2、3 秒总中毒时间是 3 秒而不是 4 秒。题目链接495提莫攻击2. 算法思路对于相邻两次攻击计算它们的时间差int x timeSeries[i] - timeSeries[i - 1];有两种情况如果x duration说明两次中毒没有重叠上一次完整贡献duration秒如果x duration说明两次中毒重叠上一次只能贡献x秒。代码中循环处理每一次攻击与下一次攻击之间的新增时间。最后一次攻击后面没有下一次攻击覆盖所以一定完整贡献duration秒。3. Java 代码class Solution { public int findPoisonedDuration(int[] timeSeries, int duration) { int ret 0; for(int i 1; i timeSeries.length; i) { int x timeSeries[i] - timeSeries[i - 1]; if(x duration) { ret duration; } else { ret x; } } // 最后一次攻击一定完整贡献 duration 秒 return ret duration; } }4. 这道题的规律这是一种常见的“相邻区间贡献”写法。每次不直接计算整个区间而是只计算从上一次开始到下一次开始之间新增加的那部分。同样的逻辑也可以写成ret Math.min(x, duration);Math.min(x, duration)的意思是取x和duration中较小的那个数。为了更清楚地体现题目中的两种情况使用if-else版本更容易理解。5. 复杂度只遍历时间数组一次时间复杂度是O(n)额外空间复杂度是O(1)。四、题目三N 字形变换1. 题目描述把字符串按照给定的行数以从上到下、从左到右的方式排列成 N 字形然后逐行读取。例如输入s PAYPALISHIRINGnumRows 3排列结果是P A H N A P L S I I G Y I R逐行读取以后得到PAHNAPLSIIGYIR题目链接6N 字形变换2. 算法思路如果真的创建一个二维字符表写法比较直观但会浪费空间。这里直接观察每一行字符下标的规律。当行数为numRows时一个完整的 N 字形周期长度是d 2 * numRows - 2;例如行数为 4 时一个周期有 6 个字符。根据每一行的位置把结果分成三部分处理第一行每隔一个周期取一个字符中间行每个周期有两个字符最后一行每隔一个周期取一个字符。3. Java 代码class Solution { public String convert(String s, int numRows) { // 只有一行时字符串不需要变化 if(numRows 1) return s; int d 2 * numRows - 2; int n s.length(); 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 - i; 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(); } }4.numRows 1为什么必须单独处理如果numRows 1周期长度是2 * 1 - 2 0如果不提前返回循环每次增加 0程序就会一直停留在原位置。因此这是一个必须处理的边界情况。5.StringBuilder是什么StringBuilder是 Java 中用来高效拼接字符串的类。常见写法是StringBuilder ret new StringBuilder(); ret.append(a); ret.append(bc); String result ret.toString();append()表示追加内容toString()表示把它转换成普通字符串。6. 复杂度每个字符最多被加入结果一次时间复杂度是O(n)。结果字符串本身需要保存所有字符空间复杂度是O(n)。五、题目四外观数列1. 题目描述从数字字符串1开始下一项是对上一项的描述。前几项如下1 11 21 1211 111221具体来说1 - 一个 1 - 11 11 - 两个 1 - 21 21 - 一个 2 一个 1 - 1211题目链接38外观数列2. 算法思路设置String ret 1;然后重复n - 1次每次读取当前字符串并生成下一项。读取当前字符串时把连续相同的字符看成一组。使用两个指针left当前连续字符组的起点right向右扫描直到遇到不同字符。当前组的数量是right - left当前组的字符是ret.charAt(left)把数量和字符依次追加到新的字符串中。3. Java 代码class Solution { public String countAndSay(int n) { String ret 1; // 从第 1 项生成到第 n 项需要生成 n - 1 次 for(int i 1; i n; i) { StringBuilder tmp new StringBuilder(); int len ret.length(); for(int left 0, right 0; right len; ) { while(right len ret.charAt(left) ret.charAt(right)) { right; } tmp.append(Integer.toString(right - left)); tmp.append(ret.charAt(left)); left right; } ret tmp.toString(); } return ret; } }4. 为什么使用[left, right)这一段在代码中当前连续组包括left但不包括right。例如字符串1 2 2 2 3 下标 0 1 2 3 4当left 1、right 4时当前连续组是下标[1, 4)也就是2、2、2数量正好是right - left 3right已经指向下一组的开头所以处理完当前组以后直接写left right;即可开始处理下一组。5. 复杂度每一轮都要扫描上一轮得到的字符串并且字符串长度会发生变化因此不能简单地只写成一次O(n)。这道题需要保存当前字符串和下一轮字符串空间主要来自StringBuilder。六、题目五数青蛙1. 题目描述一只青蛙必须依次发出c、r、o、a、k给定一个由多个青蛙叫声混合而成的字符串返回同时需要的最少青蛙数量。如果字符串不是若干个完整的croak混合而成返回-1。例如输入croakcroak 输出1 输入crcoakroak 输出2 输入croakcrook 输出-1题目链接1419数青蛙2. 算法思路可以把一只青蛙的叫声过程分成 5 个状态状态 0已经发出 c等待 r 状态 1已经发出 cr等待 o 状态 2已经发出 cro等待 a 状态 3已经发出 croa等待 k 状态 4刚刚完成 croak使用数组hash记录处于每个状态的青蛙数量int[] hash new int[5];处理字符时遇到c优先让已经完成croak的青蛙重新开始如果没有可以复用的青蛙就需要一只新青蛙遇到r、o、a、k必须有青蛙处在它的前一个状态否则字符串不合法遍历结束后如果还有青蛙停留在中间状态说明叫声没有完成也是不合法的。3. Java 代码import java.util.HashMap; import java.util.Map; class Solution { public int minNumberOfFrogs(String c) { char[] croakOfFrogs c.toCharArray(); String t croak; int n t.length(); int[] hash new int[n]; MapCharacter, Integer index new HashMap(); // 记录 c、r、o、a、k 在 t 中的位置 for(int i 0; i n; i) { index.put(t.charAt(i), i); } for(char ch : croakOfFrogs) { if(ch t.charAt(0)) { // 已经完成 croak 的青蛙可以重新使用 if(hash[n - 1] ! 0) hash[n - 1]--; hash[0]; } else { int i index.get(ch); // 必须有青蛙处在前一个状态 if(hash[i - 1] 0) return -1; hash[i - 1]--; hash[i]; } } // 不能有青蛙停在 croak 中间 for(int i 0; i n - 1; i) { if(hash[i] ! 0) return -1; } return hash[n - 1]; } }4.Map和HashMap是什么Map可以保存“键和值”的对应关系。例如MapCharacter, Integer index new HashMap(); index.put(c, 0); index.put(r, 1);之后可以通过int i index.get(ch);找到字符对应的状态编号。HashMap是Map的一种常用实现。put()用来保存对应关系get()用来根据键取值。5. 复杂度字符串只遍历一次croak的长度固定为 5因此时间复杂度是O(n)空间复杂度是O(1)。七、5 道模拟题中可以总结出的规律规律一题目描述中的“每一步”就是循环的一轮替换问号是从左到右处理每个字符提莫攻击是依次处理相邻时间数青蛙是依次处理叫声中的每个字母。先确定处理顺序代码结构就会清楚很多。规律二需要修改字符串时使用char[]char[] s ss.toCharArray();String适合读取char[]适合修改。规律三需要频繁拼接字符串时使用StringBuilderStringBuilder ret new StringBuilder(); ret.append(ch); return ret.toString();规律四连续相同字符可以使用左右两个指针外观数列中的left right分别表示连续字符组的开始和结束位置。right - left就是这一组的长度。规律五多个对象交错完成固定流程可以记录每个阶段的数量数青蛙并不是在模拟某一只具体的青蛙而是在统计“有多少只青蛙处于某一个阶段”。这是把复杂过程转成状态计数。规律六发现不可能时可以立即返回例如if(hash[i - 1] 0) return -1;如果当前字符无法由前一个状态转移过来后面继续处理也没有意义直接返回结果即可。八、这 5 道题使用到的 Java 方法s.length(); // 字符串长度 s.charAt(i); // 读取下标 i 的字符 s.toCharArray(); // 转为字符数组 String.valueOf(s); // 字符数组转回字符串 ret.append(x); // 追加字符或字符串 ret.toString(); // 转换成 String数组长度写法不同nums.length而不是nums.length()如果需要保存字符和数字的对应关系可以使用MapCharacter, Integer index new HashMap();九、这一阶段的总结模拟题真正要练习的不是“把题目原样翻译成代码”而是识别题目中隐藏的状态替换问号时状态是当前位置左右的字符提莫攻击时状态是相邻攻击之间新增了多少时间N 字形变换时状态是当前字符在一个周期中的位置外观数列时状态是一段连续相同字符的起点和终点数青蛙时状态是一只青蛙已经完成了croak的哪一部分。当题目看起来很长时我会先把过程拆成“当前看到了什么、当前允许做什么、做完以后状态变成什么”。这一步想清楚以后代码通常就是一个循环加上几种分情况处理。