【优选算法】模拟

news/2024/12/2 11:33:34/

在这里插入图片描述

目录

  • 一、[替换所有的问号](https://leetcode.cn/problems/replace-all-s-to-avoid-consecutive-repeating-characters/description/)
  • 二、[提莫攻击](https://leetcode.cn/problems/teemo-attacking/description/)
  • 三、[Z 字形变换](https://leetcode.cn/problems/zigzag-conversion/description/)
  • 四、[外观数列](https://leetcode.cn/problems/count-and-say/description/)
  • 五、[数青蛙](https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/)
  • 结尾

一、替换所有的问号

题目描述
在这里插入图片描述

思路讲解
本题的可以使用模拟
算法来解决本题,模拟算法就依葫芦画瓢,思路比较简单,但是比较考验代码能力。

对题目进行解释就是在数组中找到每一个?,将这个?变为26个小写字母中的任意一个,但是它不能与左右两边的字母相同,例如:a?b中的?只要不变为a/b中的其中一个,就可以变为除a和b以外的其他任意的小写字母。需要注意两个特别的位置,数组的开头和结尾,数组的开头位置左边没有数据,数组的结尾位置右边没有数据,需要对这两个位置进行特殊处理。

编写代码

class Solution {
public:string modifyString(string s) {int sLen = s.size();for(int i = 0 ; i <= sLen - 1; i++){if(s[i] == '?'){for(int ch = 'a' ; ch <= 'z' ;ch++){if((i == 0 || s[i - 1] != ch) && (i == sLen - 1 || s[i + 1] != ch) ){s[i] = ch;break;}}}}return s;}
};

二、提莫攻击

题目描述
在这里插入图片描述

思路讲解
本题同样是使用模拟
算法来解决,提莫对艾希进行攻击后,艾希会进入长达duration秒的中毒状态,当在艾希处于中毒状态的期间继续攻击,那么艾希的中毒时间会被重置,继续中毒duration秒。例如:艾希在1秒的时候进入中毒状态,中毒状态持续时间duration为2秒,则艾希在第三秒时就会解除中毒状态,但是若提莫在第二秒时继续攻击艾希,那么艾希的中毒时间被重置,从第二秒开始中毒2秒,则艾希在第四秒时就会解除中毒状态。

通过上面的描述我们可以得知,当提莫两次攻击的时间(t1,t2)差大于等于中毒持续时间(duration),则艾希的第一次中毒时间会持续duration秒,反之当提莫两次攻击的时间差大于等于中毒持续时间(duration),则艾希的第一次中毒时间会持续t1 - t2秒。需要注意的是提莫最后一次攻击后,艾希的中毒状态必定有duration秒。接下来就可以将思路转化为代码了。

编写代码

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int ans = 0;int timeSeriesLen = timeSeries.size();for(int i = 1 ; i < timeSeriesLen ;i++){if(timeSeries[i] - timeSeries[i-1] < duration){ans += timeSeries[i] - timeSeries[i-1];}else{ans += duration;}}// 最后一个攻击后必定中毒duration秒ans += duration;return ans;}
};

三、Z 字形变换

题目描述
在这里插入图片描述

思路讲解
本题同样是使用模拟
算法来解决,将题目给的字符串,以从上往下、从左到右进行 Z 字形排列,说是Z字形但是看起来却像N字形。

以下图为例,我们可以创建一个n行len列的二位数组(这里的len是字符串的长度,实际上可能并不需要这么长,大家可以找一个方法来计算出len的大小),按照特定的方法将字符串中放到二维数组中,再一行一行的遍历,组成新的字符串返回即可。但是这样本题的复杂度为:时间复杂度O(n * len) + 空间复杂度O(n * len),并不是一个很好的解决方案。
在这里插入图片描述

我们根据上面的解法进行优化,我们不将字符串放入二维数组中,而是将字符串每个字符的下标放入二维数组进行观察,仔细观察每一行,发现第0行中每一个数相差6也就是2n-2,我们设公差d=2n-2,同样第n-1行每一个数相差的也是2n-2,再看中间几行,以每两个数为一组,第一组的两个下标相加等于公差d,后面每一组下标都是在前一组对应数的基础上加上公差d,通过这里的描述就可以得出下面的结论。

  1. 第0行:0 --> 0+d --> 0+2d --> ... -> 0 + xd
  2. 第k行:{k,d-k} --> {k+d,d-k+d} --> {k+2d,d-k+2d} -> ... --> {k+xd,d-k+xd}
  3. 第n-1行:n-1 --> n-1+d --> n-1+2d --> ... -> n-1 + xd

在这里插入图片描述
然后再测试其他行的情况,发现上面的结论同样适用,除了只有n=1的情况,n=1时公差d=0,会导致代码陷入死循环,需要特殊处理。总结出上面的规律后,实际上这个二维数组就不用定义了,可以使用上面这个结论来解决本题。

编写代码

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1)return s;string ans;int sLen = s.size();int d = 2 * numRows - 2;  // 公差,寻找下一个字母需要移动的位置// 第一行for(int i = 0 ; i < sLen ; i += d)ans += s[i];for(int i = 1 ; i < numRows - 1;i++){for(int num1 = i , num2 = d - i ; num1 < sLen ; num1 +=d , num2 += d){ans += s[num1];if(num2 < sLen)ans += s[num2];}            }// 最后一行for(int i = numRows-1 ; i < sLen ; i += d)ans += s[i];return ans;}
};

四、外观数列

题目描述
在这里插入图片描述

思路讲解
本题的解题思路依旧是模拟,将题目内容转换为下图,那么本题的就可以使用双指针遍历字符串,记录每一段的数字和相同数字的个数并添加到一个新的字符串即可解决本题。
在这里插入图片描述

编写代码

class Solution {
public:string countAndSay(int n) {string ans("1");int left = 0 , right = 0;int count = 0; // 记录连续相同数字的个数while(--n){string tmp;while(right < ans.size()){while(right < ans.size() && ans[left] == ans[right]){count++;right++;}tmp += (count + '0');tmp += ans[left];count = 0;left = right;}left = right = 0;ans = tmp;}return ans;}
};

五、数青蛙

题目描述
在这里插入图片描述

思路讲解
本题的解题思路依旧是模拟,本题需要得到模拟字符串中所有蛙鸣所需不同青蛙的最少数目,从上面题目示例的演示可以得到,当一个青蛙叫完后可以继续叫,当没有青蛙处于叫完状态并且还继续需要蛙叫时,就需要增加新的青蛙了。

这里我们定义一个哈希表(这里可以使用数组)来记录处于每种字符下青蛙的个数,接下来对遍历到某个字符时,进行处理的方法进行分类讨论。

  1. 当遍历到r、o、a、k时,查看前一个字符下有多少个青蛙,若为非0,则将前一个字符中的一个青蛙放到当前字符下,若为0,说明给出的字符串不是 “croak” 的有效组合,返回-1。
  2. 当遍历到c时,查看字符k下有多少个青蛙,字符k下的青蛙个数代表已经叫完青蛙的个数,也就是可以重新开始叫的青蛙的个数,若为非0,则将字符k中的一个青蛙放到字符c中重新开始叫,若为0,则说明需要新的青蛙,引入一个新的青蛙放到字符c中即可。

当字符串遍历完后,再遍历一下哈希表,查看字符c、r、o、a下的青蛙是否为0,为非0,说明给出的字符串不是 “croak” 的有效组合,返回-1,为0说明给出的字符串是 “croak” 的有效组合,返回字符k下的青蛙个数即可。

编写代码

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {unordered_map<int,int> um;int count = 0;for(int i = 0 ; i < croakOfFrogs.size() ; i++){// k为0则说明没有已经叫完的蛙// 那么需要有一只新的蛙if(croakOfFrogs[i] == 'c'){if(um['k'] != 0)um['k']--;elsecount++;um['c']++;}// 若前面有蛙叫出了c,那么这里继续叫r// 且叫c的蛙要少一个,叫r的蛙多一个// 否则则出错返回-1else if(croakOfFrogs[i] == 'r'){if(um['c'] != 0){um['c']--;um['r']++;}else{return -1;}}else if(croakOfFrogs[i] == 'o'){if(um['r'] != 0){um['r']--;um['o']++;}else{return -1;}}else if(croakOfFrogs[i] == 'a'){if(um['o'] != 0){um['o']--;um['a']++;}else{return -1;}}else // croakOfFrogs[i] == 'k'{if(um['a'] != 0){um['a']--;um['k']++;}else{return -1;}}}// 叫完后,所有的蛙必须是叫完k// 若其他叫声中还有蛙,则说明无效,返回-1if(um['c'] || um['r'] || um['o'] || um['a'])return -1;return count;}
};

结尾

如果有什么建议和疑问,或是有什么错误,大家可以在评论区中提出。
希望大家以后也能和我一起进步!!🌹🌹
如果这篇文章对你有用的话,希望大家给一个三连支持一下!!🌹🌹

在这里插入图片描述


http://www.ppmy.cn/news/1551741.html

相关文章

CentOS使用chrony服务进行时间同步源设置脚本

CentOS使用chrony服务进行时间同步源设置脚本 #!/bin/bash# Created: 2024-11-26 # Function: Check and Set OS time sync source to 10.0.11.100 # FileName: centos_set_time_source_to_ad.sh # Creator: Anster # Usage: # curl http://webserver-ip/scripts/centos_set…

yolov11剪枝

思路&#xff1a;yolov11中的C3k2与yolov8的c2f的不同&#xff0c;所以与之前yolov8剪枝有稍许不同&#xff1b; 后续&#xff1a;会将剪枝流程写全&#xff0c;以及增加蒸馏、注意力、改loss&#xff1b; 注意&#xff1a; 1.在代码105行修改pruning.get_threshold(yolo.mo…

Qt 中的 UiTools 详解

Qt 是一个功能强大的 C 跨平台开发框架&#xff0c;支持用户界面设计、图形渲染、事件处理等诸多功能。UiTools 是 Qt 提供的一个模块&#xff0c;专门用于动态加载和处理 .ui 文件。它在动态界面生成、模板化设计等场景下尤为重要。 一、什么是 UiTools&#xff1f; UiTools …

javaweb 前端 vue3

vue快速入门 引入createAPP这个模块&#xff0c;或者说这个函数 第二步&#xff0c;创建应用实例 调用createAPP这个函数&#xff0c;传递对象{}&#xff0c;js中定义对象用{} js的分号可以加或者不加 第四步准备数据&#xff0c;在传递的对象中声明这个方法data&#xff0c;指…

七:仪表盘安装-controller node

一&#xff1a;工具、环境准备-controller node 二&#xff1a;OpenStack环境准备-controller node 三&#xff1a;安装服务-controller node 四&#xff1a;工具、环境准备-compute node 五&#xff1a;OpenStack环境准备-compute node 六&#xff1a;安装服务-compute node 七…

【JAVA】Java高级:连接池的使用与性能优化——C3P0、HikariCP与DBCP比较

在Java开发中&#xff0c;数据库连接池帮助我们有效地管理数据库连接&#xff0c;减少连接的创建和销毁所带来的开销&#xff0c;从而提高应用程序的性能和可伸缩性。常用的数据库连接池有C3P0、HikariCP和DBCP。接下来&#xff0c;我们将逐步深入了解这三种连接池的特点、优缺…

【学术投稿】Imagen:重塑图像生成领域的革命性突破

【连续七届已快稳ei检索】第八届电子信息技术与计算机工程国际学术会议&#xff08;EITCE 2024&#xff09;_艾思科蓝_学术一站式服务平台 更多学术会议请看 https://ais.cn/u/nuyAF3 目录 引言 一、Imagen模型的技术原理 1. 模型概述 2. 工作流程 3. 技术创新 二、Ima…

浅谈网络 | 应用层之DNS协议

目录 DNS 服务器的工作原理DNS 解析流程负载均衡示例&#xff1a;DNS 访问数据中心中对象存储上的静态资源 随着互联网的普及&#xff0c;网站的数量越来越多&#xff0c;常用的网站也有二三十个。如果我们全部用 IP 地址来访问网站&#xff0c;恐怕很难记住。于是&#xff0c;…