郑州免费建站,怎么用微信官方网站做二维码,网站建设 中企动力 顺德,wordpress微信捐赠文章目录 一、算法原理二、算法实战1. leetcode1576 替换所有的问号2. leetcode495 提莫攻击3. leetcode6 N字形变换4. leetcode38 外观数列5. leetcode1419 数青蛙 三、总结 一、算法原理
模拟就是用计算机来模拟题目中要求的操作#xff0c;模拟题目通常具有代码量大、操作… 文章目录 一、算法原理二、算法实战1. leetcode1576 替换所有的问号2. leetcode495 提莫攻击3. leetcode6 N字形变换4. leetcode38 外观数列5. leetcode1419 数青蛙 三、总结 一、算法原理
模拟就是用计算机来模拟题目中要求的操作模拟题目通常具有代码量大、操作多、思路繁琐的特点。所谓的模拟题用一句老话所就是照着葫芦画瓢根据题目的表述进行筛选提取关键要素按需求书写代码解决实际问题。 二、算法实战
1. leetcode1576 替换所有的问号 替换所有的问号 解题思路
这是一道简单的模拟题意思是一个字符串中有 ? 字符将些字符替换为a ~ z中的任意一个字符后使得这个字符串中不会出现连续两个以上的连续字符。首先我们遍历这个字符串先找到字符 ? 的位置然后从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){if((i 0 || ch ! s[i-1]) (i s.size()-1 || ch ! s[i1])){s[i] ch;break;} }}}return s;}
};2. leetcode495 提莫攻击 提莫攻击 解题思路
首先扫描这个数组使用cnt统计答案timeSeries[i]表示此时攻击的开始点timeSeries[i1]表示下一次攻击的开始点。
timeSeries[i 1] - timeSeries[i] duration表示两次攻击重叠。cnttimeSeries[i 1] - timeSeries[i]。timeSeries[i 1] - timeSeries[i] duration表示两次攻击不重叠 cntduration。
因为最后一次攻击是肯定会持续完的所以我们扫描数组的时候只需要扫描前n-1个元素。但是最后返回结果时候需要返回cntduration。
代码实现
class Solution {
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int cnt 0;for(int i 0; i timeSeries.size() - 1; i){int tmp timeSeries[i 1] - timeSeries[i];if(tmp duration)cnt tmp;elsecnt duration;}return cnt duration;}
};3. leetcode6 N字形变换 N字形变换 解题思路
首先我们应该先搞清楚从原字符串到目标字符串是如何变换而来的。 我们可以看到这个过程先将该字符串以N字形的顺序依次填入一个二维数组中然后将该二维数组中的内容从上到下一行一行拼接起来即可。这里我们可以从中找一些规律出来 代码实现
class Solution {
public:string convert(string s, int numRows) {string ret ;if(numRows 1)return s;int sub 2*numRows - 2;for(int i 0; i numRows; i){// 处理第一行和最后一行if(i 0 || i numRows-1){for(int j i; j s.size(); j sub){ret s[j];}}else{// 处理中间行for(int k i, p sub - k; k s.size() || p s.size(); k sub, p sub){if(k s.size()) ret s[k];if(p s.size()) ret s[p];}}}return ret;}
};4. leetcode38 外观数列 外观数列 解题思路
题目告诉了我们数列的每一项的变换过程是通过上一项推导出来的因此我们可以根据上一项模拟数列每一项的形成过程。在数列每一项的模拟过程中我们依然使用滑动窗口的算法原理来实现。
代码实现
class Solution {
public:string countAndSay(int n) {// 使用双指针算法进行模拟string start 1;while(--n){string tmp;for(int left 0, right 0; left start.size(); right){if(start[left] ! start[right]){tmp to_string(right - left);tmp start[left];left right;}}start tmp;}return start;}
};5. leetcode1419 数青蛙 数青蛙 解题思路
这道题目属于典型的比较难的模拟题先开一个哈希表然后将croak按照char, int的方式映射进哈希表这里的int指的是croak中字符的下标。开一个cnt来计数统计每一个字符出现的次数。
从前向后遍历字符串如果chc说明需要一只青蛙开始发出蛙鸣如果前面统计cnt[n - 1]这里的n-1表示croak字符串的最后一个’k’的下标意思是如果cnt[n - 1]已经出现过了说明前面有一只青蛙已经将croak这个字符串全部叫了一遍那么我们让前面的青蛙继续从头开始叫就可以了不需要增加青蛙的数量因此让cnt[n - 1]--cnt[0]如果cnt[n - 1] 0, 则直接让cnt[0]。
如果ch!c则说明一只青蛙正在发出蛙鸣的过程中此时我们让此时青蛙发出蛙鸣的字符的前一个字符的下标cnt[c前面的字符]- -然后让正在遍历的字符数量cnt[c]如果中途发现cnt[c前面的字符] 0 说明该字符连续出现了两次以上或者字幕出现的顺序有问题。直接返回-1即可。
最后我们统计的时候只需要关心croak中最后一个’k’出现了几次即可同时我们还需要遍历cnt中除最后一个元素外看前面的字母出现的次数是否为0若不为0说明字幕出现的顺序不符合要求直接返回-1。
代码实现
class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string t croak;int n t.size();vectorint cnt(n);unordered_mapchar, int hash;for(int i 0; i n; i) hash[t[i]] i;for(char ch : croakOfFrogs){if(ch c){if(cnt[n - 1]) cnt[n - 1]--;cnt[0];}else{int i hash[ch];if(cnt[i - 1])cnt[i - 1]--, cnt[i];else return -1;}}for(int i 0; i n - 1; i)if(cnt[i] ! 0) return -1;return cnt[n - 1];}
};三、总结
模拟的过程就是对真实场景尽可能的模拟但我们需要注意的是模拟题并没有我们所想象的那么简单它的代码中可能会有很多的坑我们在写模拟算法的过程中需要谨慎。
