模拟算法专题——算法介绍算法讲解力扣实战应用
目录
1、模拟算法介绍
2、算法应用【leetcode】
2.1 替换所有的问号
2.1.1 算法思想
2.1.2 算法代码
2.2 提莫攻击
2.2.1 算法思想
2.2.2 算法代码
2.3 Z字形变换
2.3.1 算法思想
2.3.2 算法代码
2.4 外观数列
2.4.1 算法思想
2.4.2 算法代码
2.5 数青蛙
2.5.1 算法思想
2.5.2 算法代码
1、模拟算法介绍
模拟算法其实就是——比葫芦画瓢。
模拟算法的思想很简单，解题思路一般在题目上就给了，我们只需用代码将题目的要求模拟出来就可以了，所以模拟算法对代码能力要求较强，模拟算法并没有固定的模版，我们只需将题目要求用代码模拟出来即可。
模拟算法是一种计算机算法，用于模拟或仿真现实世界中的某个过程、系统或现象。它通过运行一系列的步骤或规则来模拟目标对象的行为，并生成与真实情况相似的结果。
2、算法应用【leetcode】
2.1 替换所有的问号
. - 力扣（LeetCode）
2.1.1 算法思想
本题为简单模拟题，只需将字符'?'替换为前后不连续的字符即可。
- 从'a'~'z'中寻找字符，与i-1位置和i+1位置比较，判断是否出现连续的字符(字符重复)
- 注意：0下标处和n-1下标处要额外处理，避免越界访问
2.1.2 算法代码
class Solution {public String modifyString(String s) {char[] ss = s.toCharArray();int len = ss.length;for (int i = 0; i < len; i++) {//替换字符if (ss[i] == '?') {for (char j = 'a'; j < 'z'; j++) {if ((i == 0 || ss[i - 1] != j) && (i == len - 1 || ss[i + 1] != j) ) {ss[i] = j;break;}}}}return String.valueOf(ss);}
}2.2 提莫攻击
. - 力扣（LeetCode）
2.2.1 算法思想
计算出每两次发动攻击之间的时间差x，判断是否 >= 持续时间d秒：
- 若x >= d，则说明时间充裕，d秒时间内会一直中毒，中毒时间ret += d
- 若x < d，则说明时间不够，中毒时间会重复，中毒时间ret += 时间差x
- 最后一次攻击，时间必然充裕，必然中毒d秒，中毒时间ret += d
2.2.2 算法代码
class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {int ret = 0;for(int i = 0; i < timeSeries.length - 1; i++) {int x = timeSeries[i + 1] - timeSeries[i];if(x < duration) ret += x;else ret += duration;}//最后一次攻击，必然中毒d秒ret += duration;return ret;}
}2.3 Z字形变换
. - 力扣（LeetCode）
2.3.1 算法思想
在模拟算法中，若想要寻得时空效率高的算法，只能通过找规律来做优化。
我们将字符的下标放在矩阵中，求得公差d = 2*n - 2，且发现字符在矩阵中和下标有以下规律：
- ①：当k==0时(第一行)，k += d，拿到下一个要打印的字符的下标，直到k >= 字符串.len
- ②：当k == n-1时(最后一行)，k += d,拿到下一个要打印的字符的下标，直到k >= 字符串.len
- ③：当k为中间行时，k和d-k为一组，(k,d-k)-->(k+d,d-k+d)-->...，直到k >= 字符串.len
2.3.2 算法代码
class Solution {public String convert(String s, int numRows) {if (numRows == 1) return s;char[] ss = s.toCharArray();int len = ss.length;StringBuilder stringBuilder = new StringBuilder();int d = 2 * numRows - 2;//公差for (int i = 0; i < numRows; i++) {int k = i;if (k == 0) {while (k < len) {stringBuilder.append(ss[k]);k += d;}} else if (k == numRows - 1) {while (k < len) {stringBuilder.append(ss[k]);k += d;}} else {int k2 = d - k;while (k < len || k2 < len) {if (k < len) stringBuilder.append(ss[k]);if (k2 < len) stringBuilder.append(ss[k2]);k += d;k2 += d;}}}return stringBuilder.toString();}
}2.4 外观数列
. - 力扣（LeetCode）
2.4.1 算法思想
外观数列其实就是从2开始(1的外观数列就是1)用口头的语言将前一个数的表述出来，比如：
1 --> 1
2 --> 11（1个1）
3 --> 21（2个1）
4 --> 1211（1个2、1个1）
5 --> 111221（1个1、1个2、2个1）
....
使用双指针法求解：
- 从数字以1开始
- 定义left和right指针，起始位置均为0下标
- 当ret[right] != ret[left]时，记录长度(相同元素的个数)，且更新left = right，继续向后遍历，直至遍历完成当前字符串
- 更新ret字符串，更新数字，直至数字n，返回数字n的外观数列
2.4.2 算法代码
class Solution {public String countAndSay(int n) {String ret = "1";for(int i = 0; i < n - 1; i++) {StringBuilder sb = new StringBuilder();int left = 0, right = 0;int len = ret.length();while(right < len) {while(right < len && ret.charAt(right) == ret.charAt(left)) right++;sb.append(right - left);sb.append(ret.charAt(left));left = right;}ret = sb.toString();}return ret;}
}2.5 数青蛙
. - 力扣（LeetCode）
2.5.1 算法思想
- 若下标为1~4的字符(r、o、a、k)，则去哈希表中查看其前驱字符，若存在则：前驱个数--，当前字符个数++；若不存在：返回-1
- 若下标为0的字符(c)，说明蛙叫刚刚开始，查看最后一个字符的个数，若存在则：最后一个字符个数--，当前字符个数++； 若不存在则：当前字符++
- 注意：当遍历完成后，除最后一个字符外，哈希表中仍有其他字符存在个数，则不成立，返回-1
2.5.2 算法代码
class Solution {public int minNumberOfFrogs(String croakOfFrogs) {char[] s = croakOfFrogs.toCharArray();int n = "croak".length();int[] hash = new int[n];// 绑定字符和其下标Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < n; i++)map.put("croak".charAt(i), i);for (char ch : s) {int index = map.get(ch);if (index == 0) {if (hash[n - 1] != 0)hash[n - 1]--;hash[0]++;} else {if (hash[index - 1]-- == 0)return -1;hash[index]++;}}//除最后一个字符外，哈希表中仍有其他字符存在个数for (int i = 0; i < n - 1; i++) {if (hash[i] != 0)return -1;}return hash[n - 1];}
}END