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

news/2024/11/2 0:00:10/

目录

  • 一、什么是模拟
  • 二、模拟算法的特点和技巧
  • 三、模拟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/news/1543723.html

相关文章

分享几款开源好用的图片在线编辑,适合做快速应用嵌入

图片生成器是指一种工具或软件&#xff0c;用于自动生成图片或图像内容&#xff0c;通常依据用户设定的参数或模板进行操作。这种工具能够帮助用户快速创建视觉效果丰富的图像&#xff0c;而无需具备专业的设计技能。 在数字化时代&#xff0c;图片编辑已经成为日常工作和生活的…

【ChatGP】让ChatGPT解释和简化复杂的技术概念

让ChatGPT解释和简化复杂的技术概念 在科技迅速发展的今天&#xff0c;许多人面临着理解复杂技术概念的挑战。无论是初学者还是专业人士&#xff0c;能够轻松理解并运用这些概念都是至关重要的。ChatGPT作为一个强大的语言模型&#xff0c;可以帮助用户解释和简化复杂的技术概…

【深度学习基础】深入理解 卷积与卷积核

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;深度学习_十二月的猫的博客-CSDN博客 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 1. 卷积 1.1 …

Python 自动化运维:安全与合规最佳实践

Python 自动化运维&#xff1a;安全与合规最佳实践 目录 &#x1f512; Python安全编程实践与最佳实践&#x1f511; 使用Hashlib与Cryptography进行数据加密&#x1f4ca; 安全审计与合规检查的重要性&#x1f50d; 处理敏感数据与隐私保护的方法 1. &#x1f512; Python安…

python/Django创建应用(app)

注意事项&#xff1a; Django已经安装在你的Python环境中。 你已经创建了一个Django项目&#xff0c;并且当前工作目录是项目的根目录。你的虚拟环境&#xff08;如果使用&#xff09;已经被激活。 在原有Django项目的控制台 python manage.py startapp myapp 创建一个应用&…

Spring Boot的核心优势及其应用详解

目录 前言1. Spring Boot的核心优势1.1 启动依赖的集成1.2 自动化配置 2. 内嵌服务器支持2.1 内嵌Tomcat服务器2.2 独立运行与便捷部署 3. 外部配置管理3.1 多环境支持3.2 配置优先级与外部化配置 4. Spring Boot的应用场景4.1 微服务架构4.2 云原生应用 结语 前言 在现代的Ja…

k8s Sidecar代理

Sidecar 代理是一种常见的设计模式&#xff0c;在 Kubernetes 和微服务架构中经常被用来增强服务的功能和隔离服务的职责。Sidecar 代理作为一个附属的进程或容器&#xff0c;通常与主应用容器一起部署在同一个 Pod 中&#xff0c;负责处理一些非业务的通用任务&#xff0c;比如…

网络:IP分片和组装

个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》《Linux》《网络》 《redis学习笔记》 文章目录 前言16位标识&#xff0c;3位标志&#xff0c;13位片偏移分片组装总结 前言 对于IP分片和组装的总结 当一个IP数据报的大小超过网络的MTU(最…