模拟算法实例讲解:从理论到实践的编程之旅

ops/2024/11/28 15:35:19/

目录

1、模拟算法简介

2、替换所有问号

 3、提莫攻击

4、Z字形变换

5、外观数列

6、数青蛙


1、模拟算法简介

模拟算法是一种基本的算法设计方法,它的核心思想是按照问题描述的规则,逐步模拟问题的发展过程,从而得到问题的解决方案。这种算法通常不依赖于复杂的数学公式或高级的数据结构,而是通过直接模拟现实世界中的操作或规则来解决问题。

2、替换所有问号

1576. 替换所有的问号

从前往后遍历整个字符串,找到问号之后,就用 a ~ z 的每⼀个字符去尝试替换即  
class Solution {
public:string modifyString(string s) { // 模拟,算法流程int n = s.size();for(int i = 0;i < n;i++){ // 遍历数组,找到?,替换if(s[i] == '?'){for(char ch = 'a';ch <= 'z';ch++){    // (?在开头||替换值与前面的字符不同) // && (?在结尾||替换值与后面字符不同)if((i == 0 || ch != s[i-1]) && (i == n-1 || ch != s[i+1])){s[i] = ch;break;}}}}return s;}
};

 3、提莫攻击

495. 提莫攻击

class Solution {
public:int findPoisonedDuration(vector<int>& timeSeries, int duration) {int T = 0;for(int i = 1;i < timeSeries.size();i++){   // 计算两次中毒的时间间隔int time = timeSeries[i] - timeSeries[i-1];// 间隔大于标准中毒时间,按标准计时 if(time > duration) T += duration;// 否则,计时会重置,所以只记录间隔时间else T += time;}// 别忘了最后一次中毒T += duration;return T;}
};

4、Z字形变换

6. Z 字形变换

方法一:用字符串数组vector<string>模拟Z字形存入数据,再将字符串数组中的字符串按行号顺序连接。

遍历字符串s时:用 flag 来做索引标记,到达Z字形转折点时的时候 (第一行 / 最后一行),执行反向 (flag = -flag) 。更新下标索引时,用 i += flag 。

class Solution {
public:string convert(string s, int numRows) {if(numRows == 1) return s;// 1.将数据存入字符串数组vector<string> vs(numRows);int i = 0,flag = -1;for(auto& x: s){vs[i] += x; // 刚进循环,第一个数据flag是-1if(i == 0 || i == numRows-1) // 第一/最后一行是转折点flag = -flag; // 用flag控制存储的方向,位置i += flag;}// 2.将字符串数组中所有字符串按行号顺序接合起来string str;for(string& rows: vs)str += rows;return str;}
};

方法二:找规律:

 第1/numRows行,隔2*numRows-2是一个元素。

 中间行,两组数据从(k,d-k)开始,每次隔2*numRows-2是一组数据,可能最后会有一个数据越界。

class Solution {
public:string convert(string s, int numRows) {// 边界情况if(numRows == 1) return s;// 找规律:第1/numRows行,隔2*numRows-2是一个元素// 中间行,两组数据从(k,d-k)开始,每次隔2*numRows-2是一组数据,// 可能最后会有一个数据越界string str;int d = 2 * numRows - 2; // 计算步长int n = s.size();// 处理第一行,从s[0]开始for(int i = 0;i < n;i += d)str += s[i];// 处理中间行的每一行,从(s[k],s[d-k])开始for(int k = 1;k < numRows-1;k++){for(int i = k,j = d-k;(i < n || j < n);i += d,j += d){if(i < n) str += s[i];if(j < n) str += s[j];}}// 处理最后一行,从s[numRows-1]开始for(int i = numRows-1;i < n;i += d)str += s[i];return str;}
};

5、外观数列

. - 力扣(LeetCode)

模拟 + 双指针,双指针用来模拟顺序读取下字符的连续次数。

class Solution {
public:string countAndSay(int n) {// 模拟 + 双指针string ret = "1"; // 初始值for (int i = 1;i < n; i++) // 模拟n-1次,因为第一次就是1{string tmp;int len = ret.size(); // 限定区域是在ret内for(int left = 0,right = 0;right < len;){while (right < len && ret[left] == ret[right]) right++;// 确定重复次数tmp += to_string(right - left); // 重复次数tmp += ret[left]; // 对应字符left = right; // 重置指针}ret = tmp; // 更换新字符串}return ret;}
};

6、数青蛙

. - 力扣(LeetCode)

方法:模拟 + 分情况讨论

用哈希表模拟寻找青蛙叫声的过程,开始时,青蛙开始发出叫声【c】,在哈希表中映射记录一次【c】叫声,假设紧接着发出【r】时,就要先在哈希表中找【r】的前驱字符【c】是否已经记录过叫,如果有记录就把这个记录传承下来,前驱【c】的叫声次数-1,当前【r】的叫声+1次;如果没有记录,就说明此时字符串记录的叫声是不完整的,不是有效组合。后续【o】...叫声与上面演示的【r】的处理方式类似。

但因为我们要找的是最少的青蛙数,青蛙在叫完完整一次“croak”后可以紧接着继续蛙鸣,所以,当读到【c】时还有一种情况是先查看哈希表中对应的【k】叫声个数,如果不是0,说明有青蛙可以重新开始一轮蛙鸣,对应我们的操作就是把记录到的【k】叫声个数-1,给【c】叫声个数+1。

总结:

1、r o a k  --->  查看前序字符是否在哈希表中存储个数

(1)存在:前驱个数--,当前个数++

(2)不存在:返回-1

2、c --->  找最后一个字符 k 在哈希表中是否存储

(1)存在:k字符个数--,c字符个数++

(2)不存在:c字符个数++

class Solution 
{
public:int minNumberOfFrogs(string croakOfFrogs) { // 用哈希表模拟string str = "croak"; // 先把叫声存储起来int n = str.size();vector<int> hash(n); // 数组模拟哈希表,用下表对应存储str的每个字符(‘c’对应0...)unordered_map<char,int> index(n); // 存储 [x,x对应的下标] 方便寻找前驱字符(通过下标)for(int i = 0;i < n; i++)index[str[i]] = i;for(auto ch : croakOfFrogs){if(ch == 'c'){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;}else{int prev = index[ch] - 1; // 找到前驱字符的下标if(hash[prev] == 0) return -1;hash[prev]--;hash[index[ch]]++;}}for(int i = 0;i < n - 1;i++)if(hash[i] != 0) return -1;return hash[n - 1];}
};
class Solution 
{
public:int minNumberOfFrogs(string croakOfFrogs) {unordered_map<char,int> vv;for(auto e : "croak"){vv[e] = 0;}int cur = 0,len = croakOfFrogs.size();while(cur < len){if(croakOfFrogs[cur] == 'r'){if(vv['c'] > 0) {vv['c']--;vv['r']++;} else return -1;}else if(croakOfFrogs[cur] == 'o'){if(vv['r'] > 0) {vv['r']--;vv['o']++;} else return -1;}else if(croakOfFrogs[cur] == 'a'){if(vv['o'] > 0) {vv['o']--;vv['a']++;} else return -1;}else if(croakOfFrogs[cur] == 'k'){if(vv['a'] > 0) {vv['a']--;vv['k']++;} else return -1;}else if(croakOfFrogs[cur] == 'c'){if(vv['k'] > 0){vv['k']--;vv['c']++;}else vv['c']++;}cur++;}for(auto e: "croa"){if(vv[e] > 0) return -1;}return vv['k'];}
};

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

相关文章

【halcon】Metrology工具系列之 get_metrology_object_model_contour

get_metrology_object_model_contour (Operator) Name get_metrology_object_model_contour — 在图像坐标中查询测量对象的模型轮廓。 Signature get_metrology_object_model_contour( : Contour : MetrologyHandle, Index, Resolution : )Description get_metrology_obj…

【Flink-scala】DataStream编程模型之 窗口的划分-时间概念-窗口计算程序

DataStream编程模型之 窗口的划分-时间概念-窗口计算程序 1. 窗口的划分 1.1 窗口分为&#xff1a;基于时间的窗口 和 基于数量的窗口 基于时间的窗口&#xff1a;基于起始时间戳 和终止时间戳来决定窗口的大小 基于数量的窗口&#xff1a;根据固定的数量定义窗口 的大小 这…

RK3568平台开发系列讲解(DMA篇)DMA engine使用

🚀返回专栏总目录 文章目录 一、申请DMA channel二、配置DMA channel的参数三、获取传输描述(tx descriptor)四、启动传输沉淀、分享、成长,让自己和他人都能有所收获!😄 📢DMA子系统下有一个帮助测试的测试驱动(drivers/dma/dmatest.c), 从这个测试驱动入手我们了解…

简单图论农场派对

题目 2406: 信息学奥赛一本通T1497-农场派对 时间限制: 2s 内存限制: 192MB 提交: 40 解决: 13 题目描述 原题来自&#xff1a;USACO 2007 Feb. Silver N(1≤N≤1000) 头牛要去参加一场在编号为 x(1≤x≤N) 的牛的农场举行的派对。有 M(1≤M≤100000) 条有向道路&#xff0c;每…

C++笔记之单例模式与静态方法的使用辨析及代码规范

C++笔记之单例模式与静态方法的使用辨析及代码规范 code review! 文章目录 C++笔记之单例模式与静态方法的使用辨析及代码规范一.示例代码二.讲解2.1.代码规范2.1.1.单例模式实现2.1.2.静态方法实现2.1.3.单例模式结合静态方法2.2.总结一.示例代码 // 使用 set 方法设置值(通…

IT成长之路-ubuntu驱动篇

历时3天的蹂躏&#xff0c;总结驱动安装全面教程。 步骤一、安装gcc、g和make包 #脚本更新 sudo apt-get update #编译gcc sudo apt-get install gcc #编译g sudo apt-get install g #编译make sudo apt-get install make 注意&#xff1a; gcc、g版本可能会导致显卡驱动安…

离散化/C++ STL编码+set去重

先只做离散 #include<iostream> #include<algorithm> #include<vector> #include<set> using namespace std; int main() {int N 0;cin >> N;vector<int> old;set<int> ne;int temp;for (int i 0; i < N; i) {cin >> te…

基于STM32的智能无人机自主飞行与目标识别系统设计

目录 引言系统需求分析 2.1 功能需求 2.2 硬件需求 2.3 软件需求系统设计 3.1 总体架构 3.2 各模块设计系统实现 4.1 硬件实现 4.2 软件实现系统调试与优化总结与展望 1. 引言 随着无人机技术的快速发展&#xff0c;无人机在军事侦察、环境监测、物流配送等领域的应用逐渐增多…