目录
模拟算法概述
练习
练习1:替换所有的问号
练习2:提莫攻击
练习3:Z字形变换
模拟算法概述
模拟:根据题目要求的实现过程进行编程模拟,即题目要求什么就实现什么
解决这类题目,需要:
1. 根据题目要求模拟算法流程
2. 将算法流程转换为代码
接下来,我们以几道练习来进一步理解和掌握模拟算法
练习
练习1:替换所有的问号
题目链接:
1576. 替换所有的问号 – 力扣(LeetCode)
题目描述:
给你一个仅包含小写英文字母和'?'
字符的字符串s
,请你将所有的'?'
转换为若干小写字母,使最终的字符串不包含任何连续重复的字符。
注意:你不能修改非'?'
字符。
题目测试用例保证除'?'
字符之外,不存在连续重复的字符。
在完成所有转换(可能无需转换)后返回最终的字符串。如果有多个解决方案,请返回其中任何一个。可以证明,在给定的约束条件下,答案总是存在的。
示例 1:
输入:s = "?zs"输出:"azs"解释:该示例共有 25 种解决方案,从 "azs" 到 "yzs" 都是符合题目要求的。只有 "z" 是无效的修改,因为字符串 "zzs" 中有连续重复的两个 'z' 。
示例 2:
输入:s = "ubv?w"输出:"ubvaw"解释:该示例共有 24 种解决方案,只有替换成 "v" 和 "w" 不符合题目要求。因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符。
提示:
1 <= s.length<= 100
s
仅包含小写英文字母和'?'
字符
思路分析:题目要求我们将所有的?替换为小写字母,且不包含连续重复的字符,我们按照题目要求进行替换即可
接下来,我们模拟替换过程:
当” />
当?出现在中间时,需要判断所替换的字符是否与其前后字符相同,当所替换的字符不与前后字符相同时,即可替换
当” />class Solution {public String modifyString(String s) {char[] chs = s.toCharArray();int len = chs.length;for(int i = 0; i < len; i++){if(chs[i] == '?'){//当出现?,进行替换for(char ch = 'a'; ch <= 'z'; ch++){if((i == 0 || ch != chs[i-1]) && (i == len – 1 || ch != chs[i+1])){//注意处理?出现在第一位或最后一位的情况chs[i] = ch;break;}}}}return new String(chs);}}
练习2:提莫攻击
题目链接:
495. 提莫攻击 – 力扣(LeetCode)
题目描述:
在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。
当提莫攻击艾希,艾希的中毒状态正好持续duration
秒。
正式地讲,提莫在t
发起攻击意味着艾希在时间区间[t, t + duration - 1]
(含t
和t + duration - 1
)处于中毒状态。如果提莫在中毒影响结束前再次攻击,中毒状态计时器将会重置,在新的攻击之后,中毒影响将会在duration
秒后结束。
给你一个非递减的整数数组timeSeries
,其中timeSeries[i]
表示提莫在timeSeries[i]
秒时对艾希发起攻击,以及一个表示中毒持续时间的整数duration
。
返回艾希处于中毒状态的总秒数。
示例 1:
输入:timeSeries = [1,4], duration = 2输出:4解释:提莫攻击对艾希的影响如下:- 第 1 秒,提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒,即第 1 秒和第 2 秒。- 第 4 秒,提莫再次攻击艾希,艾希中毒状态又持续 2 秒,即第 4 秒和第 5 秒。艾希在第 1、2、4、5 秒处于中毒状态,所以总中毒秒数是 4 。
示例 2:
输入:timeSeries = [1,2], duration = 2输出:3解释:提莫攻击对艾希的影响如下:- 第 1 秒,提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒,即第 1 秒和第 2 秒。- 第 2 秒,提莫再次攻击艾希,并重置中毒计时器,艾希中毒状态需要持续 2 秒,即第 2 秒和第 3 秒。艾希在第 1、2、3 秒处于中毒状态,所以总中毒秒数是 3 。
提示:
1 <= timeSeries.length <= 104
0 <= timeSeries[i], duration <= 107
timeSeries
按非递减顺序排列
思路分析:在t时刻发起攻击后,进入中毒状态,duration 时间后解除,而在 duration 时间内又发起攻击,则在发起攻击时刻重新计时,过程如下图所示:
我们可以计算出两次攻击的间隔时间:d = t2 – t1
当d >= duration时,在两次攻击间隔内,中毒时间为duration
当d < duration时,在两次攻击时间间隔内,中毒时间为d
因此,我们只需要计算出相邻两次攻击的间隔时间,再计算出中毒时间,最后求出中毒时间总和,即可求出中毒总时间
注:在最后一次攻击后,也有一段中毒时间
代码实现:
class Solution {public int findPoisonedDuration(int[] timeSeries, int duration) {if(timeSeries.length <= 1) return duration;//当只有一次攻击时,直接返回durationint sum = 0;for(int i = 0; i = duration) sum += duration;else sum += d;}sum += duration;//最后一次攻击后的中毒时间return sum;}}
练习3:Z字形变换
题目链接:
6. Z 字形变换 – 力扣(LeetCode)
题目描述:
将一个给定字符串s
根据给定的行数numRows
,以从上往下、从左到右进行Z 字形排列。
比如输入字符串为"PAYPALISHIRING"
行数为3
时,排列如下:
P A H NA P L S I I GY I R
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"
。
请你实现这个将字符串进行指定行数变换的函数:
string convert(string s, int numRows);
示例 1:
输入:s = "PAYPALISHIRING", numRows = 3输出:"PAHNAPLSIIGYIR"
示例 2:
输入:s = "PAYPALISHIRING", numRows = 4输出:"PINALSIGYAHRPI"解释:P INA L SI GY A H RP I
示例 3:
输入:s = "A", numRows = 1输出:"A"
提示:
1 <= s.length <= 1000
s
由英文字母(小写和大写)、','
和'.'
组成1 <= numRows <= 1000
思路分析:
我们以题目示例为例,来进行一次变换:
此时,先从上往下,再从左下往右上,再从上往下… 将字符串变换成了”Z”字形,也类似于”N”
我们首先按题目要求进行变换,要进行从上往下,再从坐下往右上的变换,因此我们需要一个矩阵,所有我们可以创建一个二维数组
我们从第0行开始,向下填写:
设当前为(x, y),向下填写:(x+1, y),直到填写到numRow – 1行
接下来,从左下到右上开始填写:
从(x, y)开始,向右上填写:(x + 1, y – 1),直到填写到第0行
…
一直填写直到最后一个字符,然后再从左到右,从上到下读取所有字符
如何判断是向下填写还是向右上填写?
我们可以使用变量flag进行标记,当x为0 或x为numRow时,就改变转向,即flag = -flag,当flag为1时,就向下填写;而当flag为-1时,就向右上填写
代码实现:
class Solution {public String convert(String s, int numRows) {if(numRows == 1) return s;//当间隔为1时,变换后仍为原字符串,直接返回即可char[] chs = s.toCharArray();char[][] arr = new char[numRows][chs.length];//直接将列数设置为字符串长度即可int x = 0, y = 0;int flag = -1;//标记转向for(int i = 0; i < chs.length; i++){if(x == 0 || x == numRows - 1){//当处于第一行和最后一行时,改变转向flag = -flag;}arr[x][y] = chs[i];if(flag == 1){//向下填写x++;}else{//向右上填写x--;y++;}}StringBuilder ret = new StringBuilder();for(int i = 0; i < arr.length; i++){//遍历数组,从左到右,从上到下,将数组中的字符拼接for(int j = 0; j < arr[0].length; j++){if(arr[i][j] != 0){ret.append(arr[i][j]);}}}return ret.toString();}}
通过观察变换后的字形我们可以发现:变换后的字形具有周期性,因此我们可以寻找其中的变换规律,从而直接得出变换后的字符串
第一行与最后一行类似,我们以第一行为例,来观察其中的规律:
设第一行两个字符之间的间隔为 d,为了更方便观察规律,我们以下标来标识每一个字符:
当numRow为4时,d为6,而间隔d,其实就是从0到6(不包括6)的字符个数,因此,我们只需求出从x1 到 x2的字符个数,即可求出d
如何求出字符个数?
我们将中间的字符都移动到第二列:
即可发现当移动到第二列后,第二列只缺少第一个和最后一个元素,因此d = 2*numRow – 2
则第一行元素为:0,0 +d,0 + 2*d,0 + 3*d,… 0 + n*d
最后一行元素为:numRow – 1,numRow – 1 + d,numRow – 1 + 2*d,…numRow – 1 + n*d
接下来,我们寻找中间元素(第i行)的变换规律:
我们可以发现:第i行的两个字符下标和为d
因此,第i行元素为:i,d – i,i + d,d – i + d… i + n*d,d – i + n*d
由上述规律,我们即可直接找到每一行的字符
注:当numRow为1时,d = 0,此时第一行元素始终为0,陷入死循环,因此要特殊处理该情况
代码实现:
class Solution {public String convert(String s, int numRows) {if(numRows <= 1) return s;//处理特殊情况int d = numRows*2 - 2;//间隔dint n = s.length();StringBuilder ret = new StringBuilder();for(int i = 0; i < n; i+= d){//添加第一行字符ret.append(s.charAt(i));}for(int row = 1; row < numRows - 1; row++){//添加中间行字符for(int i = row, j = d - row; 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();}}