模拟算法 (算法详解+例题)

ops/2024/11/1 18:07:33/

目录

  • 一、什么是模拟
  • 二、模拟算法的特点和技巧
  • 三、模拟OJ题
    • 3.1、替换所有的问号
    • 3.2、提莫攻击
    • 3.3、N字形变换
    • 3.4、外观数列
    • 3.5、数青蛙

一、什么是模拟

模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能,可以用语言来模拟那个功能,模拟成功也就相应地表示编程成功。

二、模拟算法的特点和技巧

特点:

  • 代码量大

  • 操作多

  • 思路复杂

  • 较为复杂的模拟题出错后难定位错误

技巧:

  • 在动手写代码之前,在草纸上尽可能地写好要实现的流程.

  • 在代码中,尽量把每个部分模块化,写成函数、结构体或类

  • 对于一些可能重复用到的概念,可以统一转化,方便处理:如,某题给你"YY-MM-DD 时:分" 把它抽取到一个函数,处理成秒,会减少概念混淆

  • 调试时分块调试。模块化的好处就是可以方便的单独调某一部分

  • 写代码的时候一定要思路清晰,不要想到什么写什么,要按照落在纸上的步骤写

三、模拟OJ题

3.1、替换所有的问号

1576. 替换所有的问号

在这里插入图片描述

算法思路

纯模拟。从前往后遍历整个字符串,找到问号之后,就⽤ a ~ z 的每⼀个字符去尝试替换即可。

算法代码

class Solution {
public:string modifyString(string s) {for(int i = 0; i<s.size(); i++)//遍历每一个字符{if(s[i] == '?'){for(char ch = 'a'; ch <= 'z'; ch++)//a ~ z都试试{if(i == 0 && ch != s[i+1]) //头位置是'?',不能和后一个相等s[i] = ch;else if(i == s.size()-1 && ch != s[i-1])//尾位置是'?' ,不能和前一个相等s[i] = ch;else if(ch != s[i+1] && ch != s[i-1]) //中间情况, 不能和两边相等s[i] = ch;}}}return s;}
};

3.2、提莫攻击

495. 提莫攻击

在这里插入图片描述

算法思路

模拟 + 分情况讨论。

计算相邻两个时间点的差值

  • i. 如果差值 ⼤于等于 中毒时间,说明上次中毒可以持续 duration 秒;

  • ii. 如果差值 ⼩于 中毒时间,那么上次的中毒只能持续两者的差值。

算法代码

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans = 0;for(int i = 0; i<timeSeries.size(); i++) //遍历每一个中毒time,计算差值与duration比较{// 如果差值 ⼤于等于 中毒时间,说明上次中毒可以持续 duration 秒,if(i + 1 < timeSeries.size() && timeSeries[i+1] - timeSeries[i] >= duration)ans+=duration;//如果差值 ⼩于 中毒时间,那么上次的中毒只能持续两者的差值//因为中毒中不完,到下个时间就会重置,这轮中毒时间就是两者的差值if(i + 1 < timeSeries.size() && timeSeries[i+1] - timeSeries[i] < duration)ans+=timeSeries[i+1] - timeSeries[i];}ans+=duration; //最后还需要加一个duration,因为最后一次攻击的中毒时间可以全部中毒完return ans;}
};

3.3、N字形变换

Z 字形变换

在这里插入图片描述

  • 对于前面的 3 行的 示例1 , 它的字符数分布是这样的
    在这里插入图片描述
  • 对于前面的 4 行的 示例2 , 它的字符数分布是这样的:
    在这里插入图片描述
  • 那么对于 n 行的字符数分布是这样的:
    在这里插入图片描述
    如上图所示,我们可以发现:

公差为 2n - 2

  1. 当前行 curRow 为 0 时 ,下标变化是 0 -> 0+d -> 0+2d -> … ->0+kd;

  2. 当前行 curRow 为 n-1 时 ,下标变化是n-1 -> n-1+d -> n-1+2d -> … ->n-1+kd;

  3. 当前行 curRow 为 k 时 ,下标变化是( k , d-k ) -> ( k+d , d-k+d ) -> ( k+ 2d, d-k+2d ) -> …

算法代码

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;int d = 2 * numRows - 2; //公差d = 2n-1string ret;for(int i = 0; i<s.size(); i+=d) //当前行 curRow 为 0 ret += s[i];for(int k = 1; k<numRows-1; k++) //当前行 curRow 为 k{//( k , d-k ) -> ( k+d , d-k+d ) -> ( k+ 2d, d-k+2d ) -> .....for(int i = k ,j = d - k; i < s.size() || j < s.size(); i+=d,j+=d){if(i < s.size()) ret+=s[i];if(j < s.size()) ret+=s[j];}}for(int i = numRows-1; i<s.size(); i+=d) //当前行 curRow 为 n-1ret+=s[i];return ret;}
};

3.4、外观数列

38. 外观数列

在这里插入图片描述

算法思路

所谓「外观数列」,其实只是依次统计字符串中连续且相同的字符的个数。依照题意,依次模拟即可。

算法代码

class Solution {
public:string countAndSay(int n) {string ret = "1" ; //countAndSay(1) = "1"for(int i = 1; i<n; i++)//循环n-1次{string tmp; //用tmp暂存,进行替换int left = 0 ,right = 0;while(right < ret.size()) //right出ret,双指针结束{while(ret[right] == ret[left]) right++; //到不相等的那个数结束//然后加上有几个这个数 right - left,再加上这个数本身tmp+= to_string(right-left);tmp+= ret[left];left = right;//更新left位置,进行下一次双指针}ret = tmp; //更新ret,进行下一次循环}return ret;}
};

3.5、数青蛙

1419. 数青蛙

在这里插入图片描述

算法思路

将青蛙分成 5 种:

