目录
一、模拟简介
模拟就是依葫芦画瓢，题目会将如何做给出来，直接做出来就行。
做题过程：
- 先模拟算法流程，
- 再将流程转化为代码。
二、1576.替换所有的问号
题目链接：1576.替换所有的问号
题目描述：
题目解析：
- 给我们一个字符串，每除字符’?‘外其它两个字符之间是不相等的，且字符全是小写字母和’?'。
- 将字符串中的’?'全部替换成小写字母。并保证两两不相等的条件。
解题思路：
- 我们直接模拟题目讲解的过程，
- 遍历字符串，找到’?'字符，就替换，
- 替换的时候，就从26个小写字母找跟’?'字符前后字符不相等的字符即可。
- 边界情况，在头是’?‘时，只需要跟后一个字符比较，在尾是’?'，只需要和前一个字符比较。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(n)
class Solution {
public String modifyString(String ss) {
char[] s = ss.toCharArray();
for(int i = 0; i < s.length; i++) {
if(s[i] == '?') {
for( char ch = 'a'; ch <= 'z'; ch++) {
if( (i == 0 || s[i-1] != ch) && (i == s.length-1 || s[i+1] != ch) ) {
s[i] = ch;
break;
}
}
}
}
return String.valueOf(s);
}
}
三、495.提莫攻击
题目链接：495.提莫攻击
题目描述：
题目解析：
- 给一个非递减数组，也就是从前往后元素要么相等，要么变大。
- 数组元素表示发起攻击，让艾希中毒的时刻。
- 在本来中毒期间，再次中毒，会刷新中毒时长。
- 求取艾希总中毒时长。
解题思路：
- 当下一次中毒时刻（也就是下一个元素），在上一次中毒效果区间内也就是 [t, t + duration - 1]，那么，就要刷新时长，不在就将中毒效果吃满。
- 刷新时长前我们记录下这次会中毒的时间也就是timeSeries[i+1] - timeSeries[i]。
- 到最后一个元素一定会吃满中毒效果（中毒时间为duration）。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int findPoisonedDuration(int[] timeSeries, int duration) {
int ret = 0;
for(int i = 0; i < timeSeries.length - 1; i++) {
if(timeSeries[i+1] <= timeSeries[i] + duration - 1) {
ret += timeSeries[i+1] - timeSeries[i];
} else {
ret += duration;
}
}
ret += duration;
return ret;
}
}
四、6.N字形变换
题目链接：：6.N字形变换
题目描述：
题目解析：
- 将题目给的字符串，按照给定的行数，按照之形排列。
- 就以下标来举例：
解题思路：
- 根据上面的图我们找规律，第一行和最后一行的每个插入元素相差的个数是一样的2*numRows-2，这个就是公差d。
- 中间行：第⼀个数取值为⾏数，每组下标为(2n - 1, 2n)的数围绕（2numRows - 2）的倍数左右取值，(即第一个数是行数 i ,第二个数是公差 d - i，然后每个加公差向后走)。
细节处理：当numRows为1的时候，如果按照上面循环就陷入死循环了，直接返回原字符串即可。
解题代码：
//时间复杂度：O(n*m)
//空间复杂度：O(n)
import java.util.*;
class Solution {
public String convert(String s, int numRows) {
StringBuffer ret = new StringBuffer();
int n = s.length();//数组长
int d = 2 * numRows - 2; //公差d
if(numRows == 1) return s;
//第一行
for(int i = 0; i < n; i += d) {
ret.append(s.charAt(i));
}
//中间行
for(int i = 1; i < numRows - 1; i++) {
for(int j = i, k = d-i; j < n || k < n; j += d, k += d) {
if(j < n) ret.append(s.charAt(j));
if(k < n) ret.append(s.charAt(k));
}
}
//最后一行
for(int i = numRows-1; i < n; i += d) {
ret.append(s.charAt(i));
}
return ret.toString();
}
}
五、38.外观数列
题目链接：38.外观数列
题目描述：
题目解析：
- 行程长度编码：就是将字符串从前向后遍历，连续相同的字符合并为个数+字符形式，单独字符个数为1。
- 第n个的字符串就是n-1的结果，n等于1的结果就是1。
解题思路：
- 递归调用，递归结束条件就是n为1的时候。
- 其他先拿到字符串countAndSay(n-1)。
- 在使用滑动窗口，
-
- 进窗口条件：right < len && s[right] == s[left]
-
- 出窗口条件：不满足进窗口时。
-
- 出窗口：left = right
-
- 更改结果：在出窗口前更改。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public String countAndSay(int n) {
if(n == 1) return "1";
char[] s = countAndSay(n-1).toCharArray();
int len = s.length;
StringBuffer ret = new StringBuffer();
int count = 0;
for(int left = 0, right = 0; right < len;) {
//进窗口
while(right < len && s[right] == s[left]) {
right++;
}
//更改结果
ret.append(right - left);
ret.append(s[left]);
//出窗口
left = right;
}
return ret.toString();
}
}
六、1419.数⻘蛙
题目链接：1419.数⻘蛙
题目描述：
题目解析：
- 返回实现croak最少得青蛙个数（也就是croak中有多少是穿插进行）。
解题思路：
- 当遇到’r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候，我们要去看看每⼀个字符对应的前驱字符，有没有⻘蛙叫出来。如果有⻘蛙叫出来，那就让这个⻘蛙接下来喊出来这个字符；如果没有，直接返回-1 ；
- 当遇到’c’ 这个字符的时候，我们去看看’k’ 这个字符有没有⻘蛙叫出来。如果有，就让这个⻘蛙继续去喊’c’ 这个字符；如果没有的话，就重新搞⼀个⻘蛙。
- 细节处理：
-
- 可能最后croak没走完，没进行到k。croakOfFrogs = “croakcroa”。
-
- 可能有多个c，croakOfFrogs = “cccccccrrooaakk”。
- 可以加一个for循环判断，也可以使用判断长度处理细节1，再判断一下hash[ 0 ]即可。
解题代码：
//时间复杂度：O(n)
//空间复杂度：O(1)
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
if(croakOfFrogs.length() % 5 != 0) return -1;
int[] hash = new int[5];
for(int i = 0; i < croakOfFrogs.length(); i++) {
if(croakOfFrogs.charAt(i) == 'c') {
if(hash[4] > 0) hash[4]--;
hash[0]++;
}else if(croakOfFrogs.charAt(i) == 'r') {
if(hash[0] == 0) return -1;
hash[0]--;
hash[1]++;
} else if(croakOfFrogs.charAt(i) == 'o') {
if(hash[1] == 0) return -1;
hash[1]--;
hash[2]++;
} else if(croakOfFrogs.charAt(i) == 'a') {
if(hash[2] == 0) return -1;
hash[2]--;
hash[3]++;
} else {
if(hash[3] == 0) return -1;
hash[3]--;
hash[4]++;
}
}
// for(int i = 0; i < 4; i++) {
// if(hash[i] != 0) return -1;
// }
return hash[0] != 0 ? -1 : hash[4];
}
}
//时间复杂度：O(n*m)
//空间复杂度：O(n)
import java.util.*;
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
if(croakOfFrogs.length() % 5 != 0) return -1;
int[] hash = new int[5];
String s = "croak";
Map<Character, Integer> index = new HashMap<>();
for(int i = 0; i < s.length(); i++) {
index.put(s.charAt(i), i);
}
for(int i = 0; i < croakOfFrogs.length(); i++) {
if(croakOfFrogs.charAt(i) == s.charAt(0)) {
if(hash[4] > 0) hash[4]--;
hash[0]++;
} else {
int in = index.get(croakOfFrogs.charAt(i));
if(hash[in-1] == 0) return -1;
hash[in-1]--;
hash[in]++;
}
}
// for(int i = 0; i < 4; i++) {
// if(hash[i] != 0) return -1;
// }
return hash[0] != 0 ? -1 : hash[4];
}
}