wordpress 4.8.6,沈阳seo网站推广,做漆包线的招聘网站,宣传片拍摄流程文案目录 一#xff0c;算法介绍二#xff0c;算法原理和代码实现1576.替换所有的问号495.提莫攻击6.Z字形变换38.外观数列1419.数青蛙 三#xff0c;算法总结 一#xff0c;算法介绍 模拟算法本质就是依葫芦画瓢#xff0c;就是在题目中已经告诉了我们该如何操作… 目录 一算法介绍二算法原理和代码实现1576.替换所有的问号495.提莫攻击6.Z字形变换38.外观数列1419.数青蛙 三算法总结 一算法介绍 模拟算法本质就是依葫芦画瓢就是在题目中已经告诉了我们该如何操作我们只要把题目中的过程转化成代码即可。特点是思路简单难点是十分考验代码功底。 二算法原理和代码实现
1576.替换所有的问号 算法原理 没有那么多弯弯绕绕就是从前往后遍历字符串如果出现 ‘?’就用26个字母判断一个 ‘?’ 字符的前一个和后一个字符保证不出现前后两个连续相同的字符再把 ‘?’ 替换即可。 细节问题 要注意边界情况的判断就是当 ‘?’ 出现在第一个位置和最后一个位置的处理。 代码实现
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 || s[i-1] ! ch) (i n-1 || s[i1] ! ch)){s[i] ch;break;}}}}return s;}
};495.提莫攻击 算法原理 根据示例可以得到下面的规律 代码实现
class Solution {
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int n timeSeries.size();int ret 0;for(int i 1; i n-1; i){int x timeSeries[i] - timeSeries[i-1];if(x duration)ret duration;else ret x;}return ret duration;}
};6.Z字形变换 算法原理 我们不直接把字符进行Z变换把每个字符的下标抽象出来 然后在表中找出下标的规律直接在字符串中根据找出的下标取字符 细节问题 当给定行数为 1 行时计算的公差 d 0会造成死循环。所以要特殊处理此时直接返回原字符串即可。 代码实现
class Solution
{
public:string convert(string s, int numRows) {// 处理特殊情况if(numRows 1) return s;int d 2 * numRows - 2, n s.size();string ret;// 处理第一行的字符for(int i 0; i n; i d)ret s[i];// 出来中间行的字符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) ret s[i];if(j n) ret s[j];}}// 处理最后一行字符for(int i numRows-1; i n; i d)ret s[i];return ret;}
};38.外观数列 算法原理 本题使用模拟双指针 这里的双指针的作用就是从前往后遍历相同字符的区域计算出相同字符的个数。 代码实现
class Solution
{
public:string countAndSay(int n) {if(n 1) return to_string(1);string ret;string tmp to_string(1);for(int i 0; i n-1; i){ret ;int left 0, right 0, len tmp.size();while(right len){while(right len tmp[right] tmp[left]) right;ret to_string(right - left) tmp[left];left right;}tmp ret;}return tmp;}
};1419.数青蛙 算法原理 这道题在模拟算法中是一道比较难的题。 使用模拟哈希表。 遍历所给的字符串与叫声字符串进行对比映射 通过模拟可以进行总结 细节处理 (1) 两个哈希表的作用 第一个哈希表用数组模拟目的是统计字符出现的个数但不是用字符进行映射统计的而是根据叫声字符串 croak的下标。 第二个哈希表用 hash char, int 实现表示的是叫声字符串croak的每个字符和每个字符对应的下标。 (2) 当遍历完整个 croakOfFrogs 字符串后还需要把第一个哈希表遍历检查一下。 代码实现 根据上面的总结实现代码有多种方式下面的实现方式是一种通用的因为可能有些题目给的叫声字符串不是只有五个字符的croak而是其他更长的。 class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string t croak;int n t.size();vectorint hash(n); // 用数组模拟哈希unordered_mapchar, int index; // [x,x这个字符的下标]for(int i 0; i n; i)index[t[i]] i;for(auto ch : croakOfFrogs){if(ch c){// 判断最后一个字符是否存在if(hash[n-1] ! 0) hash[n-1]--;hash[0]; }else{int i index[ch]; // 找到字符的下标if(hash[i-1] 0) return -1;else hash[i-1]--, hash[i];}}// 除了最后一个字符k外其他字符如果还有出现直接返回-1for(int i 0; i n-1; i)if(hash[i] ! 0) return -1;return hash[n-1];}
};三算法总结 解决有关模拟类的题型最重要的就是根据题目写代码。有些模拟题可能正面做困难进行优化时一般都是找规律进行转换。