  • 刚才发出了 c 的声音。
  • 刚才发出了 r 的声音。
  • 刚才发出了 o 的声音。
  • 刚才发出了 a 的声音。
  • 刚才发出了 k 的声音。

遍历 croakOfFrogs,例如当前遍历到 r,那么就看看有没有青蛙刚才发出了 c 的声音,如果有,那么让它接着发出 r 的声音。换句话说,我们需要消耗一个 c,产生一个 r。

所以我们使用一个哈希表(数组)hash 来维护这 5 种青蛙的个数,并分类讨论:

  • 遍历到 c 时,看看有没有青蛙刚才发出了 k 的声音,如果有,那么复用这只青蛙,让它接着发出 c 的声音,即 hash[‘k’]-- 和 hash[‘c’]++;如果没有这种青蛙,那么新产生一只青蛙发出 c 的声音,即 hash[‘c’]++。

  • 遍历到 r , o,a,k ,找到该字母在 croak 的上一个字母的 hash 值,如果 hash 值大于 0,那么将其减一,同时当前字母的 hash 值加一;如果上一个字母的 hash 值等于 0,那么就返回 −1。

  • 遍历结束后,所有青蛙必须在最后发出 k 的声音。如果有青蛙在最后发出的声音不是 k(也就是 cnt 值大于 0),那么返回 −1,否则返回 hash[k]。

算法代码

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t = "croak";vector<int> hash(t.size()); //[0,4]对应crock ,各个个数unordered_map<char,int> index; //[x,x这个字符对应的下标]for(int i = 0; i<t.size(); i++)index[t[i]] = i; //存[x,x这个字符对应的下标]for(auto ch : croakOfFrogs) //遍历{if(ch == 'c'){//看看有没有青蛙刚才发出了 k 的声音,如果有,那么复用这只青蛙 ,k--,c++;if(hash[4] != 0) hash[4]--; hash[0]++;}else{int i = index[ch];//找出roak对应的下标if(hash[i-1] == 0) return -1; //找到该字母在 croak 的上一个字母的值,非0直接错hash[i-1]--; //不是0就--hash[i]++; //这个字母对应的数++,为了判断下一个字母}}//所有青蛙必须在最后发出 k 的声音。如果有青蛙在最后发出的声音不是 k,那么返回 −1。for(int i = 0; i<t.size()-1; i++) {if(hash[i] != 0)return -1;}return hash[t.size()-1];//返回}
};

http://www.ppmy.cn/ops/130194.html

相关文章

程序中怎样用最简单方法实现写excel文档

很多开发语言都能找到excel文档读写的库&#xff0c;但是在资源极其受限的环境下开发&#xff0c;引入这些库会带来兼容性问题。因为一个小功能引入一堆库&#xff0c;我始终觉得划不来。看到有项目引用的jar包有一百多个&#xff0c;看着头麻&#xff0c;根本搞不清谁依赖谁。…

Canvas字体高度计算与PDF高度如何统一

因为英文书写时并不是像汉字一样就是一个方块字&#xff0c;比如下图p有部分是在基线以下&#xff0c;其他的字体都是以基线为参照书写&#xff0c;所以在Canvas中字(或字母)所占的高度是&#xff1a; metrics.boundingBoxAscent metrics.boundingBoxDescent上行间距下行间距…

vue 禁用element-ui calendar 取消非本月日期的点击事件

需求描述&#xff1a;原本的日历组件不是本月的日期是灰色的&#xff0c;且点击后会跳转到对应的月份&#xff0c;现在不想它跳转&#xff0c;需要禁用它的点击事件 方法&#xff1a;使用css的pointer-events:none属性即可&#xff0c;把不是当前月份的日历表格的td属性修改 :…

【STM32】SD卡

(一)常用卡的认识 在学习这个内容之前&#xff0c;作为生活小白的我对于SD卡、TF卡、SIM卡毫无了解&#xff0c;晕头转向。 SD卡&#xff1a;Secure Digital Card的英文缩写&#xff0c;直译就是“安全数字卡”。一般用于大一些的电子设备比如&#xff1a;电脑、数码相机、AV…

python debug作业

任务类型任务内容预计耗时闯关任务Leetcode 383(笔记中提交代码与leetcode提交通过截图)20mins闯关任务Vscode连接InternStudio debug笔记10mins可选任务pip安装到指定目录10mins leetcode题目解析&#xff1a; 解题思路 字符统计&#xff1a;使用 Python 的 Counter 类统计 ra…

三代CAN技术演进:从CAN CC到CAN XL的创新路径(下篇)

欢迎关注虹科&#xff0c;为您提供最新资讯&#xff01; #CAN #工业通信 #CAN XL 导读 CAN&#xff08;Controller Area Network&#xff09;是一种用于实时应用的串行通信协议&#xff0c;广泛应用于汽车和工业电子设备中&#xff0c;以实现不同设备间的高效数据交换。它采…

程序员如何平衡日常编码工作与提升式学习

程序员如何平衡日常编码工作与提升式学习 在快速变化的技术世界中&#xff0c;作为程序员的你可能常常感到疲惫不堪&#xff0c;尤其是在日常的编码工作与个人成长之间寻找平衡时。如何在应对紧迫的项目截止日期同时&#xff0c;又能不断提升自己的技能&#xff1f;本文将探讨…

【网络面积篇】TCP断开连接(笔记)

目录 一. 四次挥手 &#xff08;1&#xff09;过程描述 &#xff08;2&#xff09;为什么是四次挥手&#xff1f; 二、相关问题 1. 第一次挥手丢失了&#xff0c;会发生什么&#xff1f; 2. 第二次挥手丢失了&#xff0c;会发生什么&#xff1f; 补充&#xff1a;close …