新乡网站优化公司,网站建设还有需求么,系统平台搭建,国内最好的视频剪辑培训机构在算法中#xff0c;模拟是一种通过计算机程序来模拟现实世界中的过程或系统行为的方法。它的核心思想是根据题目给定的规则和逻辑#xff0c;按照步骤细致地重现事件的发展流程#xff0c;从而获得最终结果。 解题时如何使用模拟算法#xff1a; 理解题目规则#xff1a;…
在算法中模拟是一种通过计算机程序来模拟现实世界中的过程或系统行为的方法。它的核心思想是根据题目给定的规则和逻辑按照步骤细致地重现事件的发展流程从而获得最终结果。 解题时如何使用模拟算法 理解题目规则仔细分析题目给出的规则和逻辑确保理解全面。设计模拟流程在动手写代码之前先在草纸上画出模拟的流程图明确每一步的操作。模块化实现将模拟过程分解为多个模块分别实现这样可以减少错误并便于调试。处理特殊情况注意边界条件和特殊情况的处理这是模拟算法中容易出错的地方。分块调试在实现过程中可以先单独测试每个模块确保其正确性。 以下是一个简单的模拟算法题目及其解题思路 题目一只长度不计的蠕虫位于n英寸深的井的底部。它每次向上爬u英寸但休息时会滑落d英寸。求蠕虫爬出井口需要的最少爬行次数。
解题思路
使用循环模拟蠕虫的爬行过程。每次循环中蠕虫向上爬u英寸然后滑落d英寸。当蠕虫的总爬行高度超过井的深度时结束循环。
代码实现
#include cstdio
int main() {int n, u, d; // 井的深度、每次爬升高度、每次滑落高度scanf(%d %d %d, n, u, d);int height 0, steps 0;while (height n) {height u;steps;if (height n) break; // 如果已经爬出井口结束循环height - d;}printf(%d\n, steps);return 0;
}通过上述步骤和示例可以看到模拟算法的核心在于“照葫芦画瓢”按照题目要求逐步实现。
1.替换所有的问号
题目描述 给你一个仅包含小写英文字母和 ? 字符的字符串 s请你将所有的 ? 转换为若干小写字母使最终的字符串不包含任何 连续重复 的字符。 注意你 不能 修改非 ? 字符。 题目测试用例保证 除 ? 字符 之外不存在连续重复的字符。 在完成所有转换可能无需转换后返回最终的字符串。如果有多个解决方案请返回其中任何一个。可以证明在给定的约束条件下答案总是存在的。 示例 1 输入s ?zs
输出azs
解释该示例共有 25 种解决方案从 azs 到 yzs 都是符合题目要求的。只有 z 是无效的修改因为字符串 zzs 中有连续重复的两个 z 。示例 2 输入s ubv?w
输出ubvaw
解释该示例共有 24 种解决方案只有替换成 v 和 w 不符合题目要求。因为 ubvvw 和 ubvww 都包含连续重复的字符。提示 1 s.length 100s 仅包含小写英文字母和 ? 字符 算法思路 从前往后遍历整个字符串找问号。找到问号之后就用 a ~ z 的每⼀个字符去尝试替换。最终的字符串不包含任何连续重复的字符说明替换的字符与它自身前或后的位置的字符都不重复。 代码实现
class Solution
{
public:string modifyString(string s) {int ns.size();for(int i0;in;i){if(s[i]?)//替换{for(char cha;chz;ch){if((i0||ch!s[i-1])(in-1||ch!s[i1])){s[i]ch;break;}}}}return s;}
};2.提莫攻击
题目描述 在《英雄联盟》的世界中有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希编者注寒冰射手进入中毒状态。 当提莫攻击艾希艾希的中毒状态正好持续 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 1040 timeSeries[i], duration 107timeSeries 按 非递减 顺序排列 算法思路 计算相邻两个时间点的差值 i. 如果差值大于等于中毒时间说明上次中毒可以持续 duration 秒 ii. 如果差值小于中毒时间那么上次的中毒只能持续两者的差值。 最后的攻击也会持续duration 秒。 代码实现 class Solution
{
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int ret0;for(int i1;itimeSeries.size();i){int xtimeSeries[i]-timeSeries[i-1];if(xduration)retduration;elseretx;}return retduration;}
};3.Z字形变换
题目描述 将一个给定字符串 s 根据给定的行数 numRows 以从上往下、从左到右进行 Z 字形排列。 比如输入字符串为 PAYPALISHIRING 行数为 3 时排列如下 P A H N
A P L S I I G
Y I R之后你的输出需要从左往右逐行读取产生出一个新的字符串比如PAHNAPLSIIGYIR。 请你实现这个将字符串进行指定行数变换的函数 string convert(string s, int numRows);示例 1 输入s PAYPALISHIRING, numRows 3
输出PAHNAPLSIIGYIR示例 2 输入s PAYPALISHIRING, numRows 4
输出PINALSIGYAHRPI
解释
P I N
A L S I G
Y A H R
P I示例 3 输入s A, numRows 1
输出A提示 1 s.length 1000s 由英文字母小写和大写、, 和 . 组成1 numRows 1000 算法思路 找规律⽤ row 代替行数row 4 时画出的 N 字形如下 0 2row-2 4row-41 2row-3 2row-1 4row-5 4row-32 2row-4 2row 4row-6 4row-23 2row1 4row-1不难发现数据是以 2row - 2 为一个周期进行规律变换的。将所有数替换成用周期来表示的变量 第一行的数是0, 2row - 2, 4row - 4 第二行的数是1, (2row - 2) - 1, (2row - 2) 1, (4row - 4) - 1, (4row - 4) 1 第三行的数是2, (2row - 2) - 2, (2row - 2) 2, (4row - 4) - 2, (4row - 4) 2 第四行的数是3, (2row - 2) 3, (4row - 4) 3。 可以观察到第一行、第四行为差为 2row - 2 的等差数列第二行、第三行除了第一个数取值为行数每组下标为(2n - 1, 2n)的数围绕2row - 2的倍数左右取值。 以此规律我们可以写出迭代算法。 代码实现 class Solution
{
public:string convert(string s, int numRows) {//处理边界情况if(numRows1) return s;string ret;int d2*numRows-2,ns.size();//1.先处理第一行for(int i0;in;id)rets[i];//2.处理中间行for(int k1;knumRows-1;k)//枚举每一行{for(int ik,jd-k;in||jn;id,jd){if(in) rets[i];if(jn) rets[j];}}//3.处理最后一行for(int inumRows-1;in;id)rets[i];return ret;}
};4.外观数列
题目描述 「外观数列」是一个数位字符串序列由递归公式定义 countAndSay(1) 1countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。 行程长度编码RLE是一种字符串压缩方法其工作原理是通过将连续相同字符重复两次或更多次替换为字符重复次数运行长度和字符的串联。例如要压缩字符串 3322251 我们将 33 用 23 替换将 222 用 32 替换将 5 用 15 替换并将 1 用 11 替换。因此压缩后字符串变为 23321511。 给定一个整数 n 返回 外观数列 的第 n 个元素。 示例 1 **输入**n 4 输出“1211” 解释 countAndSay(1) “1” countAndSay(2) “1” 的行程长度编码 “11” countAndSay(3) “11” 的行程长度编码 “21” countAndSay(4) “21” 的行程长度编码 “1211” 示例 2 **输入**n 1 输出“1” 解释 这是基本情况。 提示 1 n 30 算法思路 所谓外观数列其实只是依次统计字符串中连续且相同的字符的个数。依照题意依次模拟即可。 代码实现 class Solution
{
public:string countAndSay(int n) {string ret1;for(int i1;in;i)//解释n-1次ret即可。{string tmp;int lenret.size();for(int left0,right0;rightlen;){while(rightlenret[left]ret[right])// 找到连续相同的字符区间right;tmpto_string(right-left)ret[left];// 将字符的数量和字符本身拼接到 tmp 中leftright;// 更新 left 指针到下一个新的字符位置}rettmp;// 将生成的新序列赋值给 ret用于下一次迭代}return ret; // 返回最终生成的序列}
};5.数青蛙
题目描述 给你一个字符串 croakOfFrogs它表示不同青蛙发出的蛙鸣声字符串 croak 的组合。由于同一时间可以有多只青蛙呱呱作响所以 croakOfFrogs 中会混合多个 “croak” 。 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。 要想发出蛙鸣 “croak”青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成请返回 -1 。 示例 1 输入croakOfFrogs croakcroak
输出1
解释一只青蛙 “呱呱” 两次示例 2 输入croakOfFrogs crcoakroak
输出2
解释最少需要两只青蛙“呱呱” 声用黑体标注
第一只青蛙 crcoakroak
第二只青蛙 crcoakroak示例 3 输入croakOfFrogs croakcrook
输出-1
解释给出的字符串不是 croak 的有效组合。提示 1 croakOfFrogs.length 105字符串中的字符只有 c, r, o, a 或者 k 算法思路 模拟青蛙的叫声。 当遇到 ‘r’ ‘o’ ‘a’ ‘k’ 这四个字符的时候我们要去看看每⼀个字符对应的前驱字符有没有青蛙叫出来。如果有青蛙叫出来那就让这个青蛙接下来喊出来这个字符如果没有直接返回 -1 当遇到 ‘c’ 这个字符的时候我们去看看 ‘k’ 这个字符有没有青蛙叫出来。如果有就让这个青蛙继续去喊 ‘c’ 这个字符如果没有的话就重新搞一个青蛙。 代码实现 class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string tcroak;int nt.size();vectorint hash(n);//用数组来模拟哈希表unordered_mapchar,int index;//[x,x这个字符对应的下标]for(int i0;in;i)index[t[i]]i;for(auto ch:croakOfFrogs){if(chc){if(hash[n-1]!0) hash[n-1]--;hash[index[ch]];}else{int iindex[ch];if(hash[i-1]0) return -1;hash[i-1]--;hash[i];}}for(int i0;in-1;i)if(hash[i]!0)return -1;return hash[n-1];}
};最后笔者要说的是模拟算法虽然在某些情况下可能显得繁琐但它具有极高的通用性和直观性能够解决许多难以直接用数学公式或复杂数据结构求解的问题。通过上述问题的分析和实现我们可以看到模拟算法的核心在于理解题目规则、设计清晰的模拟流程、处理特殊情况。在实际应用中模拟算法不仅可以帮助我们快速实现解决方案还能在复杂问题中找到规律为进一步优化提供思路。
总之模拟算法是算法设计中的重要工具掌握它能够帮助我们更好地应对各种复杂问题。
